Monday 14 March 2011

Happy Pi Day, everyone! (3/14, get it?) I got back from PyCon last night and have been trying to figure out how to integrate the energy and direction from the conference into my regular life here in Boston. It’s a challenge, but PyCon is always an invigorating experience, and I’m really glad to have gone.

In honor of Pi Day, I’ll present you with two puzzles I heard at PyCon, one as part of Google’s recruiting efforts, and one as part of a panel about Python in middle school.

Google’s puzzle: A number is a palindrome if the digits read the same
backwards as forwards: 1, 88, 343, 234565432, and so on. What is the
sum of the digits in the number of palindromes less than a googol
(10^{100})? That is, count all the palindromes greater than
zero and less than a googol, then sum all the digits in that number,
not the sum of the digits in all the palindromes.
What’s your answer? They actually posed it as “write a program to
compute the sum of the digits, etc,” and were interested in the
shortest program, but I prefer it as a pure math question.

The education question was a puzzle presented to middle-school kids, who were asked to write programs to find the answer. Imagine a set of stairs with n steps from bottom to top. You can walk up the stairs by taking every step, or by skipping a single step any time you want. You can’t skip more than one step at a time. How many different ways are there to walk up a flight of n steps? For example, representing a step as t and a skip as k, you could do a flight of 3 steps as ttt, tk, kt, and 4 steps could be tttt, ttk, tkt, ktt, or kk.

Update: I posted my solutions.

## Comments

ZeD12:11 AM on 15 Mar 2011You can't skip more than one step at a time.[...]

4 steps could be tttt, ttk, tkt, ktt, or kkumm

4 steps could be tttt, ttk, tkt and ktt, but how can they be

kk?johannes1:36 AM on 15 Mar 2011You mean Half Tau Day?

http://halftauday.com/

Christos Georgiou4:46 AM on 15 Mar 2011Aren't there int("1" + 50*"9") palindrome numbers less than a googol (10**100)?

Ram Rachum7:09 AM on 15 Mar 2011I'd go with an answer of 9 for the Google question, simply because it would have been hard for them to ask the question if the answer

wasn't9.pybarak7:15 AM on 15 Mar 20111. For google's question we can create a nice palindrom sum generator:

def palindrom_sums_generator(n):

i=0

while (i

pybarak7:27 AM on 15 Mar 20111. something like:

return [sum(map(lambda(x):int(x),list(str(x)))) for x in xrange(10**100) if palindrom(x)]

And the palindrom function returns true iff the number is palindrom:

def palindrom(x):

l1=list(str(x))

l2 = list(str(x))

l2.reverse()

return l1==l2

2. recursively it is defined as the Fibonacci series where F(n)=F(n-1)+F(n-2)

pybarak7:32 AM on 15 Mar 2011Sorry, for the first question here is the solution where counting the number of palindroms and then summing the digits of the count (it's almost the same):

return sum(list(str(len([x for x in xrange(10**100) if palindrom(x)])))

Ram Rachum7:35 AM on 15 Mar 2011Pybarak: I see you're not into that whole "checking if my code even runs before posting it" thing. Even if it did run I doubt it would finish in a reasonable time.

Ned Batchelder7:41 AM on 15 Mar 2011@ZeD: Why couldn't four steps be taken in two bounds, skipping a step each time?

@pybarak: I'm with Ram here: any solution involving iterating 10**100 times isn't really a solution!

Ned Batchelder7:42 AM on 15 Mar 2011@Ram: you're just *guessing* 9? Don't you think the number of palindromes under a googol would be very large? Possibly with more than 9 digits itself? How could the sum of those digits be 9?

Ram Rachum7:47 AM on 15 Mar 2011Oh, I confused "sum of digits" with "repeated digital sum".

Ned Batchelder8:00 AM on 15 Mar 2011@Ram: in that case, yours was a good (and correct!) guess.

pybarak11:11 AM on 15 Mar 2011Using some math one can show that the number of n-digit palindromes is 9*(10^(n/2-1)) when n is even and 9*(10^(n/2)) when n is odd. So the number we are looking for would be

The returned list should be filtered to remove the zero-prefixed elements9*100=900(9 for each additional digit, as the first number smaller than googol has 100 digits)Here is a more elegant (recursive) solution to create an n-digit palindrome:

@Ram: I actually ran this one on my laptop. Here is the output for palindromes of length 2 (I won't print 3 since there are 90 of them):

Christian Oudard11:52 AM on 15 Mar 2011I think I came up with the correct answer: 450. I don't see any other comments that mention it, though. Here's the code that gave me that answer:

https://gist.github.com/871017

Christos Georgiou12:01 PM on 15 Mar 2011Why do I get 451? Do you guys count 0 as a palindromic number or not?

Christian Oudard1:07 PM on 15 Mar 2011@christos, correct, I did not count 0 in my code. The problem was a bit ambiguous on this point.

Ned Batchelder1:45 PM on 15 Mar 2011The problem said, "count all the palindromes greater than zero and less than a googol"

Chris Pitzer8:35 PM on 15 Mar 2011You can't iterate to solve this, the numbers are too big. Luckily, the numbers are quite round, so it stays fairly terse.

We want a number less than half the length of 10**100, and we want it twice. Once we will duplicate it for the second half of the palindrome, and next we will duplicate it but pivot on the center character. This way we get palindromes of an even and odd number of characters.

palindromes = (10**50-1)*2

sum_of_digits = sum([int(x) for x in str(palindromes)])

Henrik Ravn3:35 AM on 17 Mar 2011Jeff Bradberry7:53 AM on 17 Mar 2011The sum of all palindromes up to 10**100 (in LaTeX math format) is:

$45 \(1 + \sum_{n=2}^{50} 10^{\lfloor \frac{n-1}{2} \rfloor} \(10^{n-1} + 10^{n-2} \)\)$

I leave it as an exercise for the student why this is so.

Jeff Bradberry12:02 PM on 17 Mar 2011Actually, n should be summed up to 100, not 50. Oops.

Brian Miller12:28 PM on 18 Mar 2011I am new to programming and am trying to figure out if the solution to the palindrome problem is a math question or a programming question, as far as Google point of view. I have confirmed the math solution by iterating 10**1 to 10**10, noting the pattern in the answers and extrapolating out the answer for 10**100. Is there a way to do the entire problem programmatically without the use of math type functions?

It would seem to me that if on average only about 6% of the numbers per **10 are palindromes, then it would be faster to generate all of the palindromes for the range and then add them. Is this correct if you were trying to solve it entirely with a program?

Eric Johnson12:10 PM on 16 Mar 2012Ancient Egyptians may have thought Pi was 256/81.

http://en.wikipedia.org/wiki/Approximations_of_%CF%80#Early_history

256/81 is about 3.16049382716049382716, which is approx 0.6 percent above the value of Pi. 22/7 is approx 0.04 percent less than Pi, so the ancient Egyptians weren't particularly accurate, but the numerator and denominator they choose are interesting for another reason.

256/81 can be expressed as 2^8 / 3^4, which can be expressed as 2^2^3/3^2^2, which of course is a palindrome.

Posted on A.E. Pi day, 2012 (A.E. = Ancient Egyptian)

## Add a comment: