Monday 14 March 2011 — This is almost 14 years old. Be careful.
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
[...]
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?
http://halftauday.com/
def palindrom_sums_generator(n):
i=0
while (i
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)
return sum(list(str(len([x for x in xrange(10**100) if palindrom(x)])))
@pybarak: I'm with Ram here: any solution involving iterating 10**100 times isn't really a solution!
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 retThe 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']https://gist.github.com/871017
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)])
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$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.
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?
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: