Combinatorics

You know, for the Code Jam problem,  you just have to know how many "fair and square" numbers there are in a given interval. That's not necessarily the same thing as having to generate all of them.

Having done (or read) the analysis, we know that the number of "fair and square" numbers between m and n is the number of palindromic numbers between ⌈sqrt(m)⌉ and  ⌊sqrt(n)⌋ (we've shown how to get those values in previous posts)--let's call those values m' and n' respectively--for which the sum of the squares of the digits is less than 10.

Let's just consider d-digit base 10 numbers for d > 1, so we don't have to worry about 0 or 3. If [m'..n'] includes all d-digit base 10 numbers, or, given our theorem, at least the d-digit base 10 numbers from 10...01 to either 20...02 (if d is even) or 20..010...02 (if d is odd), then it has all the d-digit palindromes of the sort we want. (Writing them that way is serious handwaving about how big d is, sorry.) How many is that?

m `choose` 0 = 1
m `choose` n = product [m - n + 1..m] `div` product [1..n]

numTwoTwos d
    | d == 1    = 0
    | even d    = 1
    | otherwise = 2

numOneTwos d
    | d == 1    = 1
    | even d    = 0
    | otherwise = d `div` 2

numNoTwos d
    | d == 1    = 2
    | otherwise = if even d then n else 2 * n
                  where d' = d `div` 2 - 1
                        n = sum [d' `choose` i | i <- [0..min d' 3]]

numYs :: Int -> Int

numYs d = numTwoTwos d + numOneTwos d + numNoTwos d

(OK, so I went ahead and handled the d = 1 case.)

Then you need only actually generate and filter the Ys from m' to the next higher power of ten, and from the largest power of ten <= n' to n'. The others you can count. Sorry, Little John; if you wanted the numbers themselves you should have taken it up with the Code Jam people.

UPDATE: Fixed my errors, and went ahead and dealt with the one-digit case in the various num*Twos functions.

Now, the only question is what to do about the portion of the interval from ⌈sqrt(m)⌉ to ⌊sqrt(n)⌋ that doesn't cover a whole range of values for a given power of ten? More precisely, how to handle it efficiently, without generating Y values any more than we have to?

UPDATE: revised numNoTwos to omit 0 for the one-digit case, since the statement of the problem says it's not dealing with 0.