# Recurrent definiton of a function

Hi, I am trying to compose a code for calculating the numbers H01 defined as a sum of the following recursively defined numbers:

H11(r) = \sum_{a + b = r}  a*b/r  (H11(a) + H12(a)) * H11(b)
H12(r) = \sum_{a + b = r}  a*b/r  (H11(a) + H12(a)) * (H11(b) + H12(b))

H01(r) = H11(r) + H12(r)


I ended up with the following code:

memoH11 = {1:0, 2:1/2}
def H11(r1):
if memoH11.has_key(r1):
return memoH11[r1]
else:
a = 0
for j1 in range(1,r1):
a += j1*(r1 - j1)/r1 * (H11(j1) + H12(j1)) * H11(r1-j1)
memoH11[r1] = a
return a

memoH12 = {1:0, 2:0}
def H12(r2):
if memoH12.has_key(r2):
return memoH12[r2]
else:
b = 0
for j2 in range(1,r2):
b += j2*(r2 - j2)/r2 * ( H11(j2) + H12(j2) ) * ( H11(r2 - j2) + H12(r2-j2) )
memoH12[r2] = b
return b

def H01(r):
return H11(r) + H12(r)


And here problems start. If I just type

H01(8)


it produces the incorrect value 27/8. But if I type

H01(6), H01(8)


it results the correct tuple (7/6, 15/4).

So how to fix the code ? Thanks in advance for any help.

edit retag close merge delete

What are you trying to do!? You should explain it clearly and not only show your (wrong) functions. How should we guess!?

@vdelecroix, Thanks, I should have stated the problem more explicitly. I've added the setup to the question.

Sort by » oldest newest most voted

First of all, Sage has a great feature for caching output of functions

@cached_function
def fibo(n):
if n == 0:
return 0
if n == 1:
return 1
return fibo(n-1) + fibo(n-2)


Then you can call fibo with quite high values and result is automatically cached for you!

sage: fibo(20)
6765


If you use it you will get a simpler code.

Next, be careful that dividing Python ints is different than dividing Sage integers:

sage: for i in range(10): print i / int(3),
0 0 0 1 1 1 2 2 2 3
sage: for i in range(10): print i / 3
0 1/3 2/3 1 4/3 5/3 2 7/3 8/3 3


In particular, in your loops you are dividing Python integers with Python integers (range generates Python integers). Hence you are doing integer divisions. You can either convert explicitely the input at the begining of each function

def H11(r1):
r1 = ZZ(r1)
....


or use srange instead of range

sage: map(type, range(4))
[<type 'int'>, <type 'int'>, <type 'int'>, <type 'int'>]
sage: map(type, srange(4))
[<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>,
<type 'sage.rings.integer.Integer'>]


I hope it is clear enough.

Vincent

more

def H11(r1):
r1 = ZZ(r1)
....


resolved the problem. Thanks a lot!