Właśnie poza zainteresowaniem próbowałem rozwiązać problem z kategorii „Ostatnie” projektu Euler ( sekwencja sumy cyfr ). Ale nie jestem w stanie wymyślić sposobu skutecznego rozwiązania problemu. Problem jest następujący (w oryginalnej sekwencji pytań ma dwie na początku, ale nie zmienia sekwencji):

Sekwencja sumy cyfr wynosi 1, 2, 4, 8, 1, 2, 23, 28, 38, 49 ... gdzie $n^{th}$ ciągu sekwencji jest sumą cyfr poprzedzających ją w sekwencji. Znaleźć $10^{15}th$ określenie sekwencji.

Naiwnego rozwiązania nie można wdrożyć, ponieważ zajmuje dużo czasu. I próbował zmniejszyć problem w przypadku potęgowania matrycy (, że wykonuje $O(log ( 10^{15}))$ czas), ale nie może się z tego ponownego montażu kryteria liniowe jak powtarzania dla tej sekwencji jest dość szczególny. Można zauważyć, że sekwencją rządzi powtarzalność:

gdzie $a_n$ jest $n^{th}$ ciągu sekwencji, a $d$ jest funkcją, która po podaniu liczby naturalnej jako wejścia zwraca sumę cyfr liczby (np.$\;d(786)=21$ ). Moje drugie podejście polegało na znalezieniu wzoru w sekwencji. Można zauważyć, że kilka pierwszych warunków sekwencji można zapisać jako

   a_1 = 1  
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(  
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

Z powyższego wzoru wynika, że $n^{th}$ ciągu sekwencji można wygenerować następującą metodą:

1. Napisz $2^{n-1}$ $1$ z symbolem dodania między nimi.
2. Opuszczając pierwszy , zastosuj funkcję d na kolejnych 2 0 terminach, a następnie na kolejnych 2 1 terminach, a następnie na kolejnych 2 2 terminach i tak dalej.$1$$d$$2^{0}$$2^{1}$$2^{2}$
3. Następnie zastosuj powyższą metodę rekurencyjnie do argumentów każdej zastosowanej funkcji .$d$

na przykład jeśli n = 3, wykonujemy następujące manipulacje:

    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

Poprzez dynamiczne programowanie można wygenerować określenie za pomocą powyższej metody w czasie O, ( l, o g ( 2 10 15 ) ) , która z kolei nie jest lepsza niż to naiwny roztworu.$n^{th}$$O(log ( 2^{10^{15}} ) )$

EDYCJA 1
Kolejną rzeczą, którą można zaobserwować, jest to, że . Na przykład d ( a 6 ) = d ( 23 ) = d ( 32 ) = 5 . Ale nie mogę skorzystać z tego punktu. Ponownie próbowałem znaleźć liniową relację powtarzalności (dla potęgowania macierzy), ale nie jestem w stanie jej znaleźć.$d(a_n) = d(2^{n-1})$$d(a_6)=d(23)=d(32)=5$

EDYCJA 2

Poniżej znajduje się wykres, gdy sekwencja jest wykreślana dla mniejszego zakresu (pierwsze składników sekwencji jest wykreślanych). $10^6$

PS: Wiem, że nie jest wskazane pytać o rozwiązania od Project Euler. Chcę tylko nowego kierunku lub podpowiedzi, ponieważ od kilku dni poruszam się w kółko. Jeśli jest to również nie do przyjęcia, mogę usunąć pytanie, jeśli zostanie zasugerowane.

$(1, 2, 4, 8, 7, 5)^\infty$$n-th$

$n-th$

Podejmując pewne kroki w celu zapewnienia prędkości na początku, dobrze jest umieszczać liczby w tablicy, unikając naiwnych modów i obliczeń div, które są drogie. Daje to stałe przyspieszenie, ale patrząc na czasy ma to znaczenie.

Od punktu początkowego można obliczyć następny i następny, i to działa do pewnego momentu, w tym samym punkcie zmienia się liczba cyfr.
Co ważniejsze, wzorce zmieniają się wraz ze wzrostem liczby.
Sumy cyfr są małe w porównaniu do samych liczb, więc tylko część liczb zmieni się w przypadku większości operacji.
Więc co tak naprawdę możemy buforować?

Wiemy, że przy dwóch liczbach z tą samą sumą cyfr, dodanie następnego numeru będzie takie samo. A co z następnym?

Sasha

Alert spoilera, poniżej jest dość wyraźny wzór pamięci podręcznej

Zależy to od dodatkowych warunków, takich jak liczby, które nie zmieniają się w biegu , nazywam to przesunięciem , kwotę początkową jako początek .

$100$$0$$9$$100$$n-th$

$100$
$100$$1$

$1$$0$

$1, 2, 4, 8$

$1$$101$$218$$305$$406$$517$$607$$719$$805$$904$$1003$

$100, 1000, 10000, 100000, 1000000...$
$100$

Ponieważ poprosiłeś o „nowy kierunek lub podpowiedź” i nie znam odpowiedzi, zostawię to tutaj, mam nadzieję, że jest to pomocne. jakieś pomysły:

Od tego czasu ma sens wzorzec mod 9

$\forall k > 1,k \in \mathbb{Z}\quad10^k \equiv 1 \mod 9$

Co możesz udowodnić przez indukcję.

Oznacza to, że wszystkie liczby są zgodne z sumą ich cyfr mod 9.

$a_n = d(a_n) \mod 9 \implies$

Jeśli nadal będziemy rozszerzać ten nawrót, otrzymamy

$a_{n} = 2^n \mod 9$

Co wyjaśnia wzór mod 9.

$a_n = 9k + 2^n$

Oto kilka mniej niż ogólny kod:

import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i 


a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

Fabuła (dla pierwszych 100) wygląda wykładniczo, ale nie sądzę, żeby była idealna.

Oto wynik działania

>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

Ostatnią rzeczą, którą mam, jest to, że jeśli zsumujesz cyfry liczby, a następnie zsumujesz cyfry liczby wynikowej i powtórzysz to, w końcu otrzymasz ten numer mod 9.

Ma to sens, biorąc pod uwagę powyższy fakt dotyczący mocy 10 mod 9.

Daje to jednak interesującą sekwencję liczb.

Edycja: Najwyraźniej nazywa się to „cyfrowym rootem”.