Wie kann das Element der Ziffernsummenfolge effizient gefunden werden?

20

Nur aus Interesse habe ich versucht, ein Problem aus der Kategorie "Recent" von Project Euler ( Digit Sum Sequence ) zu lösen . Ich kann mir aber keinen Weg ausdenken, um das Problem effizient zu lösen. Das Problem ist wie folgt (in der ursprünglichen Fragensequenz sind am Anfang zwei vorhanden, die Reihenfolge wird jedoch nicht geändert):

Die Ziffer Summenfolge ist 1,2,4,8,16,23,28,38,49 .... wo die nth Laufzeit der Summe der Sequenz ist Stellen in der Sequenz vorangeht. Finden Sie den 1015th Term der Sequenz.

Die naive Lösung kann nicht implementiert werden, da dies viel Zeit in Anspruch nimmt. Ich habe versucht , das Problem zu einem Fall von Matrix Exponentiation zu reduzieren (das wäre nimmt O(log(1015)) Menge an Zeit), konnte aber nicht mit einer solchen Wiederholung Einpassen der linearen Kriterien als Rezidiv für diese Sequenz ganz kommen ist eigenartig. Es ist ersichtlich, dass die Reihenfolge durch die Wiederholung bestimmt wird:

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

wobei an ist nth Term der Folge und d ist eine Funktion , die , wenn eine natürliche Zahl als Eingabe kehrt Summe der Ziffern der Zahl (zB gegeben.d(786)=21 ). Mein zweiter Ansatz bestand darin, ein Muster in der Sequenz zu finden. Es ist ersichtlich, dass die ersten Begriffe der Sequenz als geschrieben werden können

   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 ) ) ) )

Aus dem Muster darüber erlangt , dass nth Laufzeit der Sequenz kann durch das folgende Verfahren erzeugt werden:

  1. Schreiben Sie 2n1 1 mit einem Additionssymbol dazwischen.
  2. Verlassen Sie die erste und wenden Sie dann die Funktion d auf die nächsten 2 0 Terme an, dann auf die nächsten 2 1 Terme, dann auf die nächsten 2 2 Terme und so weiter.1d202122
  3. Wenden Sie dann die obige Methode rekursiv auf Argumente jeder angewendeten Funktion an.d

Wenn beispielsweise n = 3 ist, führen wir die folgenden Manipulationen durch:

    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 ) ) )

Durch die dynamische Programmierung kann ich die Erzeugung Laufzeit unter Verwendung des obigen Verfahrens in der Zeit O ( l o g ( 2 10 15 ) ) , was wiederum nicht besser als die naive Lösung.nthO(log(21015))

BEARBEITEN 1
Eine andere Sache, die beobachtet werden kann, ist, dass . Zum Beispiel ist d ( a 6 ) = d ( 23 ) = d ( 32 ) = 5 . Aber ich kann diesen Punkt nicht nutzen. Ich habe erneut versucht, eine lineare Wiederholungsrelation zu finden (für die Matrixexponentiation), aber ich kann sie nicht finden.d(an)=d(2n1)d(a6)=d(23)=d(32)=5

BEARBEITEN 2

Es folgt die Grafik, wenn die Sequenz für einen kleineren Bereich aufgezeichnet wird (die ersten Terme der Sequenz werden aufgezeichnet). 106Bildbeschreibung hier eingeben

PS: Ich weiß, dass es nicht ratsam ist, Lösungen von Project Euler anzufordern. Aber ich möchte nur eine neue Richtung oder einen Hinweis, da ich mich seit ein paar Tagen im Kreis bewege. Wenn das auch nicht akzeptabel ist, kann ich die Frage entfernen, wenn sie vorgeschlagen wird.

Schärpen
quelle
1
Ich fühle mich wie You are given a106 = 31054319.in der ursprünglichen Euler-Problematik ein Hinweis.
Filip Haglund
@FilipHaglund das ist kein Hinweis. Wie durch rohe Gewalt allein kann ich diesen Wert leicht berechnen. Es dient nur zur Überprüfung Ihres Ansatzes.
Sashas
3
Auch bei OEIS: oeis.org/A004207 .
Yuval Filmus
@EvilJS Ja, ich habe die Grafik so gezeichnet, dass sie allmählich im Zick-Zack ansteigt. Könnten Sie Ihren letzten Punkt
näher erläutern?
Geschieht etwas Interessantes, wenn man bedenkt, dass interessante Muster Mod 9 erscheinen, wenn man sich die Sequenz Mod 11 oder Mod 99 ansieht? Der Wert mod 11 kann aus der Summe der ungeraden Ziffern und der Summe der geraden Ziffern abgeleitet werden. Der Wert mod 99 kann aus der Summe benachbarter Ziffernpaare abgeleitet werden.
DW

Antworten:

4

