Checking if a number can be written as a product of some fibonacci numbers

Question

I have tried to solve the problem above but I got stuck. I guess that it all comes to factorization by non-prime numbers. The number could be really big - about 10^15.

What I attempted to do is to factor the x and all the Fibonacci numbers up to about 155th(this is the one that is over 10^30, and that means that I can not include its factors in my x's factors), then just like in normal factorization, I loop from the highest Fibonacci number to the lowest and check if my x has all the factors of the i-th Fibonacci number. If it does then I divide x by it. When I get to the i=1(I looped through all the Fibonacci factors table), I just check if my x is equal to 1. If it is, then my answer is YES, otherwise it is NO.

This solution does not work, because sometimes it divides x in way which rules out further division, so I tried to split it into two loops - the first one can divide the x by only Fibonacci numbers which have at least one number which does not belong to the Fibonacci sequence, and the second one can divide by every number.

I took factored Fibonacci numbers from this website: http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html

Here is an example which destroys the 1st idea:

x=2^10 × 3^5 × 5^2 × 7 × 11 × 17 × 23 × 47 × 89 × 1103

I divide it by: 48th number, 12th, 11th, 10th and after that I can't get rid of the 17 so my answer is no, but it should be yes dividing by: 48th, 11th, 10th, 9th, 10th, 6th, 5th, 3*4th.

My 2nd idea is a little bit weird so that is why I wrote it. Is my solution correct? Or maybe there is another which can determine if the number can be written as a product of Fibonacci numbers? (Note that x can be really big)

Answer 1

Without relying on any special properties of Fibonnacci numbers, you could categorise this as a coin change problem, where the available coins are the Fibonacci numbers, and the target must be achieved via multiplication instead of addition.

A solution is then to use a recursive algorithm combined with memoization to avoid the same subproblem to be solved repeatedly (principle of dynamic programming).

Here is a demo implementation in JavaScript, which runs the algorithm for the problem you mentioned in the question:

// Preprocessing: collect all Fibonacci numbers with 15 digits or less:
let fib = [];
let a = 1, b = 2;
while (b < 1e16) {
    fib.push(b);
    [a, b] = [b, a+b];
}
fib.reverse(); // Put greatest Fib numbers first

let memo = new Map(); // For memoization
function solve(n, start=0) {
    if (n === 1) return true;
    let result = memo.get(n);
    if (result === undefined) { // Not in map:
        let i;
        for (i = start; i < fib.length; i++) {
            if (n % fib[i] == 0) {
                // Try solving problem after division by this factor:
                if (solve(n / fib[i], i)) break;
            }
        }
        result = i < fib.length;
        memo.set(n, result);
    }
    return result;
}

// Example input from question:
n = 2**10 * 3**5 * 5**2 * 7 * 11 * 17 * 23 * 47 * 89 * 1103
console.log(n, solve(n)); // 864126051784934400 true