Ziffernfolge im Quadrat

[Otmar]

Gesucht ist die kleinste natürliche Zahl, deren Quadrat aus zwei gleichen hintereinander geschriebenen Ziffernfolgen besteht.

Beispiel: 55123775512377 wäre so eine Zahl, ist aber keine Quadratzahl.
Alles in üblicher in Dezimalschreibweise ohne führende Nullen.

Damit dieses Rätsel auch mit Schulwissen mit Zettel, Stift und etwas Überlegen lösbar wird, sei noch gesagt, dass die Quadratzahl mehr als 20 Stellen hat.

[Neuling]

Hallo Otmar, habe eine Quadratzahl gefunden. Ob sie allerdings die kleinste ist, ... ?

Mehr ->

a = 45454545455
a² = 2066115702520661157025

Lösungsweg:

Mehr ->

Da Du gesagt hast, dass die Zahl mehr als 20 Stellen hat, muss sie mindestens 22 Stellen haben. (Zwei mal hintereinander ergibt eine gerade Anzahl von Stellen.) Solch eine Zahl ist dann durch 1000000000001 teilbar. Denn so multipliziert erscheint jede 11stellige Zahl genau zwei mal hintereinander.
1000000000001 = 11*11*23*4093*8779 (Sorry, das hat mir der Computer ausgerechnet!)
Eine Quadratzahl enthält aber jeden Primzahlfaktor mindestens 2 mal oder richtiger gesagt, immer in geradzahliger Anzahl.

Warum ich meinen ersten Versuch dann mit 11*23*4093*8779 = 9090909091 gestartet habe, kann ich nicht mal richtig begründen. Mir war nur klar, dass wegen der zwei dann vorhandenen 11en die Quadratzahl auf alle Fälle durch 1000000000001 teilbar ist.
Leider ergab sich mit 9090909091² = 82644628100826446281 nur eine 20stellige Zahl, die aber schon verdammt gut aussah.
Zwei Dinge wusste ich - wenn ich auf dem richtigen Weg bin, dann müssen mittig die zwei Nullen verschwinden und ich muss mit einer Quadratzahl "erweitern". Bis ich auf Faktor 25 gekommen bin, hat's noch einen Moment gedauert. Und dass man dies eigentlich wegen 8*25 = 200 auch ohne zu Multiplizieren sehen konnte, ist mir auch erst so richtig bewusst geworden, nachdem ich das Produkt errechnet hatte.

Also: a = 5*11*23*4093*8779

Edit: Habe doch noch eine kleinere Quadratzahl gefunden!

Mehr ->

a = 4*11*23*4093*8779 = 36363636364
a² = 1322314049613223140496

Und diese müsste jetzt aber die kleinste sein, denn mit Faktor 9 und 9*8=72 hätte ich nur eine Null in der Mitte wegbekommen.

[Otmar]

Hallo Neuling,
du hast die kleinste und auch die nächstgrößere derartige Zahl gefunden.

Mehr ->

Mit Zettel und Stift hätte man die Zahl auch finden können, wenn man 100000000001 durch 11 geteilt hätte und vom Ergebnis über die alternierende Quersumme gefunden hätte, dass auch dieses durch 11 teilbar ist. Allerdings wäre es der Aufwand zu hoch, um nachzuweisen, dass 100000000001 nicht noch einen anderen Primfaktor hat, der mindestens zwei Mal vorkommt. Hier hätte man raten müssen, was bei einem Rätsel aber erlaubt ist. Aber du bist auf "Nummer Sicher" gegangen und hast die Faktorisierung besorgt.

Meine Lösung:

Mehr ->

Gesucht ist z mit z² = 10^k * b + b wobei b eine k stellige Zahl ist. Also z²=(10^k+1)b = a*b mit a = 10^k+1. Für a und b gilt (a-1)/10 <=b< a-1. Angenommen in a wäre jeder Primfaktor nur einfach vorhanden, dann müsste in b jeder Primfaktor von a enthalten sein, so dass a*b eine Quadratzahl ist. Dann wäre aber b >= a was nicht sein darf. Deshalb muss in der Zerlegung von a wenigstens ein Primfaktor mehrfach vorkommen und wir können a = p²*r schreiben mit p > 1 und so groß, dass in r alle Primfaktoren einfach sind. Dann ist b = r * q² wobei q zwar klein ist, aber wenigstens so groß, dass b k Stellen hat. Wegen r = a/p² ist b = a(q/p)² und wegen (a-1)/10 <= b = a(q/p)² muss (q/p)² >= 1/10 sein.

