[Edu-sig] Updating some more...
kirby urner
kirby.urner at gmail.com
Thu Jul 1 18:28:26 CEST 2010
Totally mind-boggling Gary.
Tracing through On-Line Dictionary of Integer Sequences I figured out
how to do it recursively, which might not be as much fun. For one
thing, it takes forever to run. I despair of ever reaching p(200) this way.
Major MacMahon rocks 'n rules (Hardy and Ramanujan too).
This song about Ramanujan's life is both funny and kinda sad:
http://www.archive.org/details/Ramanujan
(play control in upper right)
Kirby
>>> gen = a000041()
>>> [next(gen) for i in range(60)]
[1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231,
297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718,
4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015,
31185, 37338, 44583, 53174, 63261, 75175, 89134, 105558, 124754,
147273, 173525, 204226, 239943, 281589, 329931, 386155, 451276,
526823, 614154, 715220, 831820]
Here's the code:
def a000041():
gen = a137683()
while True:
yield sum(next(gen))
def pascal():
row = [1]
while True:
yield row
row = [i+j for i,j in zip(row + [0], [0] + row)]
def invpascal():
gen = pascal()
while True:
row = next(gen)
if len(row)%2:
yield [row[i]*pow(-1,i) for i in range(len(row))]
else:
yield [row[i]*pow(-1,i+1) for i in range(len(row))]
def a137683():
gen1 = invpascal()
gen2 = a026794()
n = 1
ipmatrix = [] # inverse pascal triangular matrix
while True:
ipmatrix.append(next(gen1))
result = []
row = next(gen2)
for i in range(n):
col = [0 for j in range(n)]
for k in range(i,n):
col[k] = ipmatrix[k][i]
result.append(sum([i * j for i,j in zip(row, col)]))
yield result
n += 1
def a026794():
n = 1
while True:
row = []
for k in range(1, n+1):
row.append(T(n,k))
yield row
n += 1
def T(n, k):
"""
T(n, k)=if(k<1|k>n, 0, if(n==k, 1, sum(i=k, n-k, T(n-k, i))))
"""
if k < 1 or k > n:
return 0
if n == k:
return 1
else:
return sum([T(n-k, i) for i in range(k, n-k+1)])
# bonus, not used
def a010054():
n = 0
incr = 0
tri = incr
while True:
if n == tri:
yield 1
incr += 1
tri = tri + incr
else:
yield 0
n += 1
On Wed, Jun 30, 2010 at 6:49 PM, Litvin <litvin at skylit.com> wrote:
> At 07:01 PM 6/30/2010, kirby urner wrote:
>
> I did something similar with a Ramanujan series converging to pi...
>
> Since you mentioned Ramanujan...
>
> He and Hardy worked quite a bit on the partition function: p(n) = the number
> of different ways n can be represented as a sum of positive integers. The
> sequence p(n) starts like Fibonacci numbers, 1, 1, 2, 3, 5... but the next
> one is 7. Nice try!
>
> At some point around 1916, an amature mathematician Major MacMahon, who was
> "good with numbers" calculated _by hand_ for Hardy and Ramanujan p(n) for n
> = 1 through 200. p(200) happens to be 3,972,999,029,388. An interesting
> story.
>
> It is possible, of course, to write a recursive function to calculate p(n),
> but a more fun way is to use the generating function (1 + x + x^2
> +x^3+...x^n)*(1+x^2+x^4+x^6+...)(1+x^3+x^6+...)*...*(1+x^n) (due to Euler,
> as most everything else...) When you distribute, the coefficients at x,
> x^2, ... of the resulting polynomial give you p(1), p(2), ... So this could
> be a basis for a meaningful project on lists and polynomials.
>
> If you plug a large enough number into the generating function, say, x =
> 10000, you get a number whose groups of five digits (from the right) give
> you p(n) as long as p(n) < 10000. So for a relatively small n instead of
> multiplying polynomials you can multiply "periodic" integers
> 100010001...0001*100000001...00000001*...
> It is easy, of course, to generate these numbers using strings. Then this
> becomes a meaningful exercise on strings.
>
> I am currently working on a "test package" for the Math and Python book and
> I've just added a question based on a small peace of this, so I felt like
> sharing. Not sure whether this is for the left brain or for the right
> brain; these periodic strings are kinda cute. :)
>
> Gary Litvin
> www.skylit.com
>
More information about the Edu-sig
mailing list