La congettura di poteri di Eulero congettura. Come cercare in modo efficiente controesempi?

Perché non leggere l'articolo di Frye? Ecco un riassunto. Hai bisogno dell'aritmetica modulare per setacciare i candidati. Mod 5 funziona come il fascino (200 volte la riduzione dello spazio di ricerca). Devi dividerlo in A ^ 4 + B ^ 4 e D ^ 4-C ^ 4. Il programma stesso è scritto in Lisp.

L'implementazione è ragionevolmente semplice, mentre la matematica sottostante è accurata. Primo: setaccia alcuni numeri usando l'aritmetica modulare. Quindi studia A ^ 4 + B ^ 4 e D ^ 4 - C ^ 4 trasformando il problema in O (n ^ 2)

In primo luogo, osserva che il mod 5 è molto restrittivo.

A A ^ 4 A ^ 4 mod 5
0 0 0
1 1 1 2 16 1
3 81 1
4 256 1

Quindi, un controesempio deve soddisfare questi due requisiti:
Un mod 5 = B mod 5 = 0 // A e B sono divisibili per 5
C ^ 4 mod 5 = D ^ 4 mod 5 = 1 // il promemoria della divisione è 1

Si noti che D è il numero più grande e non è divisibile per 5, C non è divisibile per 5. A < B, A e B sono divisibili per 5. Questo riduce il numero di coppie possibili di un fattore di 200. D deve essere dispari usando considerazioni simili per il mod 4.

Il Mod 9 produce solo 4 biquadratici che producono 6 congruenze di interesse. Otterrai 1,7 miglioramenti da mod 9; 1.4 miglioramento da mod 13; 1,4 miglioramento da 29.

Se D e C hanno un fattore primo comune F allora ((A F) ^ 4 + (B F) ^ 4 può essere eliminato (è stato trattato prima). L'impatto è piccolo, ma aiuta, tuttavia.

Setacciare D ^ 4-C ^ 4 è meno efficiente, ma possiamo ancora fare certe cose. Per prima cosa, possiamo dividerlo per 625 prima della decomposizione. Sia N il numero da scomporre. Il secondo vincolo è limitare A, B

// Ho copiato e incollato il resto dell'articolo. Non leggerlo se vuoi reinventare l'implementazione.

(defun  constrained-search  (L  U)    
"Find solution  to  A'  +  B'  +  C '  =  D'    
with  L  <=  D  <  U."       
(decompose-each (constraint-sieve  L  U)))     

Questa funzione di primo passaggio vincolo-setaccia itera sulla variabile D sui valori tra L e U che sono primi rispetto a 10. Per ogni D, itera sulla variabile C su valori inferiori a D che sono nella corretta corrispondenza del modulo 625 con D. Quando una coppia (D, C) supera entrambi l'insieme di test di modularità e test kctor e prime-factor comuni, quindi il valore N = (D '- C') / 625 è mettere in una lista. Gli elenchi per ciascuna scelta di D vengono aggiunti insieme e restituiti come vdue del funzione. Ecco il codice per la funzione first pass: (defun constraint-sieve (L U) "Applicare i vincoli modulari e dei fattori a D e C. Restituisci la lista dei candidati che superano i test. "

(loop  for  D  in  (prime-10  L  U)    
append    
(loop for  C  in  (good-e-for-d  D)    
when (and (mod-ok-p  D  C)    
(factor-ok-p  D  C))    
collect    
(/  (-  (biquad  D)  (biquad  C))    
625))))    

La funzione di secondo passaggio si decompone: ognuno prende l'elenco di candidati generato dal primo passaggio come argomento. Si itera sulla variabile N sui candidati nell'elenco. Per ogni candidato, esso calcola i limiti corretti su A e scorre tra di loro. Quando trova una A tale che N - A 'sia un biquadrato, sfugge al livello esterno e restituisce alcune informazioni sul vincitore. Se un vincitore si incontra, sarebbe necessaria un'altra funzione per identificarla completamente. Ecco il codice per il secondo passa la funzione:

