Nombres primers

Avís

Per a resoldre aquest exercici no es poden fer servir llistes, tuples, diccionaris ni cap altra estructura de dades per a desar tots els elements dels iterables.

S’està estudiant el funcionament i propietats de generadors de nombres primers. A tal efecte, s’estudia una fórmula recursiva que presentem a continuació

(1)\[a_{n}=a_{n-1}+\gcd(n,a_{n-1}),\quad a_{1}=7, n\ge 1\]

On gcd és una funció que retorna el màxim comú divisor. S’ha demostrat que a partir de la dada inicial \(a_{1}=7\), la seqüència infinita \(b_1b_2b_3\ldots\):

(2)\[\quad b_1=a_1,\quad b_i=a_i-a_{i-1},\quad i>1\]

només genera nombres primers senars (és a dir, el 2 no surt mai).

Deseu els següents generadors en el fitxer primers.py

1. Implementeu la funció generadora següent:

   primers.primers()

   que genera la seqüència infinita de nombres enters \(b_i\) definida a l’equació (2).

   Per exemple,

   
   >>> it = primers()
   >>> for i in range(30):
   ...      print(next(it), end='-')
   7-1-1-1-5-3-1-1-1-1-11-3-1-1-1-1-1-1-1-1-1-1-23-3-1-1-1-1-1-1-
   
   
   

   Nota

   Disposeu de jocs de proves al fitxer test-primers.txt Podeu trobar la funció gdc al mòdul math

2. Com que l’anterior seqüència genera excessius uns, dissenyeu la funció:

   primers.sense_uns(it)

   que a partir d’un iterador d’enters torna un altre iterador que dona qualsevol valor enter d”it excepte si el valor en qüestió és 1.

   Per exemple,

   
   >>> seq = iter([1,2,3,1,1,11,12,12,1,1,1,45,67,1,1,1,1,44,45,67,89,2,1,1,1,1,1])
   >>> it = sense_uns(seq)
   >>> for i in range(12):
   ...      print(next(it), end='-')
   2-3-11-12-12-45-67-44-45-67-89-2-
   
   >>> it = sense_uns(primers())
   >>> for i in range(20):
   ...      print(next(it), end='-')
   7-5-3-11-3-23-3-47-3-5-3-101-3-7-11-3-13-233-3-467-
   
   
   

   Nota

   Disposeu de jocs de proves al fitxer test-sense_uns.txt

3. Finalment, feu la funció:

   primers.n_uns(it)

   que a partir d’un iterador d’enters genera una seqüència de les longituds de seqüències d’uns contigus presents en it.

   Per exemple,

   
   >>> seq = iter([1,2,3,1,1,11,12,12,1,1,1,45,67,1,1,1,1,44,45,67,89,2,1,1,1,1,1])
   >>> it = n_uns(seq)
   
   >>> list(it)
   [1, 2, 3, 4, 5]
   
   >>> it = n_uns(primers())
   >>> for i in range(20):
   ...      print(next(it), end='-')
   3-4-10-22-1-49-2-4-5-115-232-1-469-2-943-1888-3778-5-7564-25-
   
   
   

   Nota

   Disposeu de jocs de proves al fitxer test-n_uns.txt

Solució

Disposeu d’una solució al fitxer primers.py.