Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Pablo Solis asked this at a recent 20 questions seminar at Berkeley. Is there a positive integer $N$, not of the form $10^k$, such that the digits of $N^2$ are all 0's and 1's?

It seems very unlikely, but I don't have a proof. It's easy to see that such a number must end in 1 or 9, and then easy to see that it must end in 01, 49, 51 or 99, and you can continue recursively for as long as you like, determining possible "suffixes". Using this, I had a computer check for me that there are no such N up to about $10^{24}$.

If you pretend that the digits of $N^2$ are randomly distributed, and $N$ has $n$-digits, there's a $(2/10)^{2n}$ chance of satisfying this condition. There are only $10^n$ $n$-digit numbers, so you might expect a $(4/10)^n$ chance of having a some $n$-digit number. This suggests we shouldn't expect to find anything.

(If you try the same problem in other bases, where the probabilities are better, you do find a few: in base 5, 222112144, 22222111221444 and 100024441003001 work.)

share|improve this question
1  
Greg Kuperberg posted python code to check up to 10^24 over at the 20-questions wiki. scratchpad.wikia.com/wiki/090917qa#4_Pablo_S –  Scott Morrison Oct 4 '09 at 20:13
5  
Problem F24 in Guy, Unsolved Problems In Number Theory, asks for squares, not $10^k,4\times10^k,9\times10^k$, with just two different decimal digits. He gives a list which also appears as sequence A016070 at the On-Line Encyclopedia of Integer Sequences, oeis.org/A016070. The largest known example is 81619 ($81619^2=6661661161$). It says if there's another example it exceeds $8.8\times10^9$. –  Gerry Myerson Feb 26 '10 at 5:29
    
I spent a few minutes writing Greg Kuperberg's code in C++ and let it run an hour or two to check up to $10^{32}$. Nothing found. –  Tapio Rajala Apr 25 '11 at 7:59

5 Answers 5

up vote 11 down vote accepted

In the interest of completeness, here is what I put on the 20-questions wiki — we might as well repeat it here in the $\infty$-questions site. I had basically the same idea as Ilya, do a branched search to look for the digits of $N^2$. However, the code that I wrote in Python works from the 10-adic end, while Ilya's works from the Archimedean end. Both programs support a heuristic model that implies that solutions in the integers are very unlikely. If you wanted an optimized search in the integers, you would work from both ends and try to match the partial solutions. And you would probably want to implement the algorithms in C++ rather than in Python.

maxmod = 10**24

def check(x):
    if not str(x**2).replace('0','').replace('1',''):
        print 'Eureka:',x,x**2

def search(x,mod):
    x %= mod
    if mod == maxmod:
        check(x)
        check(mod-x)
        return
    top = -(x**2/mod) % 10
    x += (top + top%2)/2 * mod
    search(x,mod*10)
    search(x + 5*mod,mod*10)

search(1,10)    # Solution is either 1 or 9 mod 10

Also, it's tempting to mark the problem as open rather than as a "puzzle". I did find several papers that analyzed the congruence structure of integers with restricted digits, and one that looked at prime factors. Two are by Erdos, Mauduit, and Sarkozy 1 2, and two are by Banks and Shparlinski (one also with Conflitti) 3 4. Presumably some of these authors can say whether the problem should be called open.

share|improve this answer

Let me redo the probabilistic argument. We know that the $k$ last digits of $n^2$ are determined by the $k$ last digits of $n$. For instance, $n^2$ ends with a $1$ if and only if $n$ ends with a $1$ or a $9$. By induction, one proves that there are $2^k$ $k$-uplets of digits $\bar a=a_1\ldots a_k$ such that the square of a number $n$ ending with $\bar a$ ends with $k$ ones and zeroes. For instance if $k=3$, the triplets are $001,249,251,499,501,749,751, 999$.

If $n$ is a solution to the problem, and $k$ is the number of digits of $n$, then $n$ must be an $\bar a$ as above. Take the square of such an $\bar a$. We know that its $k$ last digits are ones and zeroes. In order that it provides a solution, the $k$ first digits have to be ones and zeroes, a property whose probability is $5^{-k}$. Therefore, the probability that there be a solution $n$ of length $k$ is approximately $(2/5)^{-k}$. Since the series $$\sum_{k=1}^\infty\left(\frac{2}{5}\right)^k$$ converges, 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.

share|improve this answer

If that's of interest to anyone, here are the results of my Python program that was trying to find a possible prefix starting from 1:

(number of digits) (prefixes found) (random prefix's square)
1 1 1
2 1 100
3 3 11025
4 7 1110916
5 13 110103049
6 29 10110101401
7 54 1000000000000
8 109 110110079422225
9 211 11011100073896521
10 420 1011001100765105025
11 825 100111001106029802256
12 1665 10111011010034411118321
13 3278 1001010099998757262220676
14 6547 101001100011007822397559225
15 13029 10101011110111066632483438225
16 26204 1101001101100999240998885170436
17 51971 100101111100099999132148424632569
18 104374 11110111010101000021756144077830521

(19 was lost)

20 415887 101001001010000099981803716294793733281
21 831804 11110100101110110101012586511482091637081
22 1663040 1110000111001111100100391333262727080693449

It confirms what we knew about probability — it's highly unlikely there is such a number — but not much more yet.

share|improve this answer

This reminds me of the first problem Knuth proposed for the "Aha" Sessions (1985): find all positive integers N such that the decimal digits of N and N2 are both in nondecreasing order from left to right.

The report is here: http://www-cs-faculty.stanford.edu/~knuth/papers/cs1055.pdf and the videos available in http://scpd.stanford.edu/knuth/index.jsp

Maybe it just doesn't help, but I think some of the analysis could (like the discovery of pumping lemmas).

share|improve this answer

The probability argument is deceptive: there is 0 probability that a random integer is a prime, yet they are infinitely many. So even if the probability that there is an integer lower than N that has the property goes to 0 as N increases, does not rule out their existence.

Same arguments can be used for squares, i.e. the probability that a number in [1,N] is a perfect square converges to 0 as N grows.

share|improve this answer
17  
The key isn't so much that the probability are tending to 0 as that that it does so very quickly. The general rule is this: We know (from the Borel-Cantelli lemmas) that if we consider a set of independent events with probabilities p_1, p_2, ... and the sum of the p_i's converge, then almost surely only finitely many events hold. Conversely, if the sum diverges, almost surely infinitely many. In a crude sense, the probability type argument would say that P(N is a square)=1/Sqrt(N) and P(N is prime)=1/Log N correspond to divergent sequences, while the all (0,1) probability (4/10)^n doesn't –  Kevin P. Costello Oct 23 '09 at 20:19
    
No, sometimes the probability arguments provide the solid intuition and may lead to a formal proof. –  Ilya Nikokoshev Oct 23 '09 at 20:39

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.