trovare la sequenza collatz più bassa che dà più di 65 numeri primi

Question

Ho un compito in cui ho bisogno di trovare la sequenza Collatz più bassa che contiene più di 65 numeri primi in Python.

Ad esempio, la sequenza di Collatz per 19 è:

19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Questa sequenza contiene 7 numeri primi.

Devo anche usare la memoizzazione in modo da non dover eseguire un "anno" per trovarlo. Ho trovato il codice per la memoizzazione delle sequenze di Collatz, ma non riesco a capire come farlo funzionare quando ho bisogno solo dei numeri primi.

Ecco il codice Memoizzazione Collatz che ho trovato:

lookup = {} 
def countTerms(n): 
    if n not in lookup: 
     if n == 1: 
      lookup[n] = 1 
     elif not n % 2: 
      lookup[n] = countTerms(n/2)[0] + 1 
     else: 
      lookup[n] = countTerms(n*3 + 1)[0] + 1 

    return lookup[n], n 

Ed ecco il mio tester per primo:

def is_prime(a): 
    for i in xrange(2,a): 
     if a%i==0: 
      #print a, " is not a prime number" 
      return False 
    if a==1: 
     return False 
    else: 
     return True 

Answer 1

il codice esistente è in modo non corretto frastagliata. Presumo che questa attività sia un'attività di compiti a casa, quindi non invierò una soluzione di lavoro completa, ma ti fornirò alcuni frammenti utili.

Per prima cosa, ecco un tester di primalità leggermente più efficiente. Piuttosto che testare se tutti i numeri inferiori a a sono fattori di a, si verifica semplicemente fino alla radice quadrata di a.

def is_prime(a): 
    for i in xrange(2, int(1 + a ** 0.5)): 
     if a % i == 0: 
      return False 
    return True 

Si noti che questa funzione restituisce True per a = 1. Va bene, dal momento che non c'è bisogno di test 1: è possibile pre-caricarlo nella lookup dict:

lookup = {1:0} 

La vostra funzione countTerms deve essere modificata leggermente in modo che si aggiunge un solo al conteggio lookup quando l'attuale n è primo. In Python, False ha un valore numerico di 0 e True ha un valore numerico di 1. Questo è molto utile qui:

def count_prime_terms(n): 
    ''' Count the number of primes terms in a Collatz sequence ''' 
    if n not in lookup: 
     if n % 2: 
      next_n = n * 3 + 1 
     else: 
      next_n = n // 2 

     lookup[n] = count_prime_terms(next_n) + is_prime(n) 
    return lookup[n] 

ho cambiato il nome della funzione di essere più Pythonic.

FWIW, la prima sequenza di Collatz contenente 65 o più numeri primi contiene in realtà 67 numeri primi. Il suo numero di seme è superiore a 1,8 milioni e il numero più alto che richiede il test di primalità quando si controllano tutte le sequenze fino a quel seme è 151629574372. Al completamento, il dict lookup contiene 3920492 voci.

---

In risposta ai commenti di James Mills per quanto riguarda la ricorsione, ho scritto una versione non ricorsiva, e per rendere più facile vedere che il iterativo e le versioni ricorsive entrambi producono gli stessi risultati che sto postando un completo programma di lavoro. Ho detto sopra che non avevo intenzione di farlo, ma immagino che dovrebbe essere ok ora, dato che spørreren ha già scritto il loro programma usando le informazioni che ho fornito nella mia risposta originale.

Concordo pienamente sul fatto che sia opportuno evitare la ricorsione tranne che nelle situazioni in cui è appropriato al dominio del problema (ad es. Attraversamento di alberi). Python scoraggia la ricorsione - non può ottimizzare la ricorsione coda-chiamata e impone un limite di profondità di ricorsione (sebbene tale limite possa essere modificato, se lo si desidera).

Questo algoritmo di conteggio primo sequenza sequenza Collatz è naturalmente affermato in modo ricorsivo, ma non è troppo difficile da fare iterativamente - abbiamo solo bisogno di un elenco per tenere temporaneamente la sequenza mentre viene determinata la primalità di tutti i suoi membri. È vero, questo elenco occupa la RAM, ma è (probabilmente) molto più efficiente in termini di spazio rispetto ai requisiti dello stack frame richiesti dalla versione ricorsiva.

La versione ricorsiva raggiunge una profondità di ricorsione di 343 quando si risolve il problema nell'OP. Questo è ben all'interno del limite di default ma non è ancora buono, e se vuoi cercare sequenze contenenti un numero molto maggiore di numeri primi, colpirai quel limite.

