Squares, primes and the numerical stratosphere

This page concerns an unassuming little maths problem, which I decided to look into for a bit of fun. To my surprise, the question turned out to have an unexpected connection to a famous problem at the cutting edge of number theory, and necessitated a trip off into the numerical stratosphere in search of some fairly large solutions. The maths used here is probably about first year undergraduate level, and the style is certainly more technical than my previous article, so come prepared.

While working on my follow up to the Pointless maths article, I became sidetracked by a nice little conundrum posted on Twitter:

This is exactly the sort of meaningless mathematical challenge that I enjoy, so let’s get stuck in.

Before we start, we need some notation. Let’s call the number that we are going to square x (we’re assuming that it’s a positive integer) and we’ll say that x has d digits. We want to find x such that x2 is equal to one of the twice-repeated string numbers described in the tweet.

First, let’s consider how large we should expect x2 to be, in terms of its number of digits. Since x has d digits, it satisfies the inequalities:

10d-1x < 10d

Since (10d-1)2 = 102d-2, which is the first integer with 2d-1 digits, and (10d)2 = 102d, which is the first integer with 2d+1 digits, x2 must have 2d-1 or 2d digits. Moreover, if x2 is to have a twice-repeated string of digits, as we wish, then it must have an even number of digits. Therefore, if we are able to find a solution x to our problem with d digits, then x2 will have to have 2d digits. This means that the string that will be repeated will have d digits, the same number as in x.

Now let’s think a little more about these numbers with repeating digits that we are interested in. For example, consider the number 345345. This number can be split up in the following way:

345345  =  345×103 + 345  =  345 (103 + 1)

Any such twice-repeated string number can be rewritten in this way. If we let z be the complete repeating number and  y be the number formed by the string that is repeated (e.g. z = 345345 and y = 345 in the above example) and if d is the number of digits of y, then we can write:

z = y (10d + 1)

This allows us to state our original problem symbolically. We wish to find a positive integer x, with d digits, such that:

                                                              x2 = y (10d + 1)                                       [Equation 1]

for some positive integer y, which must also have d digits. If we can find such numbers, then we are done, because the left hand side will definitely be a perfect square and the right hand side will definitely be a twice-repeating string number. However, it may turn out that no such numbers exist, in which case we would like to find a rigorous proof that the problem is impossible so that we can all stop worrying about it and sleep easily in our beds.*

Let’s suppose that a solution does exist and try to work out what it would look like. Note in particular that 10d + 1 has d + 1 digits, so it must be larger than x. Hold on to that thought, because in a minute it will prove to be a crucially important fact.

The fundamental theorem of arithmetic tells us that every whole number can be expressed as a unique product of primes, so let’s write 10d + 1 in this way:

10d + 1 = p1a1 p2a2pnan

Here, p1 , p2 , … , pn are distinct primes, each raised to some positive integer power
a1 , a2 , … , an . Incidentally, we know that the smallest of these primes is at least 7, because it is quite easy to show that 10d + 1 is not divisible by 2, 3 or 5.

Now, Euclid’s Lemma tells us that if a prime number divides a product of two numbers then it must divide one or both of these numbers. Here then, we have that each of the primes
p1 , p2 , … , pn divides 10d + 1, and from Equation 1 we see that 10d + 1 divides x2. Therefore all of the primes p1 , p2 , … , pn divide x2, which is the product of x and x. Therefore, all of the primes p1 , p2 , … , pn divide x, so x = w p1 p2pn for some positive integer w.

Suppose for a moment that every one of these primes appeared only once in the prime factorisation of 10d + 1. In other words, a1 = a2 = … = an = 1 and we can write
10d + 1 = p1 p2pn . This would mean that x = w (10d + 1), but since w is positive, this implies that x ≥ 10d + 1. However, the crucially important fact that we flagged up earlier told us that actually 10d + 1 > x. We therefore have a contradiction and so, if we have a solution, at least one of the primes in the factorisation of 10d + 1 must appear twice or more.

