Carmichael teorema dimostra che ogni numero di Fibonacci dopo 144 ha almeno un primo divisore che non divide precedente numero di Fibonacci.
Non ci sono molti numeri di Fibonacci al di sotto dei 10^18; meno di 90.
Creare un array di tutti i numeri di Fibonacci <= 10^18.
Dato un input n, che è il prodotto dei numeri di Fibonacci, la sua fattorizzazione in numeri di Fibonacci deve includere ogni numero di Fibonacci sopra 144 che divide, ripetuta tante volte quante si divide.
Passare attraverso i vostri numeri di Fibonacci, in ordine decrescente e mantenere il dividendo n per ogni numero che divide, fino ad arrivare a 144.
Ora bisogna stare attenti, perché due numeri di Fibonacci non hanno fattori primi non visto nei precedenti numeri di Fibonacci. Queste sono le 8 e 144. Da 8 a 2^a 3 e 2 è un numero di Fibonacci, non è possibile rendere il vostro numero di unfactorable in numeri di Fibonacci, prendendo la 8. Sotto ottimizzazione, si sceglie sempre la 8.
Quindi 144 è l'unico fattore che potrebbe essere necessario rifiutare per un piccolo fattore. Questo può accadere solo se il 34 o il 21 fattori, e il 144 elimina un bisogno di 2 o 3.
34 = 2 * 17, 21 = 3 * 7
Che stato prolisso, ma ci fa un semplice approccio.
Passare attraverso i numeri di Fibonacci <= n in ordine decrescente fino ad arrivare a 144, quindi passare al 34, 21, poi di nuovo a 144 e scendendo a 2.
Questo vi darà l'ottimale fattorizzazione sotto il tuo strano segnando schema.
----- a questo fine -----
[679891637638612258, 420196140727489673, 259695496911122585, 160500643816367088, 99194853094755497, 61305790721611591, 37889062373143906, 23416728348467685, 14472334024676221, 8944394323791464, 5527939700884757, 3416454622906707, 2111485077978050, 1304969544928657, 806515533049393, 498454011879264, 308061521170129, 190392490709135, 117669030460994, 72723460248141, 44945570212853, 27777890035288, 17167680177565, 10610209857723, 6557470319842, 4052739537881, 2504730781961, 1548008755920, 956722026041, 591286729879, 365435296162, 225851433717, 139583862445, 86267571272, 53316291173, 32951280099, 20365011074, 12586269025, 7778742049, 4807526976, 2971215073, 1836311903, 1134903170, 701408733, 433494437, 267914296, 165580141, 102334155, 63245986, 39088169, 24157817, 14930352, 9227465, 5702887, 3524578, 2178309, 1346269, 832040, 514229, 317811, 196418, 121393, 75025, 46368, 28657, 17711, 10946, 6765, 4181, 2584, 1597, 987, 610, 377, 233, 34, 21, 144, 89, 55, 13, 8, 5, 3, 2]