Aus der Aufgabenstellung wird entnommen, dass b mehr als 10 Stellen hat, also k >= 11 ist. Ein ersten mögliches a ist 100000000001. Das ist offenbar durch 11 teilbar, da die alternierende Quersumme von a durch 11 teilbar ist. a/11 = 9090909091, was man fast im Kopf ausrechnen kann. Da auch die alternierende Quersumme von a/11 durch 11 teilbar ist, denn sie ist 9*5 - 1 = 44, kommt in a der Primfaktor 11 mindestens zwei mal vor. Offenbar ist das mehrfache Auftreten von Primfaktoren in Zahlen 10^k+1 selten, denn für k < 11 ist es noch nicht passiert, was wir aus dem Hinweis in der Aufgabenstellung entnehmen. Deshalb kann man an dieser Stelle raten, dass 11 der einzige Primfaktor in a ist, der mehrfach (und höchstens dreifach) auftritt und liegt richtig damit, was man ja heutzutage per Computer leicht prüfen kann (so wie es Neuling gemacht hat). Nun ist p = 11 und q soll klein sein aber es muss q²/11² >= 1/10 sein weshalb wir für q=4 nehmen. Wegen z²=a*b = (p^2 r)*(r*q²)= (p r q)²=((a/p) * q)² ist z = (100000000001/11) * 4 = 9090909091*4=36363636364, die gesuchte Zahl.

Man kann beliebig viele solche Zahlen finden:

Mehr ->

Offenbar läßt 10^11 beim Dividieren durch 11²=121 den Rest 120. Also ist 10^11 = 121m'+120 = 121m-1. Dann ist (10^11)² = 121²m²-2*121m+1. Also ist der Rest von 10^22 bei Division durch 11² genau 1. Das heißt wiederum, dass 10^11 * 10^22 bei Division durch 11² wieder den Rest 120 läßt und mehr noch, auch wenn wir 10^11 beliebig oft mit 10^22 multiplizieren, bei Division durch 11² bleibt immer der Rest 120. Deshalb ist a(i) = 10^(11 + 22i) + 1 für alle natürlichen Zahlen i durch 11² teilbar und wir hätten unendlich viele Zahlen z(i)=4 a(i)/11 deren Quadrat eine Ziffernfloge ist, die zweimal hintereinander steht. Das Spiel geht nicht nur mit dem Primfaktor 11 sondern auch mit anderen Faktoren. z.B. mit 7: 10^(21+42i) ist immer durch 7² teilbar wodurch neue Zahlen (3/7) * 10^(21+42i) die Eigenschaft haben, dass beim Quadrieren eine doppelte Ziffernfolge entsteht.

[Neuling]

Hallo Otmar!

Ich muss mich selbst noch mal korrigieren.

Da ich nicht mehr editieren kann, hier wenigstens die Richtigstellung. In meinem Beitrag ist bei jedem Wert "10...01" eine Null zu viel drin. Habe zwar bei der Analysierung die exakte Zahl eingetippt, aber beim Dokumentieren - wahrscheinlich wegen der 11stelligen Zahl - immer bis 11 gezählt. Also, es müssen 10 Nullen zwischen den Einsen sein.

Mehr ->

Und hoffentlich lege ich mir mit den folgenden Zeilen nicht selbst den nächsten Stolperstein in den Weg.
Mir war Dein Hinweis, dass die Quadratzahl mehr als 20 Stellen hat, zu dicht an der Lösung. Eine Ansage in der Form, dass die gesuchte Zahl ein paar mehr als nur 10 Stellen hat, hätte mir gereicht. Vielleicht wolltest Du mit Deiner Vorgabe ja auch nur verhindern, dass jemand frustriert aufgibt, wenn er per Hand mehrere Zahlen der Form "10...01" in Primfaktoren zerlegt. (Hätte das wirklich jemand per Hand gemacht?) Und ehrlich gesagt, ohne die maschinelle Zerlegung wäre ich nicht so schnell (wenn überhaupt) zum Ziel gelangt. Denn nach einer 11 als Primfaktor, hätte ich als nächstes mit der 13 probiert. Mein erster gedanklicher Ansatz war, es müsste eine Zahl der Form a² mal (10...01)² sein. Die Primzahldarstellung von 100000000001 hat einen neuen Denkansatz ausgelöst und mich in die richtige Spur gelenkt.
Na egal. Und Deine Ausführungen schaue ich mir später noch in Ruhe an.

