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.

The Challenge 361 post clearly states the two tasks - computing the Zeckendorf representation of a number and finding a celebrity in a matrix, along with illustrative examples that make the problem definitions easy to grasp. Its structured presentation of inputs and expected outputs helps readers understand the algorithmic goals before diving into solutions, making it a solid reference for anyone exploring these classic programming challenges.

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);
}

21 lines of code

Output from script

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