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 ciągu sekwencji jest sumą cyfr poprzedzających ją w sekwencji. Znaleźć 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 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 jest ciągu sekwencji, a jest funkcją, która po podaniu liczby naturalnej jako wejścia zwraca sumę cyfr liczby (np. ). 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 ciągu sekwencji można wygenerować następującą metodą:
- Napisz z symbolem dodania między nimi.
- 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.
- Następnie zastosuj powyższą metodę rekurencyjnie do argumentów każdej zastosowanej funkcji .
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.
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źć.
EDYCJA 2
Poniżej znajduje się wykres, gdy sekwencja jest wykreślana dla mniejszego zakresu (pierwsze składników sekwencji jest wykreślanych).
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.
źródło
You are given a106 = 31054319.
w oryginalnym problemie Eulera jest podpowiedź.Odpowiedzi:
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 .
źródło
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
Co możesz udowodnić przez indukcję.
Oznacza to, że wszystkie liczby są zgodne z sumą ich cyfr mod 9.
Jeśli nadal będziemy rozszerzać ten nawrót, otrzymamy
Co wyjaśnia wzór mod 9.
Oto kilka mniej niż ogólny kod:
Fabuła (dla pierwszych 100) wygląda wykładniczo, ale nie sądzę, żeby była idealna.
Oto wynik działania
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”.
źródło