Zur weiteren Übung schiebe ich auch gleich noch eine Aufgabe zur Quadratzahlsuche nach.
Gruß Neuling

[Neuling]

Hallo Otmar!

Ein paar Fragen zu Deinem Lösungsweg.

Mehr ->

"Angenommen in a wäre jeder Primfaktor nur einfach vorhanden, dann müsste in b jeder Primfaktor von a enthalten sein, so dass a*b eine Quadratzahl ist. Dann wäre aber b >= a was nicht sein darf."

Wieso b ≥ a ? b = a denke ich, sicher nur verschrieben?

"Wegen r = a/p² ist b = a(q/p)² und wegen (a-1)/10 <= b = a(q/p)² muss (q/p)² >= 1/10 sein. "

Den letzten Schritt verstehe ich nicht.

"Deshalb kann man an dieser Stelle raten, dass 11 der einzige Primfaktor in a ist, der mehrfach (und höchstens dreifach) auftritt"

Höchstens dreifach ? wieso?

Diese Stelle ist mir auch nicht ausführlich genug beleuchtet. Die Primzahlsuche hätte mit 7 beginnen müssen (2, 3 und 5 kann man ausschließen) Und wenn man die kleinsten (?) zwei gleichen Primfaktoren gefunden hat, kann man die Suche beenden.
Angenommen es wären mehr "doppelte" drin, die ich alle "ausklammere", um so weiter entferne ich mich doch von der "Mindeststellenzahl", die man dann später wieder durch q² "auffüllen muss. ? Mache ich hier einen Denkfehler?


Zu Deiner "Hochrechnung"
Fakt ist, dass es für Deine Beispielaufgabe 7 Lösungen gibt (q kann 4, 5, 6, 7, 8, 9, und 10 sein) und q = 4 liefert die kleinste Quadratzahl.
Die Anzahl war abhängig von der kleinsten gefundenen Primzahl, die doppelt drin ist. q muss kleiner sein als 11.

Mit Deiner Hochrechnung hast Du gezeigt, dass ((10 hoch 33) + 1) eine weitere Zahl ist, mit der diese Aufgabe funktioniert? Okay. Mein Bauchgefühl sagt, dass es dann auch wieder genau 7 solcher Quadratzahlen gibt ???
Zwischen ((10 hoch 11) + 1) und ((10 hoch 33) + 1) könnten aber weitere solcher Zahlen liegen, die einen anderen doppelten Primfaktor enthalten.
Die Herleitung mit 7² verstehe ich nicht. Woher weißt Du, dass ((10 hoch 21) +1) durch 49 teilbar ist.

Gruß Neuling

[Otmar]

Sorry, ich hatte gerade alle deine Fragen beantwortet. Als ich wegschicken wollte, sagt mir das Forum, dass ich mich erneut anmelden muss, und alles war weg. Ich tippe das jetzt nicht nochmal ein.

[Otmar]

Zweiter und letzter Versuch:

Warum b>=a?

Mehr ->

Der Schluss kommt ja daher, dass a*b Quadratzahl ist. a*b ist natürlich auch Quadratzahl, wenn b noch weitere Primfaktorpaare enthält, die nicht in r enthalten sind.

Bei der zweiten Frage ist das Nachfragen berechtigt.

Mehr ->

Denn eigentlich folgt aus (a-1)/10 <= a(q/p)² ganz direkt bei Division durch a nur:
(q/p)² >= 1/10 - 1/(10a)

Es gibt zwei Möglichkeiten hier weiterzukommen:

Möglichkeit 1:

Mehr ->

Man merkt sich, dass in der Grenze 1/10 noch der Fehler 1/(10a) mit a > 10^11 ist und die eigentliche Grenze etwas kleiner ist. Also z.B. (q/p)²>0.09999999999. An den Stellen an denen ich weiter unten in meiner Lösung die Schranke benutze, spielt diese kleine Abweichung keine Rolle.

Der Ausdruck 0.09999999999 hat mir aber nicht gefallen und deshalb hab ich (q/p)²>= 1/10 geschrieben, wohl wissend, dass ich zur Not zeigen kann, dass auch diese Relation stimmt.

Und deshalb hier Möglichkeit 2:

Mehr ->