L'iterativo delle versioni ricorsive & esegue all'incirca la stessa velocità (almeno, lo fanno sulla mia macchina). Per risolvere il problema indicato nell'OP, entrambi richiedono poco meno di 2 minuti. Questo è significativamente più veloce della mia soluzione originale, principalmente a causa delle ottimizzazioni nei test di primalità.

La fase di generazione della sequenza Collatz di base deve già determinare se un numero è pari o dispari. Chiaramente, se già sappiamo che un numero è pari, non è necessario testare se è un numero primo. :) E possiamo anche eliminare i test per fattori pari nella funzione is_prime. Possiamo gestire il fatto che 2 è primo semplicemente caricando il risultato per 2 nella cache lookup.

Su una nota correlata, quando si cerca la prima sequenza contenente un numero determinato di numeri primi non è necessario testare nessuna delle sequenze che iniziano con un numero pari. Anche i numeri (a parte 2) non aumentano il numero primo di una sequenza e poiché il primo numero dispari in tale sequenza sarà inferiore al numero corrente, i suoi risultati saranno già nella cache lookup, supponendo che iniziamo la nostra ricerca da 3. E se non iniziamo la ricerca da 3, dobbiamo solo assicurarci che il nostro seme iniziale sia abbastanza basso da non perdere per errore la prima sequenza contenente il numero desiderato di numeri primi. L'adozione di questa strategia non solo riduce il tempo necessario, ma riduce anche il numero di voci nella cache di ricerca.

#!/usr/bin/env python 

''' Find the 1st Collatz sequence containing a given number of prime terms 

    From http://stackoverflow.com/q/29920691/4014959 

    Written by PM 2Ring 2015.04.29 

    [Seed == 1805311, prime count == 67] 
''' 

import sys 

def is_prime(a): 
    ''' Test if odd `a` >= 3 is prime ''' 
    for i in xrange(3, int(1 + a ** 0.5), 2): 
     if not a % i: 
      return 0 
    return 1 


#Track the highest number generated so far; use a list 
# so we don't have to declare it as global... 
hi = [2] 

#Cache for sequence prime counts. The key is the sequence seed, 
# the value is the number of primes in that sequence. 
lookup = {1:0, 2:1} 

def count_prime_terms_iterative(n): 
    ''' Count the number of primes terms in a Collatz sequence 
     Iterative version ''' 
    seq = [] 
    while n not in lookup: 
     if n > hi[0]: 
      hi[0] = n 

     if n % 2: 
      seq.append((n, is_prime(n))) 
      n = n * 3 + 1 
     else: 
      seq.append((n, 0)) 
      n = n // 2 

    count = lookup[n] 
    for n, isprime in reversed(seq): 
     count += isprime 
     lookup[n] = count 

    return count 

def count_prime_terms_recursive(n): 
    ''' Count the number of primes terms in a Collatz sequence 
     Recursive version ''' 
    if n not in lookup: 
     if n > hi[0]: 
      hi[0] = n 

     if n % 2: 
      next_n = n * 3 + 1 
      isprime = is_prime(n) 
     else: 
      next_n = n // 2 
      isprime = 0 
     lookup[n] = count_prime_terms(next_n) + isprime 

    return lookup[n] 


def find_seed(numprimes, start): 
    ''' Find the seed of the 1st Collatz sequence containing 
     `numprimes` primes, starting from odd seed `start` ''' 
    i = start 
    mcount = 0 

    print 'seed, prime count, highest term, dict size' 
    while mcount < numprimes: 
     count = count_prime_terms(i) 
     if count > mcount: 
      mcount = count 
      print i, count, hi[0], len(lookup) 
     i += 2 


#count_prime_terms = count_prime_terms_recursive 
count_prime_terms = count_prime_terms_iterative 

def main(): 
    if len(sys.argv) > 1: 
     numprimes = int(sys.argv[1]) 
    else: 
     print 'Usage: %s numprimes [start]' % sys.argv[0] 
     exit() 

    start = int(sys.argv[2]) if len(sys.argv) > 2 else 3 

    #Round `start` up to the next odd number 
    if start % 2 == 0: 
     start += 1 

    find_seed(numprimes, start) 


if __name__ == '__main__': 
    main() 

Quando viene eseguito con

$ ./CollatzPrimes.py 65

l'uscita è

seed, prime count, highest term, dict size 
3 3 16 8 
7 6 52 18 
19 7 160 35 
27 25 9232 136 
97 26 9232 230 
171 28 9232 354 
231 29 9232 459 
487 30 39364 933 
763 32 250504 1626 
1071 36 250504 2197 
4011 37 1276936 8009 
6171 43 8153620 12297 
10971 44 27114424 21969 
17647 48 27114424 35232 
47059 50 121012864 94058 
99151 51 1570824736 198927 
117511 52 2482111348 235686 
202471 53 17202377752 405273 
260847 55 17202377752 522704 
481959 59 24648077896 966011 
963919 61 56991483520 1929199 
1564063 62 151629574372 3136009 
1805311 67 151629574372 3619607 

