Generadors de Collatz P61669

Sigui n qualsevol natural estrictament positiu. Considereu el procés següent: Si n és parell, dividiu-lo per dos. Altrament, multipliqueu-lo per 3 i sumeu-li 1. Quan arribeu a 1, pareu. Per exemple, començant en 3, s’obté la seqüència de Collatz S(3):

Des de l’any 1937 es conjectura que aquest procés acaba per a qualsevol n inicial, encara que no ho ha sabut demostrar ningú. En aquest problema suposarem que la conjectura és certa.

1. Escriviu una funció
   def collatz (n: int) -> Iterator[int]

   que, donat un natural n≥ 1, generi la seqüència de Collatz S(n).

2. Escriviu una funció
   def collatz_length (n: int) -> int

   que, donat un natural n≥ 1, retorni la llargada d’S(n).

3. Escriviu una funció
   def collatz_highest (n: int) -> int

   que, donat un natural n≥ 1, retorni l’element més alt d’S(n).

4. Escriviu una funció
   def collatz_highest_position (n: int) -> tuple[int, int]

   que, donat un natural n≥1, retorni una tupla amb la posició de l’element més alt d’S(n) i el seu valor. Les posicions es comencen a comptar des de zero.

5. Escriviu una funció
   def collatz_11(int) -> bool

   que, donat un natural n≥1, indiqui si S(n) conté algún múltiple de 11 (excepte en la primera posició).

6. Escriviu una funció
   def collatz_first_common (n1: int, n2: int) -> int

   que, donats dos naturals n₁,n₂≥1, retorni el primer element comú d’S(n₁) i S(n₂).

7. Escriviu una funció
   def collatz_common_elements (n1: int, n2: int) -> int

   que, donats dos naturals n₁,n₂≥1, retorni el nombre d’elements comuns en S(n₁) i S(n₂).

8. Escriviu una funció
   def collatz_union (n1: int, n2: int) -> list[int]

   que, donats dos naturals n₁,n₂≥1, retorni tots els elements d’S(n₁) i S(n₂) en ordre estrictament creixent.

9. Escriviu una funció
   def collatz_top_numbers() -> Iterator[int]

   que generi la llista infinita de valors inicials pels quals el seu element més alt és més gran que qualsevol dels valors inicials menors Altrament dit, es vol la seqüència des­crita per [i ∣ maxS(i) > maxS(j) ∀ j < i].

10. Escriviu una funció
    def collatz_first_missing(n: int) -> int

    que, donat un natural n≥1, retorni el natural no nul més petit que no pertany a S(n).

Observacions

• Implementeu totes les funcions de forma senzilla, clara i concisa treient profit de Python.
• Descarregueu-vos el fitxer code.py. El programa principal i l’esquelet de les funcions ja se us dóna implementat.
• El Jutge dóna puntuacions parcials per a cada apartat, però l’avaluació va a càrrec del professor.