At this point, we can take a breather from the heavy analysis to investigate some actual numbers of the form 10d + 1, to see what their prime factorisations actually look like. These numbers are simply those that start and end with a 1, with 0s in between. Here are the first few of them, with their prime factorisations (which I got from here):

  • 101 + 1 = 11 (prime)
  • 102 + 1 = 101 (prime)
  • 103 + 1 = 1001 = 7 × 11 × 13
  • 104 + 1 = 10001 = 73 × 137
  • 105 + 1 = 100001 = 11 × 9091
  • 106 + 1 = 1000001 =101 × 9901
  • 107 + 1 = 10000001 =11 × 909091
  • 108 + 1 = 100000001 =17 × 5882353
  • 109 + 1 = 1000000001 = 7 × 11 × 13 × 19 × 52579
  • 1010 + 1 = 10000000001 = 101 × 3541 × 27961
  • 1011 + 1 = 100000000001 = 112 × 23 × 4093 × 8779

Finally, we have arrived at a number of the form 10d + 1 with a repeated prime factor, which is what we were looking for. I am quite surprised that it took so long, and it would be interesting to know whether there is a particular reason why these numbers seem to have so few repeated prime factors. Things don’t get any better in this respect either, since you have to wait until
1021 + 1 = 1000000000000000000001 = 72 × 11 × 13 × 127 × 2689 × 459691 × 909091 for the next one.**

Anyway, the repeated factor of 11 in 1011 + 1 gives us hope, since it suggests that we might be able to find some 11 digit solutions for x. We know that such an x must be divisible by all the distinct prime factors of 1011 + 1, so x will have to be a multiple of 11 × 23 × 4093 × 8779, which is equal to 9090909091. The first few multiples of this number provide us with the following “near misses”:

  • 90909090912 = 82644628100826446281
  • 181818181822 = 330578512403305785124
  • 272727272732 = 743801652907438016529

Note that these examples fail because the corresponding value of y (from Equation 1), the string of repeated numbers, has fewer than 11 digits, rendering our analysis invalid. However, the next seven multiples of 9090909091 all provide solutions to our problem:

  • 363636363642 = 1322314049613223140496
  • 454545454552 = 2066115702520661157025
  • 545454545462 = 2975206611629752066116
  • 636363636372 = 4049586776940495867769
  • 727272727282 = 5289256198452892561984
  • 818181818192 = 6694214876166942148761
  • 909090909102 = 8264462810082644628100

At this point, we run out of 11 digit solutions, as x and the corresponding y both tip over into twelve digits (in fact both x and y become equal to 1011 + 1) and our method stops working:

  • 1000000000012 = 10000000000200000000001
Slide1

The smallest square whose digits consist of the same string, repeated twice.

As we have already mentioned, we have to wait a long time for the next solutions to turn up, some 21-digit monsters. They are all multiples of 142857142857142857143, a number which rather beautifully contains three (and a bit) repetitions of the recurring part of the decimal expansion of 1/7 (looking back at our earlier solutions, they were clearly related to the decimal expansion of 1/11). This time there are only four solutions before the method breaks down, but they are rather lovely ones, borrowing the property of the decimal expansion of 1/7, whereby they are all (sort of) translated versions of one another (with the exception of the final digit in each case):

  • 4285714285714285714292 = 183673469387755102041183673469387755102041
  • 5714285714285714285722 = 326530612244897959184326530612244897959184
  • 7142857142857142857152510204081632653061225510204081632653061225
  • 8571428571428571428582 = 734693877551020408164734693877551020408164

Given how we derived these numbers, it is not too surprising that they are related to the decimal expansion of 1/7, since the number 142857142857142857143, of which these solutions are multiples, was derived by dividing the excess factor of 7 out of 1000000000000000000001. Nevertheless, it is quite an attractive and striking observation.

It would be interesting to look into these solutions and how frequently they occur in more depth, but, given that they seem to be tied in with a particularly mysterious unsolved*** problem in number theory (see the footnotes), I think pursuing this any further would likely drive me completely mad. Aside from anything else, there are practical difficulties when working with such big numbers. I looked for solutions with up to 29 digits, by checking the factorisations of 10d + 1 for repeated primes, but the online factoring calculator couldn’t go any higher than that. I believe, therefore, that the eleven solutions on this page (seven with 11 digits, four with 21 digits) are the only solutions for which the number to be squared is less than 1029 (one hundred thousand trillion trillion, or one hundred octillion). That means that there are only eleven perfect squares consisting of a twice repeated string of digits that are smaller than 1058.