Answer 2

Iniziamo con una funzione che determina se un numero è primo; useremo l'algoritmo di Miller-Rabin, che è più veloce di divisione di prova per la dimensione di numeri che avremo a che fare con:

from random import randint 

def isPrime(n, k=5): # miller-rabin 
    if n < 2: return False 
    for p in [2,3,5,7,11,13,17,19,23,29]: 
     if n % p == 0: return n == p 
    s, d = 0, n-1 
    while d % 2 == 0: 
     s, d = s+1, d/2 
    for i in range(k): 
     x = pow(randint(2, n-1), d, n) 
     if x == 1 or x == n-1: continue 
     for r in range(1, s): 
      x = (x * x) % n 
      if x == 1: return False 
      if x == n-1: break 
     else: return False 
    return True 

Dal momento che vogliamo trovare la prima numero che soddisfa i criteri, il nostro la strategia sarà di partire da 2 e risalire, archiviando i risultati man mano che procediamo. Abbiamo innescare la cache (che è un brutto gioco di parole, sorry) con i conteggi prime nelle sequenze Collatz da 0 a 2:

primeCount = [0,0,1] 

Funzione pCount(n) conta i numeri primi nella sequenza Collatz per n.Non appena il valore corrente della sequenza k scende sotto n, cerchiamo il risultato nella cache. Fino ad allora, testiamo ogni numero dispari nella sequenza di Collatz per la primalità e incrementiamo il conteggio dei numeri primi p se appropriato. Quando abbiamo il numero primo per n, lo aggiungiamo alla cache e lo restituiamo.

def pCount(n): 
    k, p = n, 0 
    while k > 0: 
     if k < n: 
      t = p + primeCount[k] 
      primeCount.append(t) 
      return t 
     elif k % 2 == 0: 
      k = k/2 
     elif isPrime(k): 
      p = p + 1 
      k = 3*k + 1 
     else: 
      k = 3*k + 1 

ora è solo una questione di calcolo dei conteggi primari per ogni n, in ordine partendo da 3, fermandosi quando il conteggio primo supera il 65:

n = 3 
t = pCount(n) 
while t < 65: 
    n = n + 1 
    t = pCount(n) 

che non ci vuole molto , meno di un minuto sul mio computer. Ecco il risultato:

print n 

Ci sono 67 numeri primi nel risultato. Se volete vederli, ecco una semplice funzione che stampa la sequenza di Collatz per un dato n:

def collatz(n): 
    cs = [] 
    while n != 1: 
     cs.append(n) 
     n = 3*n+1 if n&1 else n//2 
    cs.append(1) 
    return cs 

Ed ecco l'elenco dei numeri primi:

filter(isPrime,collatz(n)) 

Che un problema in giro matematica ricreativa!

EDIT: Poiché la gente ha chiesto del tester di primalità di Miller-Rabin, lascia che mostri questo semplice tester di primalità basato su una ruota da 2,3,5; fa la divisione di prova per 2, 3 e 5 e per numeri che non sono multipli di 2, 3 o 5, che include alcuni materiali compositi, quindi è un po 'meno efficiente della divisione di prova per primi, ma non è necessario pre-calcolare e memorizzare i numeri primi, quindi è molto più facile da usare.

def isPrime(n): # 2,3,5-wheel 
    if n < 2: return False 
    wheel = [1,2,2,4,2,4,2,4,6,2,6] 
    w, next = 2, 0 
    while w * w <= n: 
     if n % w == 0: return False 
     w = w + wheel[next] 
     next = next + 1 
     if next > 10: next = 3 
    return True 

Dire filter(isPrime,range(1000000)) identifica le 78498 primi minori di un milione nel giro di pochi secondi. Potresti voler confrontare le tempistiche per questo tester di primalità rispetto al tester Miller-Rabin e determinare dove si trova il punto di crossover in termini di efficienza di runtime; Non ho fatto nessun orario formale, ma sembra che risolva il problema del 65-collatz-prime più o meno nello stesso periodo del tesetere Miller-Rabin. Oppure si potrebbe voler combinare la divisione di prova con una ruota da 2,3,5 fino ad un certo limite, diciamo 1000 o 10000 o 25000, quindi eseguire Miller-Rabin sui sopravvissuti; che elimina rapidamente la maggior parte dei materiali compositi, quindi può essere eseguito molto rapidamente.