MB Matheblog # 43

Ein Jubiläum: Diese Website wurde vor 25 Jahren gestartet.

Inhalt Blog voriger Eintrag

zur Leitseite Index der gesamten Website

2025-09-09                    Kommentare sind willkommen.

english version

Quadratzahlen, die nur Nullen und Einsen enthalten

Dieser Blogbeitrag stellt ein ungelöstes zahlentheoretisches Problem vor. Es ist das zweite ungelöste Problem auf dieser Website; das erste hatte das Thema "Nächste Nachbarn" (siehe Blog # 15 und Problem # 114).  –  Hier ist die Vermutung, deren Beweis bisher nicht geglückt ist:

Die Zahlen \(~100^{_~m}~\) mit \(~m\in N_o~\) sind die einzigen positiven Quadratzahlen, die nur die Ziffern \(~0~\) und \(~1~\) enthalten.

Unter "Quadratzahlen" sind Quadrate ganzer Zahlen zu verstehen.

Wie wir noch sehen werden, spricht viel dafür, dass diese Vermutung richtig ist. Sie mag durchaus überraschend oder merkwürdig erscheinen, aber vor allem ist es erstaunlich, dass sie mindestens seit 1962 bekannt ist, aber bisher recht wenig Beachtung gefunden hat. Offene zahlentheoretische Probleme werden in der Regel eingehend in der mathematischen Welt diskutiert; hier ist das nicht der Fall. Eine Recherche ergibt allerdings (spärliche) Hinweise darauf, dass sich in größeren Abständen immer wieder mal jemand Gedanken zu diesem interessanten Problem gemacht hat.

Wie oft in der Zahlentheorie ist die Formulierung der Vermutung höchst einfach, aber einen einfachen Beweis scheint es nicht zu geben.

Wir wollen zunächst der Geschichte dieses Problems nachgehen. In chronologischer Reihenfolge werden die Quellen, soweit bekannt, im Folgenden aufgeführt.

Bei der Leningrader Mathematik-Olympiade 1962 taucht dieses Problem (erstmals?) auf. Man möchte die Schülerinnen und Schüler noch nachträglich bedauern, die versucht haben, eine Lösung zu finden. Ein späterer Kommentar dazu findet sich auf der Website mathoverflow; in deutscher Übersetzung heißt es dort: "Ich vermute, dass das Programmkomitee geglaubt hat, eine Lösung zu kennen. Ich bin ziemlich sicher, dass sie falsch lagen." (→ Quelle, siehe Kommentare)

Anscheinend wurde das Problem erst 1984 wieder aufgegriffen. Stan Wagon stellte es als Problem 909 auf S. 20 der Januar-Ausgabe 1984 des Magazins Crux Mathematicorum vor. Diese renommierte Publikation, seit 1975 herausgegeben von der Canadian Mathematical Society, enthält eine der weltweit ältesten und umfangreichsten Problemsammlungen.

1985 erhielt Stan Wagon eine Antwort von Stanley Rabinowitz, ebenfalls in Crux Mathematicorum (März-Ausgabe 1985, S. 94f). Er hält die Vermutung für richtig, da er alle Zahlen bis \(~10^{_~18}~\) durch Quadrieren getestet hat. Außerdem führt er aus, dass die Anzahl der \(~k-\)stelligen \(~n~\),  für die die letzten \(~k~\) Stellen von \(~n^2~\) in \(\{0,1\}\) sind (im Folgenden als erlaubte \(~n~\) bezeichnet), für jedes \(~k~\) gering ist und leicht berechnet werden kann.

Wieder gibt es eine lange Pause von mehr als 20 Jahren.

Im  20 questions seminar  der Universität Berkeley stellt Pablo Solis 2009 das Problem erneut zur Debatte, offenbar in Unkenntnis der früheren Beiträge.

In kurzer Folge gibt es daraufhin mehrere Beiträge auf mathoverflow. Anscheinend finden wir hier zum ersten Mal eine inhaltliche Beschäftigung mit dem Problem. Am Ursprung dieser Beiträge steht Kim Morrison, der den Anstoß zu einer probabilistischen Betrachtung des Problems gibt. Er erhält einige Antworten  –  im Wesentlichen mit dem Tenor, dass die Vermutung mit hoher Wahrscheinlichkeit richtig ist. Der abschließende Kommentar 2010 (in deutscher Übersetzung) stammt von Denis Serre: "Ich wette, dass es nur endlich viele Lösungen gibt. Aber wenn Sie keine kurze finden, vermute ich, dass es überhaupt keine Lösungen gibt." Unter einer Lösung ist hier ein Gegenbeispiel zur Vermutung zu verstehen.  –  Eine Diskussion des probabilistischen Arguments folgt weiter unten.  –  In den mathoverflow-Beiträgen wird auch (wie bei Stanley Rabinowitz 1985, s.o.) der Ansatz verfolgt, dass man iterativ alle erlaubten \(~k-\)stelligen \(~n~\) konstruieren kann. Auch dies wird weiter unten ausführlich behandelt.

Tapio Rajala vermeldet 2011 auf mathoverflow, dass er alle \(~n\le 10^{_~32}~\) getestet hat, also erheblich mehr als Stanley Rabinowitz 1985 (s.o.); einen Widerspruch zur Vermutung hat auch er nicht gefunden.

Nach 28 Jahren erinnert sich Crux Mathematicorum an das immer noch offene Problem von 1984 (s.o.) und stellt es 2012 erneut seiner Problemlösergemeinde vor (Crux Vol. 38(4), S. 144).

2012 greift  StackExchange  das Problem auf. Hagen von Eitzen kommt dort im Wesentlichen zum gleichen probabilistischen Resultat wie schon Denis Serre 2010. Seine Liste der erlaubten \(~k-\)stelligen \(~n~\) ist allerdings unvollständig.

Die OEIS-Folge A098608 ist eine Liste der Zahlen \(~100^{_~m}~\) mit \(~m\in N_o~\) und wurde 2025 um den Kommentar ergänzt, dass es sich bei dieser Folge um die einzigen positiven Quadratzahlen handelt, die nur Ziffern in \(\{0,1\}\) haben  –  natürlich gekennzeichnet als "Conjecture".

Soweit zur Historie des Problems. Im Folgenden sollen sowohl die erlaubten \(~n~\) als auch die zugehörigen Wahrscheinlichkeiten für die Vermutung genauer untersucht werden.  –  Die folgenden Spiegelpunkte betreffen die erlaubten \(~n~\).

• Es reicht aus, nur \(~n~\) ohne Endnullen zu betrachten, da Streichung oder Hinzufügung von Endnullen nichts daran ändert, dass \(~n^2~\) nur Ziffern in \(\{0,1\}\) hat oder nicht hat.


• Eine notwendige Bedingung für  "\(n^2~\) hat nur Ziffern in \(\{0,1\}\)"  ist  "letzte \(~k~\) Ziffern von \(~n^2~\) sind in \(\{0,1\}\)".  Für diese Bedingung gibt es einen Algorithmus zur Berechnung der zugehörigen ("erlaubten") \(~n~\) (s.u.).


• Nach Definition der erlaubten \(~n~\) gilt für \(~(k+1)-\)stellige erlaubte \(~n~\),  dass die letzten \(~k~\) Stellen bereits festgelegt sind durch die erlaubten \(~k-\)stelligen \(~n~\).  Der iterative Algorithmus muss also in jedem Schritt lediglich führende Ziffern hinzufügen. Die erlaubten \(~n~\) dürfen führende Nullen aufweisen.


• Bevor man in die Theorie einsteigt, die zur Formulierung des Algorithmus führt, kann man sich einen ersten Überblick verschaffen und für kleine \(~k~\) die erlaubten \(~n~\) suchen.

  Erlaubte \(~n~\):
  k=1                     1                                      9
  k=2         01                  51                  49                  99
  k=3    001       501       251       751       249       749       499       999
  k=4 0001 5001 0501 5501 4251 9251 3751 8751 1249 6249 0749 5749 4499 9499 4999 9999
  ...
  Die Tabelle zeigt, dass  –  wie erwartet  –  in jeder Zeile lediglich führende Ziffern zu den Einträgen in der Zeile darüber hinzugefügt werden. Aber sie zeigt noch mehr: Im Schritt von \(~k~\) nach \(~k+1~\) entstehen aus jedem Eintrag der \(~k-\)ten Zeile genau \(~2~\) Einträge in der \(~(k+1)-\)ten Zeile (die ähnlich wie im Pascal'schen Dreieck direkt darunter stehen); und die hinzugefügten Ziffern unterscheiden sich immer um \(~5~\).  Diese Aussagen müssen weiter unten natürlich noch bewiesen werden.  –
  Dass bei den erlaubten \(~n~\) tatsächlich nur eine notwendige, aber keine hinreichende Bedingung für  "Ziffern von \(~n^2~\) in \(\{0,1\}\)"  vorliegt, sieht man beispielhaft an den ersten Einträgen der \(~4.~\) Zeile in der Tabelle oben:
   n         n²
  0001         1
  5001  25010001
  0501    251001
  5501  30261001
  4251  18071001
  9251  85581001
  ...

• Nun zum Beweis:
  Sei \(~n=a_{_~k}~..._~a_{_~1}\)  ein erlaubtes \(~n~\),  evtl. mit führenden Nullen. Für \(~k\le 4~\) kennen wir die Ziffern \(~a_{_~j}\)  schon; insbesondere ist immer \(~a_{_~1}\in \{1,9\}\). Wir suchen nun \(~a_{_~k+1}\)  für erlaubte \(~n'=a_{_~k+1_~}a_{_~k}~..._~a_{_~1}\).
  \[{n'~}^2~=~(n+a_{_~k+1}\cdot 10^{_~k_~})^{_~2}~=~n^2 + 2\cdot n\cdot a_{_~k+1}\cdot 10^{_~k_~} + a_{_~k+1}^2\cdot 10^{_~2k_~}\] \(b~\) sei die \(~(k+1)-\)te Stelle von \(~n^2\).
  \(q~\) sei die \(~(k+1)-\)te Stelle von \(~{n'~}^2\). Ziel ist \(~q\in \{0,1\}\). \[q=(b+2\cdot a_{_~1}\cdot a_{_~k+1})~\text{mod}~10\] Bei festem \(~{a_1}_~\) erhält man wegen dem Faktor \(~2~\) in \(~q~\) jeweils dieselben \(~5~\) Ergebnisse für \(~q~\) für die Zahlenpaare \[\textbf{(1)}~~~~a_{_~k+1}\in \{0,5\},~\{1,6\},~\{2,7\},~\{3,8\},~\{4,9\}\] In (2) und (3) betrachten wir zunächst \(~a_{_~k+1}\in \{0,1,2,3,4\}~\); eine zweite Lösung ergibt sich dann durch Addition von \(~5_~\). \[\textbf{(2)}~~~~a_1=1:~~~q\in \{_~(b+2_~a_{_~k+1})~\text{mod}~10~~|~~a_{_~k+1}\in \{0,1,2,3,4\}_~\}\]       \(b~\) gerade:   \(q=0~\) ergibt \(~a_{_~k+1}=0~\) für \(~b=0~\) und \(~a_{_~k+1}=5-b/2~\) sonst.
        \(b~\) ungerade:   \(q=1~\) ergibt \(~a_{_~k+1}=0~\) für \(~b=1~\) und \(~a_{_~k+1}=(11-b)/2~\) sonst.

          Wegen (1) erhält man zu jedem so ermittelten \(~{a_{_~k+1}}_~\) ein weiteres, indem man \(~5~\) addiert. \[\textbf{(3)}~~~~a_1=9:~~~q\in \{_~(b+8_~a_{_~k+1})~\text{mod}~10~~|~~a_{_~k+1}\in \{0,1,2,3,4\}_~\}\]       \(b~\) gerade:   \(q=0~\) ergibt \(~a_{_~k+1}=b/2~\).
        \(b~\) ungerade:   \(q=1~\) ergibt \(~a_{_~k+1}=(b-1)/2~\).

          Wegen (1) erhält man zu jedem so ermittelten \(~{a_{_~k+1}}_~\) ein weiteres, indem man \(~5~\) addiert.



• Zusammenfassung des Beweises mit Formulierung des Algorithmus

  Es gibt genau \(~{2^k}_~\) erlaubte \(~n~\) mit \(~k~\) Stellen (evtl. mit führenden Nullen).

  Induktiv:   \(k=1~~→~~n\in \{1,~9\}\)

  \(k~→~k+1\)
  Den Zahlen aus dem \(~k-\)ten Schritt werden \(~{a_{_~k+1}}_~\) vorangestellt; dafür lassen sich (2) und (3) noch etwas vereinfachen:

  \(a_1=1~:~~a_{_~k+1}=\lfloor~(11-b)/2~\rfloor~\) und \(~a_{_~k+1}=(_~\lfloor~(11-b)/2~\rfloor +5)~\text{mod}~10\)
  \(a_1=9~:~~a_{_~k+1}=\lfloor~b/2~\rfloor~\) und \(~a_{_~k+1}=\lfloor~b/2~\rfloor +5\)


• Zwei Beispiele für \(~n~\) mit \(~k=4~\) (siehe Tabelle oben) \(~→~_~n'~\) mit \(~k=5~\) (zwei Ergebnisse)
  • \[~~n=375\boldsymbol{1}~~→~~a_1=1\] \[~~n^2=140\boldsymbol{7}0001~~→~~b=7\] \[~~~~~~→~~a_{k+1} \in \{2,_~7\}~~→~~n_1' = \boldsymbol{2}3751,~~n_2' = \boldsymbol{7}3751\]
  • \[~~n=074\boldsymbol{9}~~→~~a_1=9\] \[~~n^2=5\boldsymbol{6}1001~~→~~b=6\] \[~~~~~~→~~a_{k+1} \in \{3,_~8\}~~→~~n_1' = \boldsymbol{3}0749,~~n_2' = \boldsymbol{8}0749\]

• Denis Serre (2010, s.o.) und Hagen von Eitzen (2012, s.o.) kommen zum gleichen Ergebnis für die Wahrscheinlichkeit \(~{p_k}_~\),  dass ein \(~k-\)stelliges \(~n_~\) (evtl. mit führenden Nullen, aber ohne Nullen am Ende) zu einem \(~{n^2}_~\) aus Nullen und Einsen führt:

• \(p_k=(2/5)^k\)

  Serre und von Eitzen geben folgende Begründung:
  Es gibt \(~{2^k}_~\) erlaubte \(~n_~\).  Für jedes dieser \(~n~\) ist die Wahrscheinlichkeit, dass die führenden \(~k~\) Stellen von \(~{n^2}_~\) in \(\{0,_~1\}\) liegen, gleich \(_~(1/5)^k\).

  Kim Morrison (2009, s.o.) berechnet den gleichen Wert für \(~{p_k}_~\),  aber auf anderem Weg, ohne Rückgriff auf die erlaubten \(~n_~\).


• Serre und von Eitzen addieren die \(~{p_k}_~\) über \(~k~\) und erhalten so einen Erwartungswert \(~E~\) für die Anzahl solcher Quadratzahlen. Sie kommen aber zu unterschiedlichen Ergebnissen, da Serre die Summe bei \(~k=1~\) beginnen lässt (was korrekt ist, mit \(~E=2/3_~\)),  aber von Eitzen bei \(~k=0_~\) (nicht korrekt, mit \(~E=5/3_~\)).  –  Nun wissen wir aber schon, dass es für \(~n~\) mit weniger als \(~33~\) Stellen keine Gegenbeispiele zur Vermutung gibt (Tapio Rajala 2011, s.o.). Addiert man die \(~{p_k}_~\) ab \(~k=33_~\),  erhält man \(~E\approx 1,23\cdot 10^{-13}\).  –  Der probabilistische Ansatz ersetzt natürlich keinen Beweis, erklärt aber die Einschätzung mehrerer Autoren, dass die Vermutung richtig ist.


• Ein möglicher Einwand gegen die angegebenen Wahrscheinlichkeiten könnte sein, dass für die \(k-\)stelligen erlaubten \(~n~\) die Quadrate \(~n^2~\) nicht immer \(~2k~\) Stellen haben. Deshalb ist der Wert \(_~(1/5)^k~\) für die führenden Stellen im Mittel zu niedrig. Eine empirische Untersuchung zeigt jedoch, dass der Anteil (tatsächlich vorhandene Stellen)\(/(2k)_~\) mit wachsendem \(~k~\) schnell gegen \(~1~\) konvergiert, so dass \(_~(1/5)^k~\) wohl ein guter Näherungswert ist.


• Ein ernstzunehmender Schwachpunkt bei der Berechnung der Wahrscheinlichkeiten ist die Unterstellung, dass die führenden Stellen in \(~{n^2}_~\) (vor den festgelegten letzten \(~k~\) Stellen) gleichmäßig verteilt sind. Es ist nicht a priori auszuschließen, dass die spezielle Wahl der erlaubten \(~n~\) zu einer ungleichmäßigen Ziffernverteilung führt.

  Nimmt man alle führenden Ziffern von \(~n^2~\) für alle \(~2^k~\) \(k\)-stelligen erlaubten \(~n~\) zusammen, so schwankt der Anteil der Nullen und Einsen in den führenden Stellen von \(~n^2~\) mit wachsendem \(~k~\) wie erwartet eng um \(~20_~\%~\).  Aber das ist nur ein (empirischer) Durchschnittswert und gilt keineswegs für die einzelnen erlaubten \(~n_~\).  Dazu ein Beispiel:

  • \(~k=6~,~~~\)erlaubtes \(n:~375.501~~~\) \(~~n^2=141.001.001.001\)
     Nur eine Ziffer von \(~n^2~\) ist \(\notin \{0,_~1\}\).
     Für \(~k=6~\) ist die Wahrscheinlichkeit für
     eine oder keine Ziffer von \(~n^2~\) \(\notin \{0,_~1\}~\) ca. \(5_~\%_~\).
  
  Schon für ein kleines \(~k~\) haben wir eine Quadratzahl mit unerwartet vielen Nullen und Einsen gefunden. Das reicht zwar überhaupt nicht aus, um zuversichtlich Gegenbeispiele zur Vermutung zu erwarten (immerhin gibt es ja bis \(~k=32~\) keine). Aber Zweifel am probabilistischen Ansatz von Serre und von Eitzen sind angebracht, weil dort unterstellt wird, dass die führenden Ziffern von \(~n^2~\) zufällig verteilt sind.

Einer Lösung dieses offenen zahlentheoretischen Problems ist man bisher nur wenig nähergekommen. Drei Dinge gilt es festzuhalten:

• Bis \(~n=10^{32}~\) gibt es keine Gegenbeispiele zur Vermutung.

• Für beliebig große \(~k~\) lassen sich diejenigen \(~2^k~\) \(k\)-stelligen \(~n~\) exakt angeben, für die die letzten \(~k~\) Stellen von \(~n^2~\) in \(\{0,_~1\}\) liegen. Nur für diese \(~n~\) lohnen sich weitergehende Untersuchungen.

• Einschätzungen der Wahrscheinlichkeit für die Richtigkeit der Vermutung sind sehr mit Vorsicht zu betrachten.

Stand 2025-05-05

Inhalt Blog   |    voriger Eintrag

Manfred Börgens   |   Zur Leitseite