Zuerst untersuchen wir aus der Ausgangsrelation die Gleichung:
(a-1)/10 = a(q/p)² also
10^(k-1) = p²r(q/p)² = r q²
Hier erinnern wir uns, dass in r jeder Primfaktor nur einfach vorkommt. Daraus folgt, dass r entweder 10 oder 1 ist. Das steht aber in Widerspruch zu a=10^k+1=rp², denn 10^k+1 ist für kein k ein Vielfaches von 10, (also Fall r = 10 scheidet aus) und für kein k > 0 eine Quadratzahl. (Da bist du fit, das siehst du sicher leicht ) Also scheidet auch r = 1 aus und von der Ausgangsrelation (a-1)/10<=a(q/p)² bleibt nur das < Zeichen (a-1)/10<a(q/p)² und damit a-1<10a(q/p)² und weil hier beide Seiten ganzzahlig sind, bleibt a<=10a(q/p)² und nun endlich 1/10<=(q/p)². Für die Lösung der Aufgabe ist nicht viel gewonnen, aber es ist doch viel schöner.

Warum 11 höchstens dreifach?

Mehr ->

Wenn die 11 vier mal vorkommen würde, könnte man p²=(11²)²=121² ausklammern. Dann wäre ein kleineres (q/p)² und damit ein kleineres b möglich. Mit q = 39 hätte man (q/p)² = (39/121)²= 0.103886... Das wäre kleiner als (4/11)² und die oben angegeben Lösung wäre falsch. Kommt aber 11 höchstens dreifach vor, dann ist p²=11² und die angegebene Lösung stimmt.

Mehr ->

Natürlich kannst du mit 7 beginnen und feststellen, dass 10^11+1 nicht durch 7 teilbar ist. Die Teilbarkeit durch 11 sieht man aber sofort über die alternierende Quersumme. Es steht auch nirgends geschrieben, dass man die Primfaktorsuche bei der kleinsten möglichen Primzahl beginnen muss. Alle effizienten Verfahren, die ich zur Faktorisierung kenne, gehen statistisch vor. Aber das ist eine andere Baustelle.

Und wenn man die kleinsten (?) zwei gleichen Primfaktoren gefunden hat, kann man die Suche beenden.
Angenommen es wären mehr "doppelte" drin, die ich alle "ausklammere", um so weiter entferne ich mich doch von der
"Mindeststellenzahl", die man dann später wieder durch q² "auffüllen muss. ? Mache ich hier einen Denkfehler?

Ja, denn je größer p ist, desto größer ist die Chance ein geeignetes q zu finden, so dass (q/p)² nur wenig größer als 1/10 wird.

Beispiel: p²= 7² 11² 23^4 dann geht für q = 12881 und (q/p)² = 0.10000146...

zu deinem Bauchgefühl:

Mehr ->

10^1 + 1 = 11
10^2 + 1 = 101
10^3 + 1 = 7 * 11 * 13
10^4 + 1 = 73 * 137
10^5 + 1 = 11 * 9091
10^6 + 1 = 101 * 9901
10^7 + 1 = 11 * 909091
10^8 + 1 = 17 * 5882353
10^9 + 1 = 7 * 11 * 13 * 19 * 52579
10^10 + 1 = 101 * 3541 * 27961
10^11 + 1 = 11² * 23 * 4093 * 8779
10^12 + 1 = 73 * 137 * 99990001
10^13 + 1 = 11 * 859 * 1058313049
10^14 + 1 = 29 * 101 * 281 * 121499449
10^15 + 1 = 7 * 11 * 13 * 211 * 241 * 2161 * 9091
10^16 + 1 = 353 * 449 * 641 * 1409 * 69857
10^17 + 1 = 11 * 103 * 4013 * 21993833369
10^18 + 1 = 101 * 9901 * 999999000001
10^19 + 1 = 11 * 909090909090909091
10^20 + 1 = 73 * 137 * 1676321 * 5964848081
10^21 + 1 = 7² * 11 * 13 * 127 * 2689 * 459691 * 909091
10^22 + 1 = 89 * 101 * 1052788969 * 1056689261
10^23 + 1 = 11 * 47 * 139 * 2531 * 549797184491917
10^24 + 1 = 17 * 5882353 * 9999999900000001
10^25 + 1 = 11 * 251 * 5051 * 9091 * 78875943472201
10^26 + 1 = 101 * 521 * 1900381976777332243781
10^27 + 1 = 7 * 11 * 13 * 19 * 52579 * 70541929 * 14175966169
10^28 + 1 = 73 * 137 * 7841 * 127522001020150503761
10^29 + 1 = 11 * 59 * 154083204930662557781201849
10^30 + 1 = 61 * 101 * 3541 * 9901 * 27961 * 4188901 * 39526741
10^31 + 1 = 11 * 909090909090909090909090909091
10^32 + 1 = 19841 * 976193 * 6187457 * 834427406578561
10^33 + 1 = 7 * 11² * 13 * 23 * 4093 * 8779 * 599144041 * 183411838171
10^34 + 1 = 101 * 28559389 * 1491383821 * 2324557465671829
10^35 + 1 = 11 * 9091 * 909091 * 4147571 * 265212793249617641
10^36 + 1 = 73 * 137 * 3169 * 98641 * 99990001 * 3199044596370769