(defun decompose-each (candidates)    
"Attempt  to  decompose each  of  the candidates.   
Return successful decomposition."    
(loop with hd-root  =  (biquad-rt  0.5)    
for  N  in  candidates   
for  a-limit  =  (i-biquad-rt  N)    
for  a-min  =  (ceiling  (*  halflroot a-lim't))    
do    
(loop  for  A from  a-min  below a-limit   
when (biquadrate-p  (-  N  (biquad A)))    
do    
(return-from decompose-each (list  N  A))))))     

Quanti candidati possiamo aspettarci che venga prodotto il primo passaggio? Quanti valori A devono eseguire la scansione del secondo passaggio per il candidato medio? Supponiamo che il i candidati sono distribuiti uniformemente sotto U ', quindi il limite superiore medio su A è circa 415. (U') '/' = 4U / 5 e solo il 16% di tale intervallo viene scansionato.

Non sono sicuro, come calcoli esattamente la quarta radice di potenza, ma questa operazione è molto costosa. Allo stesso modo il calcolo della 4a potenza è costoso. L'utilizzo di un database per precalorizzare i 4 ° poteri fino a un milione potrebbe risparmiare un sacco di risorse.
Allo stesso modo, puoi iniziare con una potenza perfetta e provare la sottrazione piuttosto che l'aggiunta. In questo modo salti 100 ^ 4 + 1 ^ 4 + 2 ^ 4 casi che hai menzionato.
La cosa migliore da fare è andare in una biblioteca universitaria e trovare quella carta. (Scusa, non ho questo documento). Devono aver usato alcuni trucchetti che meritano di essere letti.

Crea una struttura dati che crei tutte le somme di due quarti potenze in ordine ascendente e un'altra che crei tutte le differenze positive di due quarti poteri in ordine ascendente. Quindi confronta i numeri di entrambe le liste in ordine crescente. In questo modo hai solo O (n ^ 2) numeri da controllare invece di O (n ^ 3).

Fondamentalmente, cerca un ^ 4 + b ^ 4 = c ^ 4 - d ^ 4. Oppure lascia c = d + e, e cerca un ^ 4 + b ^ 4 = (d + e) ^ 4 - d ^ 4 = 4d ^ 3e + 6d ^ 2e ^ 2 + 4de ^ 3 + e ^ 3.

Per generare un elenco enorme di numeri in ordine, cercare "coda di priorità".

Aggiungere un po 'all'implementazione: immagina di voler gestire le somme sulla mano sinistra e le differenze sulla mano destra fino a 10 ^ 24. Sul lato sinistro, hai 10 ^ 6 ≥ a ≥ b ≥ 0. Usa una matrice per memorizzare 0 ≤ a ≤ 10 ^ 6 che b usi per ciascuna a; inizialmente ogni "a" ha b = 0, e si immettono i 1.000,001 valori a ^ 4 + b ^ 4 in una coda di priorità (insieme a ciascun valore a). Quindi si prende ripetutamente il valore più piccolo dalla coda di priorità, si aumenta il valore b nella voce dell'array corrispondente di 1 e si aggiunge il nuovo valore a ^ 4 + b ^ 4.

Sul lato destro, se guardi i valori d ^ 4 - c ^ 4, d potrebbe essere grande come 63 milioni. Invece guarda i valori (c + e) ^ 4 - c ^ 4, e hai solo bisogno di e da 1 a 1.000.000.

PS. x ^ 4 = 0 (modulo 16) se x è pari e x ^ 4 = 1 (modulo 16) se x è dispari. Pertanto nell'equazione a ^ 4 + b ^ 4 + c ^ 4 = d ^ 4, a, b, c, d sono tutti pari, oppure d e uno di a, b, c sono dispari. Possiamo ignorare tutte le soluzioni uniformi, perché otteniamo tutte quelle trovando un'altra soluzione e moltiplicando tutti i numeri per 2. Possiamo supporre che quello strano di a, be c è c. Così ora guardiamo a ^ 4 + b ^ 4, dove a e b sono entrambi pari, e d ^ 4 - c ^ 4 dove d e c sono entrambi dispari, o (c + e) ^ 4 - c ^ 4, dove e è pari e c è dispari. Ciò consente di risparmiare circa 3/4 di tutti i numeri da testare.