Ihre Sequenz wird in oeis.org/A004207 als Ziffernsumme beschrieben. Es gibt einige gute Punkte ähnliche Sequenz mod 9 hat sich wiederholendes Muster , teilt es digital Wurzeln mit oeis.org/A065075 und oeis.org/A001370 . Ob diese Eigenschaften nützlich sind, ist ein offenes Problem (da es keine geschlossene Formgleichung für n - t h gibt ).(1,2,4,8,7,5)nth

Es gibt einige Eigenschaften dieser Sequenz erwähnenswert:
Wenn Sie berechnen Nummer, die Sie brauchen nur zu speichern Zähler (zu wissen , welche numer es war) und die Zahl selbst. Zum Neustart ist nichts mehr erforderlich, da die nächste Nummer die aktuelle Nummer + die Summe der Ziffern ist.nth

Wenn Sie zunächst ein paar Schritte unternehmen, um die Geschwindigkeit zu gewährleisten, sollten Sie die Zahlen in ein Array einfügen, um die naiven Mod- und Div-Berechnungen zu vermeiden, die teuer sind. Dies führt zu einer konstanten Beschleunigung, aber manchmal spielt es eine Rolle.

Vom Startpunkt aus können Sie den nächsten und den nächsten Punkt berechnen. Bis zu einem gewissen Punkt ist genau dieser Punkt die Änderung der Stellenzahl.
Was wichtiger ist, ändern sich die Muster mit zunehmender Anzahl.
Ziffernsummen sind im Vergleich zu Zahlen selbst klein, sodass sich bei den meisten Operationen nur der Teil der Zahl ändert.
Was können wir also wirklich zwischenspeichern?

Wir wissen, dass bei zwei Zahlen mit derselben Ziffernsumme die Addition zur nächsten Zahl dieselbe ist. Was ist mit dem nächsten?

Sasha

Der Spoiler-Alarm unten ist ein ziemlich explizites Cache-Muster

Es hängt von zusätzlichen Bedingungen ab, wie die Zahlen, die sich im Lauf nicht ändern , ich werde es Verschiebung nennen , Startbetrag als Start .

10009100nth

100
1001

10



1,2,4,8

11012183054065176077198059041003



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

Böse
quelle
4

Da Sie nach "einer neuen Richtung oder einem Hinweis" gefragt haben und ich die Antwort nicht kenne, lasse ich dies hier, ich hoffe, es ist hilfreich. einige Ideen:

Sinnvollerweise gäbe es ein Pattern Mod 9, da

k>1,kZ10k1mod9

Was Sie durch Induktion beweisen können.

Dies bedeutet, dass alle Zahlen zur Summe ihrer Ziffern mod 9 kongruent sind.

einn=d(einn)mod9

einn=einn-1+d(einn-1)=2d(einn-1)mod9

Wenn wir diese Wiederholung weiter ausbauen, erhalten wir

einn=2nmod9

Welches erklärt das Muster mod 9.

einn=9k+2n

Hier ist etwas weniger als allgemeiner Code:

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()

Die Handlung (für die ersten 100) sieht exponentiell aus, aber ich denke nicht, dass sie perfekt ist.

Grundstück für Lücken

Hier ist die Ausgabe von

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

Logarithmische Darstellung der Lücken

Das Letzte, was ich habe, ist, dass es den Anschein hat, als ob Sie, wenn Sie die Ziffern einer Zahl summieren und dann die Ziffern der resultierenden Zahl summieren und dies wiederholen, schließlich diese Zahl Mod 9 erhalten.

Sinnvoll angesichts der obigen Tatsache über Potenzen von 10 mod 9.

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

Es gibt jedoch eine interessante Folge von Zahlen.

Edit: Anscheinend wird dies eine "digitale Wurzel" genannt.

quietContest
quelle
1
Es wurde mindestens dreimal kommentiert. Auch wenn Sie eine Darstellung machen, die für Sie exponentiell aussieht, sollten Sie vielleicht den Logarithmus verwenden und darüber auf der Skalenachse informieren? Wenn Sie lesbare 10 ^ 16 Ausdrücke plotten würden, wäre ich wirklich beeindruckt.
Evil
Was wurde 3 mal kommentiert? Die Leute sagten, es gäbe einen "Pattern Mod 9", aber ich hatte das Gefühl, dass es nicht klar war, was das war. Ich habe nur ein bisschen recherchiert und kommentiert, was ich hatte, da ich nicht glaube, dass ich weiter daran arbeiten kann. Auch hier habe ich keine Lösung, aber die Frage stellte keine.
quietContest
Ein Log-Plot gemäß dem EvilJS-Vorschlag wurde hinzugefügt, kann nicht größer geplottet werden, da es zu Pausen kommt und ich wirklich keine Zeit habe, dieses Problem weiter zu verfolgen
quietContest