3. Nombres de Catalan (3,5 punts)

Els nombres de Catalan formen una seqüència de nombres naturals que apareix en diversos problemes de recompte que habitualment són recursius. Obtenen el seu nom del matemàtic belga Eugène Charles Catalan (1814-1894).

El terme general d’aquesta successió recursiva és:

\(c_0 = 1\)

\(c_n = \dfrac{2(2n-1)c_{n-1}}{n+1}\)

Per exemple, els quatre primers termes de la successió serien:

per \(\;\;n=0\qquad c_0 = 1\)

per \(\;\;n=1\qquad c_1 = \dfrac{2(2\cdot 1-1)\cdot 1}{1+1} = \dfrac{2}{2} = 1\)

per \(\;\;n=2\qquad c_2 = \dfrac{2(2\cdot 2-1)\cdot 1}{2+1} = \dfrac{6}{3} = 2\)

per \(\;\;n=3\qquad c_3 = \dfrac{2(2\cdot 3-1)\cdot 2}{3+1} = \dfrac{20}{4} = 5\)

Els primers termes són \(\;1,\, 1,\, 2,\, 5,\, 14,\, 42,\, 132,\, 429,\, 1430,\, 4862,\, 16796,\, 58786,\, \ldots\)

Dissenya la funció següent i desa-la al mòdul numcat (fitxer numcat.py).

succ_cat(u)

u és un ìnt d’un sol dígit (entre 0 i 9)

La funció retorna la llista dels termes generats fins que la suma dels dos últims [de la llista] acaba en u.

Per exemple:

>>> succ_cat(7)    # 2 + 5 = 7, que ACABA en 7
[1, 1, 2, 5]
>>> succ_cat(3)    # 1 + 2 = 3, que ACABA en 3
[1, 1, 2]
>>> succ_cat(4)    # 42 + 132 = 174, que ACABA en 4
[1, 1, 2, 5, 14, 42, 132]
>>> succ_cat(6)    # 14 + 42 = 56, que ACABA en 6
[1, 1, 2, 5, 14, 42]
>>> succ_cat(8)    # 4862 + 16796 = 21658, que ACABA en 8
[1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796]

Disposes de tests al fitxer test-numcat.txt.