L'aritmetica modulare è la chiave.

Prima di tutto, prendi il totale e aggiungi tutti i suoi byte insieme. Se si verifica una qualsiasi traversata, aggiungere anche quelle nel totale (ad esempio, F0 + F6 = E7). Continua finché non hai un valore a byte singolo. Il processo funziona altrettanto bene se si inizia aggiungendo parole a 32 bit a parole a 32 bit finché non si ottiene un risultato a 32 bit e quindi la "metà superiore" a 16 bit alla "metà inferiore" a 16 bit e poi la "metà superiore" a 8 bit di quel risultato alla "metà inferiore" a 8 bit. Dal momento che i linguaggi di alto livello non gestiscono le trasporta molto bene, usa l'assemblatore).

Questo ti dà il valore del totale, modulo 255 = 3 x 5 x 17. Modulo 3, una quarta potenza può essere solo 0 o 1. Modulo 5, una quarta potenza può essere solo 0 o 1. Modulo 17, una quarta potenza può essere solo 0, 1, 4, 13 o 16. Usando questi fatti puoi facilmente precomporre una tabella che dice, per ogni valore compreso tra 0 e 255, se una quarta potenza (modulo 255) può avere quel valore o no . La tabella può essere una tabella di 256 bit o 256 byte: scegli quale sia più efficiente.

Quindi il tuo algoritmo è, dato un totale, diciamo che è lungo 128 bit:

1. Aggiungi i 64 bit superiori ai 64 bit inferiori, aggiungendo il carry, che ti darà un numero a 64 bit compreso tra 0 e 2 ^ 64 - 1.
2. Aggiungi i 32 bit superiori ai 32 bit inferiori, aggiungendo il carry, che ti darà un numero a 32 bit compreso tra 0 e 2 ^ 32 - 1.
3. Aggiungi i 16 bit superiori ai 16 bit inferiori, aggiungendo il carry, che ti darà un numero a 16 bit compreso tra 0 e 2 ^ 16 - 1.
4. Aggiungi gli 8 bit superiori agli 8 bit in basso, aggiungendo il carry, che ti darà un numero a 8 bit compreso tra 0 e 2 ^ 8 - 1.
5. Cerca il numero nella tua tabella "potrebbe essere una quarta potenza", che per comodità ha 256 voci da 0 a 255 inclusi (la voce per 255 è uguale alla voce per 0).
6. Se la tabella "potrebbe essere una quarta potenza" indica che il risultato potrebbe essere una quarta potenza, quindi testare la "quarta potenza" usando la tecnica esistente.

Solo 4/51, o meno dell'8%, dei totali lo farai fino al passaggio 6, quindi hai velocizzato l'intero processo di un fattore di circa 12.

Come bonus, con un po 'più precomputazione, puoi notare che il totale modulo 255 dipende solo dai valori dei tuoi numeri originali modulo 255. Puoi quindi precomputare una tabella di tutti i 256 x 256 x 256 insiemi di moduli 255 valori di a1, a2, a3 - questo è solo 16MB o 16Mb, a seconda di come decidi di memorizzarlo - e usa questa tabella per dirti se valga la pena calcolare il 4 ° potere.

Potresti anche provare a fare cose modulo 65535 invece di modulo 255, che rimuove il passo 4, lascia solo 1/51 = 2% dei tuoi totali rendendolo fino alla fase "quarta radice", a scapito di un po ' tabella di ricerca più ampia (64 KB o 64 KB).

Un filtro ancora più veloce

Guarda solo il byte meno significativo - efficacemente, il valore modulo 256. Ci sono solo 18 LSB possibili che corrispondono a 4 potenze perfette, quindi riduci istantaneamente il tuo 4o rooting al 7%. E questo filtro può essere combinato con il modulo-255 o modulo-65535. Il risultato sarà 181 o 725 volte più veloce del metodo di enumerazione originale.