Jak skutecznie znaleźć element sekwencji Sumy cyfr?

20

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 nth ciągu sekwencji jest sumą cyfr poprzedzających ją w sekwencji. Znaleźć 1015th 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(1015)) 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ść:

an=an1+d(an1).....(1)

gdzie an jest nth 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 nth ciągu sekwencji można wygenerować następującą metodą:

  1. Napisz 2n1 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.1d202122
  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.nthO(log(21015))

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(an)=d(2n1)d(a6)=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). 106wprowadź opis zdjęcia tutaj

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.

sashas
źródło
1
Mam wrażenie, że You are given a106 = 31054319.w oryginalnym problemie Eulera jest podpowiedź.
Filip Haglund
@FilipHaglund, który nie jest wskazówką. Tak jak sama brutalna siła mogę łatwo obliczyć tę wartość. Służy tylko do sprawdzenia twojego podejścia.
sashas
3
Również w OEIS: oeis.org/A004207 .
Yuval Filmus
@EvilJS może tak, że wykreśliłem wykres w takim zakresie, że zwiększa się on stopniowo w sposób zygzakowaty. Czy mógłbyś rozwinąć swój ostatni punkt „„ wzorce buforowania… ”.
sashas
Biorąc pod uwagę, że ciekawe wzory pojawiają się w mod 9, czy dzieje się coś ciekawego, jeśli spojrzymy na sekwencję mod 11 lub mod 99? Wartość mod 11 można wyprowadzić z sumy cyfr o indeksie nieparzystym i sumy cyfr o indeksie parzystym. Wartość mod 99 można wyprowadzić z sumy sąsiednich par cyfr.
DW

Odpowiedzi:

4

(1,2,4,8,7,5)nth


nth

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 .

10009100nth

100
1001

10



1,2,4,8

11012183054065176077198059041003



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

Zło
źródło
4

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

k>1,kZ10k1mod9

Co możesz udowodnić przez indukcję.

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

an=d(an)mod9

an=an1+d(an1)=2d(an1)mod9

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

an=2nmod9

Co wyjaśnia wzór mod 9.

an=9k+2n

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.

fabuła dla luk

Oto wynik działania

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

logarytmiczny wykres luk

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.

nd(n)d(d(n))mod9

Daje to jednak interesującą sekwencję liczb.

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

quietContest
źródło
1
Zostało to skomentowane co najmniej trzy razy. Także kiedy robisz wykres, który wygląda wykładniczo, może powinieneś użyć logarytmu, poinformować o tym na osi skali? Jeśli planowałbyś czytelne terminy 10 ^ 16, byłbym pod wielkim wrażeniem.
Zły
Co zostało skomentowane 3 razy? Ludzie mówili, że istnieje „wzorzec mod 9”, ale czułem, że nie było jasne, co to było. Właśnie zbadałem i skomentowałem to, co miałem, ponieważ nie sądzę, że będę w stanie kontynuować pracę nad tym. Znów nie mam rozwiązania, ale pytanie nie wymagało takiego rozwiązania.
quietContest
Dodano wykres dziennika według sugestii EvilJS, nie mogę wykreślić większego wykresu, ponieważ liczba łamie się, a ja naprawdę nie mam czasu, aby kontynuować rozwiązywanie tego problemu
quietContest