Let’s just finish by marvelling at the size of this number. There are only eleven perfect squares of this kind that are less than:

10000000000000000000000000000000000000000000000000000000000
or
ten billion trillion trillion trillion trillion
or
ten octodecillion

Nice problem.


UPDATE (04/2015): Using Wolfram Alpha and the Number Empire online factoriser, I was able to extend the search up to 126 digit squares, revealing further families of solutions, including:

Seven 66 digit squares:

  • 3636363636363636363636363636363642 = 132231404958677685950413223140496132231404958677685950413223140496
  • 4545454545454545454545454545454552 = 206611570247933884297520661157025206611570247933884297520661157025
  • 5454545454545454545454545454545462 = 297520661157024793388429752066116297520661157024793388429752066116
  • 6363636363636363636363636363636372 = 404958677685950413223140495867769404958677685950413223140495867769
  • 7272727272727272727272727272727282 = 528925619834710743801652892561984528925619834710743801652892561984
  • 8181818181818181818181818181818192 = 669421487603305785123966942148761669421487603305785123966942148761
  • 9090909090909090909090909090909102 = 826446280991735537190082644628100826446280991735537190082644628100

Eight 78 digit squares:

  • 3846153846153846153846153846153846153852 = 147928994082840236686390532544378698225147928994082840236686390532544378698225
  • 4615384615384615384615384615384615384622 = 213017751479289940828402366863905325444213017751479289940828402366863905325444
  • 5384615384615384615384615384615384615392 = 289940828402366863905325443786982248521289940828402366863905325443786982248521
  • 6153846153846153846153846153846153846162 = 378698224852071005917159763313609467456378698224852071005917159763313609467456
  • 6923076923076923076923076923076923076932 = 479289940828402366863905325443786982249479289940828402366863905325443786982249
  • 7692307692307692307692307692307692307702 = 591715976331360946745562130177514792900591715976331360946745562130177514792900
  • 8461538461538461538461538461538461538472 = 715976331360946745562130177514792899409715976331360946745562130177514792899409
  • 9230769230769230769230769230769230769242 = 852071005917159763313609467455621301776852071005917159763313609467455621301776

There are a further seven 110 digit solutions and four 126 digit solutions, but let’s draw the line at 100 digits. Attempts to find even larger squares were thwarted by an inability to factorise 1064 + 1 (and by the fact that you have to stop somewhere!).

Together with the eleven solutions that we had already found, this allows to replace our earlier conclusion with the eminently more satisfying statement:
 

There are only twenty-six perfect squares of this kind smaller than a googol.

 


* If we are really unlucky, it may turn out to be impossible to find a solution and impossible to prove that no solution exists (see Gödel’s Incompleteness Theorems), but we would have had to have kicked a lot of black cats under a lot of ladders to fall prey to that one.

** Fascinatingly, I think that the reason that so few numbers of the form 10d + 1 seem to have repeated prime factors and, consequently, why there are so few solutions to this problem (or that the solutions are so very sparsely distributed, at any rate) may have something to do with the abc conjecture, which I was aware of, but had never actually bumped into ‘in the wild’ before.

Very loosely (and I’m no expert on this), the abc conjecture says that, given coprime positive integers a, b, c, such that a + b = c , c tends not to exceed the product of all the distinct prime factors of a, b, c by too much (in the sense that there are only a finite number of triples a, b, c for which c exceeds this product by a certain degree). As I understand it, this (sort of) has the effect of preventing the prime factors of c from being raised to high powers in its prime decomposition, since this would illegally push up c relative to the aforementioned product.

The expression 10d + 1 = C appears to be an example of the abc conjecture in action. The three terms are certainly coprime and as d increases, so does C. The effect, based on the abc conjecture, seems to be that the powers of the primes in the factorisation of C must remain low, to prevent C from excessively exceeding the product of its distinct prime factors with the 2 and 5 from the 10d term.

I certainly had no idea when I was starting out that the problem would be related to this result, so I really find this quite amazing!

*** Unless you are an expert in Inter-universal Teichmüller Theory of course.


Thomas Oléron Evans, 2014


Click here for the previous page in the Maths section.
Click here for the next page in the Maths section.

One thought on “Squares, primes and the numerical stratosphere

Leave a Reply

Your email address will not be published. Required fields are marked *