Using your Head is Permitted

July 2013 solution

First, for a number, s, to be a PSP it must have a root, r. Let us call the digits of this root a₁,..., a_n, where n is the number of the root's digits, and we count them from a₁ being the least significant one.

Our first question is how many digits are in s=r². I claim that there are 2n-1 of them. This basically means that there is no increase in the number of digits due to carry from the 2n-1'th digit. To prove that this is the case, let us consider the situation in the top-most digits of r². The value of r is smaller than (a_n+1)*10^n-1, so r² is smaller than (a_n+1)²*10^2n-2. Because r is a palindrome, we know that a_n=a₁. The least significant digit of r² is a₁² % 10, and because we know that r² is also a palindrome, this must also be its most significant digit. If r² has more than 2n-1 digits, we must have

In fact, because having more than 2n digits is clearly impossible (this would have required switching the first "10" in Equation (1) with "100", leaving no possible solutions), the number of digits should be exactly 2n in this case, which indicates also

The most significant digit of any number cannot be zero, so a_n must be between 1 and 9. Equation (1) rules out all a_n in the range 1-7, and Equation (2) rules out the remaining two cases.

Together, these prove that the number of digits in r² must be 2n-1.

Let us now consider s₁,..., s_2n-1, the digits of s=r². One possibility is that all s_i satisfy s_i=b_i, where the b_i are defined by

This holds when all b_i are smaller than 10. This is a good case for us, because the fact that the a_i sequence is palindromic also ensures, by Equation (3), that the b_i sequence is, so r² is a palindrome, and therefore also a PSP.

We claim that in the remaining case, where some of the b_i are greater than 9, r² is necessarily not a palindrome.

Consider which can be the maximal i for which b_i is higher than 9. As demonstrated above, it certainly cannot be b_2n-1. Suppose we have found the maximal such i, then b_i+1,..., b_2n-1 are all less than 10.

Consider a specific digit, s_k, where k>i. First, we have the equality, s_k=s_2n-k, because s is a palindrome. Next, we have s_2n-k=b_2n-k, because there is, by assumption, no carry in the least digits of s. (All b values up to b_2n-k are, by assumption, less than 10.) Finally, we have b_2n-k=b_k, because the b sequence is palindromic. In total, this adds up to s_k=b_k, so the top digits of s are equal to the top b values.

However, this cannot be. The top digits of s should be b_2n-1...b_i+1 plus any carry that came from the i'th digit. The equality suggests that no such carry occurred, contrary to our assumption.

Therefore, no such maximal i exists. All b_i are smaller than 10.

The next observation to make is that the highest of all b values is b_n=Σ_i=1ⁿ a_i².

(We know that it is the highest because of, e.g., the rearrangement inequality.)

Because b_n is the maximum, the condition that s is PSP really boils down to r being a palindrome and Σ_i=1ⁿ a_i²<10.

Taking into account that in a palindrome every digit except the middle digit (if such exists) appears an even number of times, this last condition can be broken down into several cases:

1. The number r is 3.
2. The palindrome r has up to four "1"s on either side and possibly a "1" in the middle if there is a middle digit. The rest of it is zeros.
3. The palindrome r has a "2" in the middle, and up to two "1"s on either side. The rest of the digits are zeroes.
4. The palindrome r has a "2" on either side and possibly a "1" in the middle, if there is a middle. The rest of the digits are zeroes.

Putting all this together, what we have is the following:

The original number, s, is known to have up to N digits, so 2n-1≤N, so n≤ (N+1)÷ 2. Each side of r is therefore at most n÷ 2 ≤ (N+1)÷ 4 in length, if n is even, and at most (n-1)÷ 2 ≤ (N-1)÷ 4 if n is odd.

It is possible to count all possibilities by enumerating over the possible values of n, while ensuring that at each point the first and last digits are nonzero. We will use a simpler solution: we will take the maximal n value (separately for even n and odd n values) and will place digits in r allowing leading zeros. Finally, we will discard any leading and trailing zeroes to form the final value of r. The closed-form computation is therefore as follows:

1 [Counting the case r=3.]
+
C^{(N+1)÷ 4}₁ + C^{(N+1)÷ 4}₂ + C^{(N+1)÷ 4}₃ + C^{(N+1)÷ 4}₄ [Counting the case that n is even and r has up to four "1"s on either side.]
+
(C^{(N-1)÷ 4}₁ + C^{(N-1)÷ 4}₂ + C^{(N-1)÷ 4}₃ + C^{(N-1)÷ 4}₄)*2+1 [Counting the case that n is odd and r has up to four "1"s on either side. We multiply by 2 because the middle digit may be either "0" or "1", and we add 1 so as to count the possibility that r=1.]
+
C^{(N-1)÷ 4}₀ + C^{(N-1)÷ 4}₁ + C^{(N-1)÷ 4}₂ [Counting the case that n is odd, there is a "2" in the middle digit, and there are up to 2 "1"s on either side.]
+
C^{(N+1)÷ 4}₁ [n is even, and there is a "2" on either side.]
+
C^{(N-1)÷ 4}₁*2 [n is odd, there is a "2" on either side, and possibly a "1" in the middle.]

Although perhaps a bit long, this is nevertheless a closed-form formula. It can be made even simpler by noting that it is the sum of two polynomials of degree 4, one in A=(N+1)÷ 4 and the other in B=(N-1)÷ 4. The result is:

Otherwise stated, if N=4k+1 or 4k+2, the result is

and if N=4k+3 or 4k+4, the result is

For completion, the latter case can also be stated as saying that if N=4k-1 or N=4k, the result is

Stated in yet a third way, the answer is

Q.E.D.

And now for the promised credits and references.

As stated, the idea for this riddle came from Graham Farr, who asked me, and some other people, a very similar question about a product of palindromes being, itself, a palindrome. To answer Graham's question, all the machinery described above was developed.

Later, Norman Do found out that, quite coincidentally, on Google's most recent Code Jam competition, a very similar question was asked about palindromes that are squares of palindromes. (See here.) As this had a cleaner and more elegant solution to it, I decided to go with that as the Using your Head is Permitted riddle for this month.

Some time later, Norman Do pointed out to us that Google had published their canonical solution for the problem. (See here.) Ironically, Google's solution for counting PSPs in the range of up to N=100, while basically the same to what is written above up until this point, ends with the following paragraph:

"To find all [PSP] numbers [with up to 100 digits], it therefore suffices to consider only palindromes consisting of these four digits [0,1,2,3], with the sum of squares of digits at most 9. It turns out this is a small enough set that it can be directly searched, allowing us to generate the full list of all [PSP] numbers up to 10¹⁰⁰ in a few seconds - and thus allowing us to solve the largest dataset."

Clearly, no generating and searching needs to be done once a closed-form formula is known, and "a few seconds" is a major overkill for the method presented here, which merely requires calculating a simple polynomial.^(*)

To illustrate the difference: Google's question required one to count the PSPs in ranges up to a googol (10¹⁰⁰). Supposing the range was increased to the googolplex range (10^googol), the techniques shown here would have still been able to solve the question in no time, whereas Google's canonical solution would not have sufficed.

^(*) Readers who actually compare this riddle with the Google Code Jam problem will note that Google asked the solvers to count PSPs between given A and B, but these A and B are not required to be powers of 10. This does, indeed, mean that the simple polynomial shown here would not solve the problem. Nevertheless, this difficulty isn't very hard to overcome. I leave the exact technique to the reader.

Back to riddle

Back to main page