Problem Statement

Just as numbers can be represented in a positional notation as sums of multiples of the powers of ten (decimal) or two (binary); all the positive integers can be represented as the sum of one or zero times the distinct members of the Fibonacci series. Recall that the first six distinct Fibonacci numbers are: 1, 2, 3, 5, 8, 13. The decimal number eleven can be written as 013 + 18 + 05 + 13 + 02 + 01 or 010100 in positional notation where the columns represent multiplication by a particular member of the sequence. Leading zeroes are dropped so that 11 decimal becomes 10100. 10100 is not the only way to make 11 from the Fibonacci numbers however; 013 + 18 + 05 + 03 + 12 + 11 or 010011 would also represent decimal 11. For a true Zeckendorf number there is the added restriction that no two consecutive Fibonacci numbers can be used which leads to the former unique solution.

Generate and show here a table of the Zeckendorf number representations of the decimal numbers zero to twenty, in order.
The intention in this task to find the Zeckendorf form of an arbitrary integer. The Zeckendorf form can be iterated by some bit twiddling rather than calculating each value separately but leave that to another separate task.

Let's start with the solution:

import std.stdio, std.range, std.algorithm, std.functional;

void main() {
    size_t
    .max
    .iota
    .filter!q{ !(a & (a >> 1)) }
    .take(21)
    .binaryReverseArgs!writefln("%(%b\n%)");
}


import std.stdio, std.typecons;

int zeckendorf(in int n) pure nothrow {
     Tuple!(int,"remaining", int,"set")
     zr(in int fib0, in int fib1, in int n, in uint bit) pure nothrow {
        if (fib1 > n)
            return typeof(return)(n, 0);
        auto rs = zr(fib1, fib0 + fib1, n, bit + 1);
        if (fib1 <= rs.remaining) {
            rs.set |= 1 << bit;
            rs.remaining -= fib1;
        }
        return rs;
    }

    return zr(1, 1, n, 0)[1];
}

void main() {
    foreach (i; 0 .. 21)
        writefln("%2d: %6b", i, zeckendorf(i));
}


import std.stdio, std.algorithm, std.range;

string zeckendorf(size_t n) {
    if (n == 0)
        return "0";
    auto fibs = recurrence!q{a[n - 1] + a[n - 2]}(1, 2);

    string result;
    foreach_reverse (immutable f; fibs.until!(x => x > n).array) {
        result ~= (f <= n) ? '1' : '0';
        if (f <= n)
            n -= f;
    }

    return result;
}

void main() {
    foreach (immutable i; 0 .. 21)
        writefln("%2d: %6s", i, i.zeckendorf);
}