MB Matheblog # 43

A jubilee: This website was launched 25 years ago.

blog overview previous article

main page index website

202x-xx-xx

deutsche Version

This article presents an unsolved problem in number theory. It is the second open problem on this website; the first was about "Nearest neighbours" (see Blog # 15 und the related problem).  –  Here is the conjecture still waiting for a proof:

The numbers \(~100^{_~m}~\) with \(~m\in N_o~\) are the only positive squares containing only the digits \(~0~\) and \(~1~\).

"Squares" are understood to be squares of integers.

As we shall see, it seems to be quite probable that the conjecture is true. The conjecture may appear surprising or curious; but first and foremost it is astonishing that it is known at least since 1962 without getting much attention. Open problems in number theory are normally discussed in detail within the mathematical community  –  but not this problem. Some research gives scarce hints to a few people having thought about the problem with large time gaps between the publications.

Typical for number theory problems is a very simple proposition lacking a simple proof.

We begin with the history of the problem. We shall cite the known sources in chronological order.

The problem was offered  –  maybe for the first time  –  at the Leningrad Mathematical Olympiad in 1962. One might belatedly feel sorry for the students trying to solve it. On the website mathoverflow we find the comment "My guess is that the problem committee thought they knew a solution... Pretty sure they were wrong." (→ Source, see comments)

It seems that the problem slept until 1984 when Stan Wagon published it as problem # 909 on p. 20 in the January 1984 issue of Crux Mathematicorum. This renowned publication was founded in 1975 by the Canadian Mathematical Society and contains one of the world's oldest and most extensive problem collections.

Stan Wagon received an answer in Crux Mathematicorum by Stanley Rabinowitz in 1985 (March 1985 issue, p. 94-95). He considers the conjecture to be true because he checked all integers up to \(~10^{_~18}~\) by squaring them. He also explains that the number of integers \(~n~\) with \(~k~\) digits for which the last \(~k~\) digits of \(~n^2~\) are in \(\{0,1\}\) (we will refer to them as admissible \(~n~\)) is small for each \(~k~\) and can be easily computed.

Again there follows a gap of more than 20 years.

In 2009 we find the problem in the  20 questions seminar  of Berkeley University, posed by Pablo Solis  –  apparently unaware of the earlier contributions.

In short succession mathoverflow publishes several contributions. Apparently for the first time we find some real mathematics applied to the problem. Kim Morrison starts with a probabilistic view onto the truth of the conjecture. He gets answers which essentially claim it to be true. The final comment (in 2010) by Denis Serre is "I bet that there are only finitely many solutions. But if you do not find a short one, I guess there will be no solution at all."  –  A discussion of the probabilistic approach will be given below.  –  In the mathoverflow contributions we find again (as with Stanley Rabinowitz 1985, see above) the notion of admissable \(~n~\) with \(~k~\) digits which can be computed by iteration. This will also be discussed further below.

Tapio Rajala reports in 2011 on mathoverflow that he checked all \(~n\le 10^{_~32}~\)  –  considerably more than Stanley Rabinowitz in 1985 (see above)  –  and found no counterexample to the conjecture.

After 28 years, in 2012, Crux Mathematicorum recollects the open problem of 1984 (see above) und asks again for a solution (Crux Vol. 38(4), p. 144).

In 2012 we find the problem in  StackExchange. Hagen von Eitzen essentially repeats the probabilistic result given by Denis Serre in 2010 (see above). However, his list of admissable \(~n~\) with \(~k\le 4~\) digits is not complete.

The OEIS sequence A098608 lists the numbers \(~100^{_~m}~\) with \(~m\in N_o~\) and was in 2025 complemented by the comment that this sequence contains the only positive squares of integers with digits in \(\{0,1\}\)  –  naturally marked as "conjecture".

After having given the history of the problem we now want to analyze the admissable \(~n~\) and the corresponding probabilities for the conjecture.  –  We start with the following points for the admissable \(~n~\).

• We will not consider \(~n~\) with \(~0~\) as last digit. Deletion or addition of \(~0\)s  at the end of \(~n~\) has no effect to \(~n^2~\) only having digits in \(\{0,1\}\) or not.


• A necessary condition for  "\(n^2~\) has only digits in \(\{0,1\}\)"  is  "the last \(~k~\) digits of \(~n^2~\) are in \(\{0,1\}\)".  For this condition exists an iterative algorithm which computes the admissable \(~n~\) (see below).


• The definition of admissable \(~n~\) implies that for admissable \(~n~\) with \(~k+1~\) digits the last \(~k~\) digits are determined by the admissable \(~n~\) with \(~k~\) digits. In each step, the algorithm prepends a leading digit to each of the the \(~n~\) computed in the previous step. Because it occurs that \(~0~\) is prepended the admissable \(~n~\) may contain leading \(~0\)s.


• In the next point we shall embark into the theory leading to the algorithm. But beforehand we do some empirical work and specify admissable \(~n~\) for small \(~k~\).

  Admissable \(~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
  ...
  The table shows that  –  as anticipated  –  in each row we find leading digits prepended to the \(~n~\) in the row above. But we find much more: Each step doubles the number of admissable \(~n~\).  We get a table somewhat similar to the Pascal triangle  –  but here each entry determines the two entries below; furthermore, the prepended digits always differ by \(~5~\).  These propositions will be proven below.  –
  That the condition "admissable" is only necessary and not sufficient for  "the digits of \(~n^2~\) are in \(\{0,1\}\)"  is exemplified by the first entries of the \(~4\)th row of the table:
   n         n²
  0001         1
  5001  25010001
  0501    251001
  5501  30261001
  4251  18071001
  9251  85581001
  ...

• Now to the proof:
  Take an admissable \(~n=a_{_~k}~..._~a_{_~1}\).  For \(~k\le 4~\) we already know the digits \(~a_{_~j_~}\) with \(~a_{_~1}\in \{1,9\}\). We now determine \(~a_{_~k+1}\)  for admissable \(~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_~}\] Let \(~b~\) be the \(~(k+1)\)th  digit of \(~n^2\).
  Let \(~q~\) be the \(~(k+1)\)th  digit of \(~{n'~}^2\). Our aim is \(~q\in \{0,1\}\). \[q=(b+2\cdot a_{_~1}\cdot a_{_~k+1})~\text{mod}~10\] For fixed \(~{a_1}_~\) the factor \(~2~\) in \(~q~\) leads to \(~5~\) pairs for \(~q~\): \[\textbf{(1)}~~~~a_{_~k+1}\in \{0,5\},~\{1,6\},~\{2,7\},~\{3,8\},~\{4,9\}\] In (2) and (3) we take \(~a_{_~k+1}\in \{0,1,2,3,4\}~\); then a second solution is given by addition of \(~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~\) even:   \(q=0~\) gives \(~a_{_~k+1}=0~\) for \(~b=0~\) and \(~a_{_~k+1}=5-b/2~\) else.
        \(b~\) odd:   \(q=1~\) gives \(~a_{_~k+1}=0~\) for \(~b=1~\) and \(~a_{_~k+1}=(11-b)/2~\) else.

          With (1) we get for every \(~{a_{_~k+1}}_~\) from the previous step another \(~{a_{_~k+1}}_~\) by addition of \(~5~\). \[\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~\) even:   \(q=0~\) gives \(~a_{_~k+1}=b/2~\).
        \(b~\) odd:   \(q=1~\) gives \(~a_{_~k+1}=(b-1)/2~\).

          With (1) we get for every \(~{a_{_~k+1}}_~\) from the previous step another \(~{a_{_~k+1}}_~\) by addition of \(~5~\).



• Summary of the proof and the algorithm

  There exist exactly \(~{2^k}_~\) admissable \(~n~\) with \(~k~\) digits (leading \(~0\)s  are allowed).

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

  \(k~→~k+1\)
  The \(~n~\) from the \(~k\)th step get a prepended \(~{a_{_~k+1}}_~\) by (2) and (3); these formulae can be simplified:

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


• Two examples for \(~n~\) with \(~k=4~\) (see table obove) \(~→~_~n'~\) with \(~k=5~\) (two results)
  • \[~~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, see above) und Hagen von Eitzen (2012, see above) get the same result for the probability \(~{p_k}_~\) for  "\(~n_~\) with \(~k_~\) digits (leading \(~0\)s  allowed; no \(~0~\) as last digit) has a square \(~{n^2}_~\) containig only \(~0\)s and \(~1\)s " :

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

  Serre and von Eitzen give the explanation:
  There are \(~{2^k}_~\) admissable \(~n_~\).  For each of these \(~n~\) the probability for the leading \(~k~\) digits of \(~{n^2}_~\) lying in \(\{0,_~1\}\) is \(_~(1/5)^k\).

  Kim Morrison (2009, see above) gives the same value for \(~{p_k}_~\),  but presents an explanation without recourse to admissable \(~n_~\).


• Serre and von Eitzen add the \(~{p_k}_~\) over \(~k~\) and get an expected value \(~E~\) for the number of squares with digits in \(\{0,_~1\}\). They arrive at different \(~E_~\).  Serre's sum starts with \(~k=1~\) (correct, with \(~E=2/3_~\)) and von Eitzen's sum with \(~k=0_~\) (incorrect, with \(~E=5/3_~\)).  –  But we know that there are no counterexamples to the conjecture for \(~n~\) with less than \(~33~\) digits (Tapio Rajala 2011, see above). The sum of the \(~{p_k}_~\) beginning with \(~k=33_~\) is \(~E\approx 1,23\cdot 10^{-13}\).  –  The probabilistic approach is no substitute for a proof but its result explains why some authors believe the conjecture to be true.


• A possible objection against the probabilities specified above could be that for \(~n~\) with \(~k~\) digits their squares \(~n^2~\) can have fewer than \(~2k~\) digits (keep in mind that \(~n~\) may have leading \(~0\)s ).  Therefore the value \(_~(1/5)^k~\) for the leading digits is too small on average. But an empirical survey shows that the ratio (leading digits)\(/(2k)_~\) converges fast to \(~1~\) with increasing \(~k_~\);  so \(_~(1/5)^k~\) can be taken for a good approximation.


• A serious weak point with computing probabilities as shown above is the assumption that the leading digits of \(~{n^2}_~\) (to the left of the pre-determined last \(~k~\) digits) are uniformly distributed. We cannot a priori rule out that the very special choice of admissable \(~n~\) leads to an unbalanced distribution of the leading digits of \(~{n^2}\).

  All leading digits of \(~n^2_~\) (beginning with the \(~(k+1)\)th digit from the right) taken together over all \(~2^k_~\) admissable \(~n~\) with \(~k~\) digits show the proportion of \(~0\)s  and \(~1\)s  (empirically) converging to roughly \(~20_~\%~\) with growing \(~k~\)  –  just as one would expect.  But this is only a mean value and certainly not valid for particular admissable \(~n_~\).  We give an example:

  • \(~k=6~,~~~\)admissable \(_~n:~375.501~~~\) \(~~n^2=141.001.001.001\)
     Only one digit of \(~n^2~\) is \(\notin \{0,_~1\}\).
     For \(~k=6~\) the probability of one or none
     digit of \(~n^2_~\) not lying in \(~\{0,_~1\}~\) is (rounded) \(5_~\%_~\).
  
  For a small \(~k~\) we have found a square number with unexpectedly many \(~0\)s  and \(~1\)s. This is by no means sufficient to confidently expect counterexamples to our conjecture (having in mind that none were found for \(~k\le 32~\)). This section should only show that Serre's and von Eitzen's probabilistic reasoning may raise some doubt regarding the randomness of the leading digits of \(~n^2\).

Only small progress with this open number theoretical problem was achieved since 1962. We want to point out three remarks:

• Up to \(~n=10^{32}~\) no counterexamples to the conjecture have been found.

• For every \(~k\in \textbf{N}~\) there are exactly \(~2^k~\) positive integers \(~n~\) with \(~k~\) digits (leading \(~0\)s  allowed) with the last \(~k~\) digits of \(~n^2_~\) in \(\{0,_~1\}\). These integers can be computed by recursion. Further research can be restricted to these \(~n_~\).

• Probability estimations for the validity of the conjecture should be treated with some reservation.

Last update 2025-05-16

blog overview   |    previous article