Im dich interessierenden Bereich kann man nur bei 10^21+1 noch eine Quadratzahl ausklammern.

Mehr ->

Die Herleitung mit 7² verstehe ich nicht. Woher weißt Du, dass ((10 hoch 21) +1) durch 49 teilbar ist.

Da hab ich nichts hergeleitet sondern nur die Lösung angegeben. Schau mal im Umfeld des Satzes von Fermat und Euler. Da wirst du sicher fündig. Ganz grob. Nach dem genannten Satz ist 10^(7*7-7)=10^42 = 1 (mod 49) Dann ist es naheliegend, dass 10^(42/2) = -1 (mod 49) ist, denn 10^(42/2) muss ja 1 oder -1 modulo 49 sein, damit 10^42=1 (mod 49) wird. Natürlich ist dann noch der Teilbarkeitstest nötig.

Edit: Hab gerade gemerkt, dass ich hier konsequent p und q getauscht hatte. Jetzt müsste es wieder passen. Hoffe, dass ich keine Stelle bei der Korrektur vergessen habe.

Edit 2: Bei Möglichkeit 1 musste noch a durch 10a ersetzt werden.

[Neuling]

Hallo Otmar!
Danke, Danke, Danke, muss das alles erst wieder in Ruhe durcharbeiten.
Ja, was Dir da passiert ist, ist ärgerlich. Habe es durch eigene Schuld auch schon geschafft, mich aus dem System zu klicken. Seitdem schreibe ich längere Kommentare am PC vor und kopiere sie dann in "Antwort erstellen".
LG Neuling

[Neuling]

Hallo Otmar!
Nicht dass Du denkst, Du hättest Dir diese ganze Arbeit umsonst gemacht. Ich habe mich schon mehrmals durch Deine Zeilen gekämpft, aber, indem Du versuchst mir etwas klar zu machen, entstehen neue Fragen. Und irgendwie kann ich grad nicht mehr, sorry.
Auch gerade erst gesehen, dass Du editiert hast. Hatte mir Deinen Beitrag rauskopiert und nicht wieder hier hereingeschaut.

Mehr ->

Ich bin z.B. nicht Deiner Meinung, dass, wenn 11 (hoch 4) in der Primfaktorzerlegung stecken würde, Du eine kleinere Quadratzahl gefunden hättest. Die zweiten 11² würden dann nur genauso wie die einfach vorkommenden Primfaktoren behandelt.

Und das mit meinem Bauchgefühl - da haben wir uns auch ein wenig missverstanden.
Ich behaupte (ohne es beweisen zu können), dass es zu jedem i in z² = (10 (hoch 11 + 22i) +1)*b genau sieben verschiedene b gibt, so dass z² die gewünschte Darstellung hat, mit z zweimal hintereinander geschrieben. Für i = 0 haben wir diese 7 Lösungen:
z = q * 11 * 23 * 4093 * 8779 mit q = 4, 5, 6, 7, 8, 9, 10

Und ich behaupte weiter (auch, ohne es beweisen zu können), dass es zu jedem i in z² = (10 (hoch 21 + 42i) +1)*b genau 4 verschiedene b gibt, so dass z² wieder die Darstellung mit z zweimal hintereinander hat. Für i = 0 müssten es diese 4 Lösungen sein.
z = q * 7 * 11 * 13 * 127 * 2689 * 459691 * 909091 mit q = 3, 4, 5, 6

(Interessant ist, dass x = 10 (hoch 21) + 1 einen Faktor 10000001 enthält.)

Gruß Neuling

[Otmar]

Das p q edit war ja fast zeitgleich mit deiner Antwort und mehr oder weniger offensichtlich. Die anderen Korrekturen sind eher belanglos. Also Wesentliches ist dir nicht entgangen.