Two Pi Day puzzles from PyCon

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 (10100)? 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

[gravatar]
ZeD 12:11 AM on 15 Mar 2011

You can't skip more than one step at a time.
[...]
4 steps could be tttt, ttk, tkt, ktt, or kk


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

[gravatar]
johannes 1:36 AM on 15 Mar 2011

You mean Half Tau Day?
http://halftauday.com/

[gravatar]
Christos Georgiou 4:46 AM on 15 Mar 2011

Aren't there int("1" + 50*"9") palindrome numbers less than a googol (10**100)?

[gravatar]
Ram Rachum 7:09 AM on 15 Mar 2011

I'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't 9.

[gravatar]
pybarak 7:15 AM on 15 Mar 2011

1. For google's question we can create a nice palindrom sum generator:
def palindrom_sums_generator(n):
i=0
while (i

[gravatar]
pybarak 7:27 AM on 15 Mar 2011

1. 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)

[gravatar]
pybarak 7:32 AM on 15 Mar 2011

Sorry, 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)])))

[gravatar]
Ram Rachum 7:35 AM on 15 Mar 2011

Pybarak: 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.

[gravatar]
Ned Batchelder 7: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!

[gravatar]
Ned Batchelder 7: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?

[gravatar]
Ram Rachum 7:47 AM on 15 Mar 2011

Oh, I confused "sum of digits" with "repeated digital sum".

[gravatar]
Ned Batchelder 8:00 AM on 15 Mar 2011

@Ram: in that case, yours was a good (and correct!) guess.

[gravatar]
pybarak 11:11 AM on 15 Mar 2011

Using 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 9*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:

def get_palindromes(n):
    if (n==0):
        return ['']
    if (n==1):
        return [str(i) for i in range(10)]
    else:
        p=get_palindromes(n-2)
        ret=[]
        for i in range(10):
            l=[str(i)+x+str(i) for x in p]
            ret+=l
        return ret
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):
>print [x for x in get_palindromes(2) if not x.startswith('0')]
>['11', '22', '33', '44', '55', '66', '77', '88', '99']

[gravatar]
Christian Oudard 11:52 AM on 15 Mar 2011

I 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

[gravatar]
Christos Georgiou 12:01 PM on 15 Mar 2011

Why do I get 451? Do you guys count 0 as a palindromic number or not?

[gravatar]
Christian Oudard 1: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.

[gravatar]
Ned Batchelder 1:45 PM on 15 Mar 2011

The problem said, "count all the palindromes greater than zero and less than a googol"

[gravatar]
Chris Pitzer 8:35 PM on 15 Mar 2011

You 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)])

[gravatar]
Henrik Ravn 3:35 AM on 17 Mar 2011

def sum_of_palindrome_count(maxd):
    """
    Return the digital sum of the number of palindromes in the range [1..10**maxd)
    """
    # We don't have to calculate the actual palindrome count, because the
    # the count is always of the form 1{0}9998, where the number of 9's 
    # is one less than half of maxd and the 0 is only present when maxd is odd
    if maxd == 1: return 9
    return (maxd//2 - 1) * 9 + 9
 

[gravatar]
Jeff Bradberry 7:53 AM on 17 Mar 2011

The 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.

[gravatar]
Jeff Bradberry 12:02 PM on 17 Mar 2011

Actually, n should be summed up to 100, not 50. Oops.

[gravatar]
Brian Miller 12:28 PM on 18 Mar 2011

I 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?

[gravatar]
Eric Johnson 12:10 PM on 16 Mar 2012

Ancient 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:

name
email
Ignore this:
not displayed and no spam.
Leave this empty:
www
not searched.
 
Name and either email or www are required.
Don't put anything here:
Leave this empty:
URLs auto-link and some tags are allowed: <a><b><i><p><br><pre>.