Task — Zeckendorf representation

You are given a positive integer (<= 100). Write a script to return the Zeckendorf Representation of the given integer.

Zeckendorf's theorem states that every positive integer can be uniquely represented as sum of non-consecutive Fibonacci numbers.

Examples

Example 1
Input: $int = 4
Output: 3,1
4 => 3 + 1 (non-consecutive fibonacci numbers)

Example 2
Input: $int = 12
Output: 8,3,1
12 => 8 + 3 + 1

Example 3
Input: $int = 20
Output: 13,5,2
20 => 13 + 5 + 2

Example 4
Input: $int = 96
Output: 89,5,2
96 => 89 + 5 + 2

Example 5
Input: $int = 100
Output: 89,8,3
100 => 89 + 8 + 3

Analysis

Édouard Zeckendorf

Édouard Zeckendorf (1901-1983) was a Belgian army doctor who was held as a prisoner of war in Germany during World War II. He was a recreational mathematician and an amateur artist, and after the war he served with a peacekeeping mission on the India/Pakistan border. His name appears as an author of more than 100 mathematical papers.

My solution has two phases:

1. Create a Fibonacci series up to a number which exceeds the supplied integer.
2. Repeated subtract from the supplied integer the largest qualifying number in the series until the result is zero.

A qualifying number is one which has not been used already, and neither have the immediately preceding and following ones.

This works because Zeckendorf also showed that a 'greedy' approach is adequate: that is, using the largest remaining qualifying (as defined above) number will yield the solution; it is never necessary to backtrack.

My solution works in negligible time even for large numbers: my last example, where the supplied integer is 10^7, completes in milliseconds.

Try it 

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2026-02-16
use utf8;     # Week 361 - task 1 - Zeckendorf representation
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

zeckendorf_representation(4);
zeckendorf_representation(12);
zeckendorf_representation(20);
zeckendorf_representation(96);
zeckendorf_representation(100);
zeckendorf_representation(10_000_000);

sub zeckendorf_representation {
    
    my ($integer, $remains, @fib, $n, $f, $explain);
    
    # initialise
    $integer = $_[0];
    $remains = $integer;
    
    # create Fibonacci series up to $integer
    $fib[0] = $fib[1] = 1;
    $n = 1;
    do {
        $n ++;
        $fib[$n] = $fib[$n - 1] + $fib[$n - 2];
    } until ($fib[$n] > $integer);

    # repeatedly subtract qualifying fibonacci term
    for ($f = $n - 1; $f >= 0; $f --) {
        if ($fib[$f] > 0
        and ($fib[$f + 1] > 0)
        and ($f > 0 and $fib[$f - 1] > 0)
        and $remains >= $fib[$f]) {
            
            # can use this term
            $remains -= $fib[$f];
            $explain .= qq[$fib[$f] + ];
            $fib[$f] = -1;
            last unless $remains;
        }
    }       
    
    # report
    say qq[\nInput:  $integer];
    say qq[Output: ] . substr($explain, 0, -3);
}

Output

Input:  4
Output: 3 + 1

Input:  12
Output: 8 + 3 + 1

Input:  20
Output: 13 + 5 + 2

Input:  96
Output: 89 + 5 + 2

Input:  100
Output: 89 + 8 + 3

Input:  10000000
Output: 9227465 + 514229 + 196418 + 46368 + 10946 + 
   4181 + 377 + 13 + 3