Given an integer n <= 10^18 which is the product of Fibonacci numbers, I need to factor it into said Fibonacci numbers.
Each factorization has a score, which is one less than the count of factors plus the sum of the indices of the factors in the Fibonacci sequence that begins with f(1) = 1, f(2) = 2.
If multiple such factorizations are possible, I need the factorization that minimizes the score.
Example:
104 = 13 * 8 or 104 = 13 * 2 * 2 * 2
f(6) = 13, f(5) = 8, f(2) = 2
For 104 = 13*8 = f(6)*f(5), we have a count of 2, indices of 6 & 5, giving us 2 + 6 + 5 - 1 = 12.
For 104 = 13 * 2 * 2 * 2 = f(6) * f(2) * f(2) * f(2), we have a count of 4 and indices of 6, 2, 2, 2, giving us 4 + 6 + 2 + 2 + 2 - 1 = 15.
We should pick 13 * 8 since it has the lower score.
The biggest problem I've come across is when we have a number like 1008, which is divisible by 144 and 21, but needs to be divided by 21 because 1008 % 7 == 0. Because my program is first dividing by the biggest numbers, number 144 is 'stealing' 3 from number 21 so my program doesn't find a solution.
Carmichael's theorem proves that each Fibonacci number after 144 has at least one prime divisor that doesn't divide any earlier Fibonacci number.
There aren't many Fibonacci numbers under 10^18; fewer than 90.
Make an array of all the Fibonacci numbers <= 10^18.
Given an input n which is the product of Fibonacci numbers, its factorization into Fibonacci numbers must include every Fibonacci number above 144 that divides it, repeated as many times as it divides it.
Go through your Fibonacci numbers in descending order and keep dividing n by any such number that divides it, until you get to 144.
Now we need to be careful because two Fibonacci numbers don't have any prime factors not seen in previous Fibonacci numbers. These are 8 and 144. Since 8 is 2^3 and 2 is a Fibonacci number, you can't render your number unfactorable into Fibonacci numbers by taking the 8. Under your optimization, you will always choose the 8.
Then 144 is the only factor that you might need to reject for a smaller factor. This can only happen if 34 or 21 are factors, and the 144 eliminates a needed 2 or 3.
34 = 2 * 17, 21 = 3 * 7
That was long-winded, but it gets us to a simple approach.
Go through the Fibonacci numbers <= n in descending order until you get to 144, then skip to 34, then 21, then back to 144 and descending down to 2.
This will give you the optimal factorization under your weird scoring scheme.
----- this order ----- [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]