## July 2013 solution

To answer the question, let us begin by considering what numbers could possibly be PSP.

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

Our first question is how many digits are in s=r2. 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 r2. The value of r is smaller than (an+1)*10n-1, so r2 is smaller than (an+1)2*102n-2. Because r is a palindrome, we know that an=a1. The least significant digit of r2 is a12 % 10, and because we know that r2 is also a palindrome, this must also be its most significant digit. If r2 has more than 2n-1 digits, we must have

(an+1)2 > 10 (an2 % 10)     (1)

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

an2 ÷ 10 ≤ an2 % 10     (2)

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

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

Let us now consider s1,..., s2n-1, the digits of s=r2. One possibility is that all si satisfy si=bi, where the bi are defined by

bij=1i aj*ai+1-j     (3)

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

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

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

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

However, this cannot be. The top digits of s should be b2n-1...bi+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 bi are smaller than 10.

The next observation to make is that the highest of all b values is bni=1n ai2.

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

Because bn is the maximum, the condition that s is PSP really boils down to r being a palindrome and Σi=1n ai2<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)÷ 41 + C(N+1)÷ 42 + C(N+1)÷ 43 + C(N+1)÷ 44 [Counting the case that n is even and r has up to four "1"s on either side.]
+
(C(N-1)÷ 41 + C(N-1)÷ 42 + C(N-1)÷ 43 + C(N-1)÷ 44)*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)÷ 40 + C(N-1)÷ 41 + C(N-1)÷ 42 [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)÷ 41 [n is even, and there is a "2" on either side.]
+
C(N-1)÷ 41*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:

(A3-2A2+11A+38)*A/24 + (B3-2B2+17B+44)*B/12 + 3

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

(k4-2k3+15k2+42k+24)/8

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

(3k4-2k3+45k2+146k+120)/24

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

(3k4-14k3+69k2+38k+24)/24

Stated in yet a third way, the answer is

(3N4-56N3+1104N2+2432N+6144)/6144 if N=4k
(N4-12N3+270N2+2180N+3705)/2048 if N=4k+1
(N4-16N3+312N2+1600N+1808)/2048 if N=4k+2
(3N4-44N3+954N2+4484N+9627)/6144 if N=4k+3

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 10100 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 (10100). Supposing the range was increased to the googolplex range (10googol), 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.