First, for a number, *s*, to be a PSP it must have a root, *r*.
Let us call the digits of this root
*a*_{1},..., *a _{n}*, where

Our first question is how many digits are in *s*=*r*^{2}. I claim that
there are 2*n*-1 of them. This basically means that there is no increase
in the number of digits due to carry from the 2*n*-1'th digit.
To prove that this is the case, let us consider the situation in the top-most
digits of *r*^{2}. The value of *r* is smaller than
(*a _{n}*+1)*10

In fact, because having more than 2*n* 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*
2*n* 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

Together, these prove that the number of digits in *r*^{2} must be
2*n*-1.

Let us now consider *s*_{1},..., *s*_{2n-1},
the digits of *s*=*r*^{2}. One possibility is that all
*s _{i}* satisfy

This holds when all *b _{i}* are smaller
than 10. This is a good case for us, because the fact that the

We claim that in the remaining case, where some of the *b _{i}* are
greater than 9,

Consider which can be the maximal *i* for which *b _{i}*
is higher than 9. As demonstrated above, it certainly cannot be

Consider a specific digit, *s _{k}*, where

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}*=Σ

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

Because *b _{n}* is the maximum, the condition that

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:

- The number
*r*is 3. - 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. - 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. - 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
2*n*-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}_{1} +
C^{(N+1)÷ 4}_{2} +
C^{(N+1)÷ 4}_{3} +
C^{(N+1)÷ 4}_{4} [Counting the case that *n* is
even and *r* has up to four "1"s on either side.]

+

(C^{(N-1)÷ 4}_{1} +
C^{(N-1)÷ 4}_{2} +
C^{(N-1)÷ 4}_{3} +
C^{(N-1)÷ 4}_{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}_{0} +
C^{(N-1)÷ 4}_{1} +
C^{(N-1)÷ 4}_{2}
[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}_{1}
[*n* is even, and there is a "2" on either side.]

+

C^{(N-1)÷ 4}_{1}*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*=4*k*+1 or 4*k*+2, the result is

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

For completion, the latter case can also be stated as saying that if
*N*=4*k*-1 or *N*=4*k*, 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^{100} 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^{100}).
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.