Avís

Per a resoldre aquest exercici no es poden fer servir iteracions (ni for ni while ), només funcions recursives.

Calamarsa

Considerem la següent operació sobre qualsevol nombre natural arbitrari:

• Si el nombre és parell, el dividim per dos.

• Si el nombre és senar, el tripliquem i li afegim una unitat.

Si aquesta operació la fem repetidament a partir d’un nombre natural, genera una seqüència de nombres naturals infinita que acaba passant pel valor 1, a partir del qual, la seqüència es fa infinita repetint la subseqüència \(4, 2, 1\). Aquesta darrera afirmació s’anomena la conjectura de Collatz, doncs no s’ha pogut demostrar matemàticament. Com que la seqüència puja i baixa de valors de manera semblant a com cau la calamarsa, l’anomenarem calamarsa.

En el fitxer calamarsa.py dissenyeu la funció recursiva:

calamarsa.calamarsa(n)

A partir d’un nombre natural \(n>0\), genera una llista de la seqüència \(n_0,n_1,n_2,\ldots,1\) on \(n_0=n\), i per \(i>0\), cada valor \(n_i\) es determina fent el següent càlcul:

\[\begin{split}n_i = \begin{cases} n_{i-1}/2 &\text{si } n_{i-1} \text{ és parell}\\ 3n_{i-1}+1 & \text{si } n_{i-1} \text{ és senar } \end{cases} \quad\forall i>0\end{split}\]

La generació de la llista acaba quan trobem un \(n_i\) tal que \(n_i=1\)

Per exemple,

>>> from calamarsa import calamarsa
>>> calamarsa(4)
[4, 2, 1]
>>> calamarsa(1)
[1]
>>> calamarsa(10)
[10, 5, 16, 8, 4, 2, 1]
>>> calamarsa(13)
[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]

Nota

Disposeu de jocs de prova al fitxer test-calamarsa.txt i d’una solució a calamarsa.py