MicroPython Forum (Archive)

Posted: **Tue Apr 27, 2021 4:08 pm**

Today I stumbled over this identity for Catalan numbers:
https://oeis.org/A000108

C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009

Normally I use "bc" tool for arbitrary precision calculations, but realized that MicroPython allows for that as well. And I wanted to learn on (Micro)Python's lambda functions. Since functools module seems not available for MicroPython, I created my own "apply(range,func)" function (concatenation of tuples):

Code: Select all

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R

These are the basic "bin(n,k)" and "C(n)" functions I used:

Code: Select all

def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)

This code computed part of above identity the imperative way:

Code: Select all

def sigma(p,q):
    s=0
    for i in range(p):
        for j in range(q):
            s+=C(i)*C(j)*C(p+q-i-j-1)
    return s

print(sigma(11,11))

It took me a while to correctly uise lamda and sum functions to compute same value -- the "sum(apply(..." looks more like mathematical "Sum_{...}...":

Code: Select all

def siglam(p,q):
    return sum(apply(range(p),
                     lambda i: sum(apply(range(q),
                                         lambda j: C(i)*C(j)*C(p+q-i-j-1)
                                        )
                                  )
                    )
              )

print(siglam(11,11))

Finally I wanted to check that identity is valid, but stack size limited what is possible. Anyway the "tst()" function allows for nice way to pass lambda functions with two arguments. Boolean values False/True are converted to 0/1 by "sum()" function. So overall sum returning 0 means that all (negative) identities tested are valid:

Code: Select all

def tst(n, f):
    return sum(apply(range(n+1),
                     lambda p: sum(apply(range(p+1),
                                         lambda q: f(p,q)
                                        )
                                  )
                    )
              )

print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")

The last line tells the number of tests done in total:

Code: Select all

>>> 
MPY: soft reboot
MicroPython v1.14 on 2021-04-13; Raspberry Pi Pico with RP2040
Type "help()" for more information.                                            
>>> import catalan                                                             
88026769844                                                                    
88026769844                                                                    
0                                                                              
0                                                                              
[bin(9+1,2)=45]                                                                
>>>

Finaly this is complete "catalan.py":

Code: Select all

def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R

def sigma(p,q):
    s=0
    for i in range(p):
        for j in range(q):
            s+=C(i)*C(j)*C(p+q-i-j-1)
    return s

print(sigma(11,11))

def siglam(p,q):
    return sum(apply(range(p),
                     lambda i: sum(apply(range(q),
                                         lambda j: C(i)*C(j)*C(p+q-i-j-1)
                                        )
                                  )
                    )
              )

print(siglam(11,11))

def tst(n, f):
    return sum(apply(range(n+1),
                     lambda p: sum(apply(range(p+1),
                                         lambda q: f(p,q)
                                        )
                                  )
                    )
              )

print(tst(8, lambda p,q: siglam(p,q) != sigma(p,q)))
print(tst(8, lambda p,q: C(p+q)-C(p)*C(q) != sigma(p,q)))
print("[bin(9+1,2)="+str(tst(8, lambda p,q: 1))+"]")

Posted: **Thu Apr 29, 2021 4:38 pm**

Cosmetics, easier to read, does not use that much space horizontally, equivalent to previous code:

Code: Select all

def siglam(p,q):
    return sum(apply(range(p), lambda i:
               sum(apply(range(q), lambda j:
                   C(i)*C(j)*C(p+q-i-j-1)
               ))
           ))

Posted: **Fri Apr 30, 2021 1:41 pm**

This is more clean:

Code: Select all

def siglam(p,q):
    return (apply(range(p), lambda i:
                (apply(range(q), lambda j:
                    C(i)*C(j)*C(p+q-i-j-1)
                ))
           ))

Returns nested tuples

Code: Select all

>>> catalan.siglam2(3,2)                                                       
((14, 5), (5, 2), (4, 2))                                                      
>>>

which "sum()" cannot handle -- but "sumit()" can:

Code: Select all

def sumit(t):
    return t if isinstance(t, (int,float)) \
      else 0 if len(t)==0                  \
      else sumit(t[0])+sumit(t[1:])

Code: Select all

>>> catalan.sumit(catalan.siglam2(3,2))                                        
32                                                                             
>>>

"sumit()" can deal with integers and floats, and with nested tuples and lists:

Code: Select all

>>> catalan.sumit([1, (2, 3), [4, 5.6], ([7, 8, 9, 10], 11)])                  
60.6                                                                           
>>>

"mulit()" can simply be defined if needed for mathematical product of terms.

Code: Select all

$ cat catalan.py
def bin(n,k):
    return 1 if k<=0 else bin(n-1,k-1) * n // k

def C(n):
    return bin(2*n,n) // (n+1)

def apply(r,f):
    R=()
    for i in r:
        R += f(i),
    return R

def sumit(t):
    return t if isinstance(t, (int,float)) \
      else 0 if len(t)==0                  \
      else sumit(t[0])+sumit(t[1:])

def siglam2(p,q):
    return (apply(range(p), lambda i:
                (apply(range(q), lambda j:
                    C(i)*C(j)*C(p+q-i-j-1)
                ))
           ))

print(sumit(siglam2(3,2)))
print(siglam2(3,2))
$

MicroPython Forum (Archive)

lambda, apply, arbitrary precision

lambda, apply, arbitrary precision

Re: lambda, apply, arbitrary precision

Re: lambda, apply, arbitrary precision