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 2011http://halftauday.com/

Christos Georgiou4:46 AM on 15 Mar 2011Ram Rachum7:09 AM on 15 Mar 2011wasn't9.pybarak7:15 AM on 15 Mar 2011def palindrom_sums_generator(n):

i=0

while (i

pybarak7:27 AM on 15 Mar 2011return [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 2011return sum(list(str(len([x for x in xrange(10**100) if palindrom(x)])))

Ram Rachum7:35 AM on 15 Mar 2011Ned Batchelder7:41 AM on 15 Mar 2011@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 2011Ram Rachum7:47 AM on 15 Mar 2011Ned Batchelder8:00 AM on 15 Mar 2011pybarak11:11 AM on 15 Mar 20119*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: The returned list should be filtered to remove the zero-prefixed elements

@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 2011https://gist.github.com/871017

Christos Georgiou12:01 PM on 15 Mar 2011Christian Oudard1:07 PM on 15 Mar 2011Ned Batchelder1:45 PM on 15 Mar 2011Chris Pitzer8:35 PM on 15 Mar 2011We 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 2011$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 2011Brian Miller12:28 PM on 18 Mar 2011It 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 2012http://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: