While participating in this year’s annual »GSA Ultra« Python competition for UK university students, I grew fond of one particular little problem about prime-like “factorisation into Fibonacci numbers”. Even though the problem statement evokes nothing but complications (at least to me):
Given a positive integer , decide whether it is expressible as a product of Fibonacci numbers. That is:
it turns out to have a very straightforward solution. The numbers expressible as a product of Fibonacci numbers are known and even have their own »OEIS sequence«, which however does not explain how to find out whether a given number if expressible in this form. The answer is the following procedure which only takes time:
- Let be the finite sequence of Fibonacci numbers smaller or equal to , in decreasing order, except 8 and 144.
- For each in this order, divide by as many times as possible.
- If the number remaining in the end is , is expressible as a product of Fibonacci numbers, otherwise it is not.
Proof. If the remaining number is , we have just expressed as a product of Fibonacci numbers. Conversely, assume is expressible as some product of Fibonacci numbers. First off, we substitute any appearance of and in the product for and respectively. Let be the largest Fibonacci number in the product. By »Carmichael’s theorem«, there exists a prime which divides both and but none of the other Fibonacci numbers in the product. The number of ‘s in the product must be then equal to the exponent of in prime factorisation of , which is also the “maximal number of times that divides ”. Similarly, (the second largest Fibonacci number in the product) appears in the product times, which is the “maximal number of times that divides ”. Continuing, the number that remains at the end of the procedure will be .
A code snippet that does the job is below. It gives the answer instantly for numbers as big as Python’s arithmetic allows.