# Finding the Zeckendorf Representation of a Positive Integer (BIO 2023 Q1)

I was practicing question 1a of the British Informatics Olympiad 2023 past paper.

In the Fibonacci sequence each number is generated by adding the previous two numbers in the sequence. We will start with the numbers 1 and 2, so the sequence is 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, … The Zeckendorf representation of the number n consists of the distinct numbers from the Fibonacci sequence which sum to n, where no two adjacent numbers from the Fibonacci sequence are used. There is always a unique representation.
For example:

• 21 is represented by the single number 21;
• 21 is not represented by 8 13, even though they sum to 21, as those numbers are adjacent in the Fibonacci sequence;
• 100 is represented by 3 8 89
The Zeckendorf representation for n always includes the largest number from the Fibonacci sequence that is no greater than n.

Write a program that reads in a number (between 1 and 1,000,000 inclusive) and outputs the numbers (in any order) in the corresponding Zeckendorf representation.

I wrote this code:

#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node *next;
};
typedef struct Node Node;

int find_largest_le_fib_n(int n) {
if (n == 0 || n == 1) {
return n;
}

int f1 = 0, f2 = 1, f3 = 1;

while (f3 <= n) {
f1 = f2;
f2 = f3;
f3 = f1 + f2;
}

return f2;
}

Node* find_zeckendorf(int n) {
Node *last;
Node *first;
Node *penultimate = NULL;

int largest_le_fib;

while (n > 0) {
largest_le_fib = find_largest_le_fib_n(n);

last = malloc(sizeof(Node));
last->data = largest_le_fib;
last->next = NULL;

if (first == NULL) {
first = last;
}

if (penultimate != NULL) {
penultimate->next = last;
}

penultimate = last;

n -= largest_le_fib;
}

return first;
}

int main() {
int n = 0;

printf("Enter number: ");
scanf("%d", &n);

Node *zeckendorf_list = find_zeckendorf(n);

while (zeckendorf_list != NULL) {
printf("%d ", zeckendorf_list->data);

Node *temp = zeckendorf_list;
zeckendorf_list = zeckendorf_list->next;
free(temp);
}

printf("\n");
}


Example run:

Enter number: 100
89 8 3


(More test cases can be found in the mark scheme)

I would be grateful to hear about any improvements that could be made to this code.

• Which do you find easier to review for correctness: last = malloc(sizeof(Node)); or last = malloc(sizeof *last);? Commented Jul 7 at 12:42

#### Review:

Again, nice looking code that does what it is supposed to do. Well presented and fairly easy to follow. Kudos!

But, the exercise states "in any order", so much of the clerical code (that is correct, too) dealing with heap memory and a linked list is, in fact, a distraction.

Since the exercise is to generate the list of numbers only, the following (distilled from your code) is presented here for your learning and appraisal.

#include <stdio.h>

int find( int n ) {
if( n == 1 ) return n;

int f1 = 1, f2 = 2; // tiny shortcut as problem suggests
while( f1 + f2 <= n ) {
int fx = f1 + f2;
f1 = f2;
f2 = fx;
}

return f2;
}

int main( void ) {
int n = 0;

for( ;; ) { // infinite loop for testing many numbers
printf("Enter number: ");
if( scanf( "%d", &n ) != 1 ) { // check return codes!
scanf( "%*[^\n]" ); // clear the input buffer. (read scanf doco!)
continue;
}

for( int large; n; n -= large )
printf( "%d ", large = find( n ) ); // output is all that's required
puts( "" );
}

return 0;
}


Here's an abridged list of some Fibonacci numbers

       0   #01
1   #02
...
832040   #31
1346269   #32 // Bigger than the problem's 1000000 limit


Output:

Enter number: 832039
514229 196418 75025 28657 10946 4181 1597 610 233 89 34 13 5 2
Enter number:


Now that we know there are 31 Fibonacci numbers between 0 and 1000000, a simple array of int store[31] would more-than serve to store and print the found values of interest for this exercise.

Were such an array to be populated once at startup (only to the limit of interest for 'single shot' or to the 1000000 limit for multiple queries) determination of the Zeckendorf representation values to be printed would be greatly accelerated.

Your code is very good. A lesson that will be valuable going forward is to only write correct code to meet today's requirements. Some suggest coding in certain (costly) ways "in case the demands change tomorrow." Let tomorrow take care of itself. Take care that the user typing "foo", instead of 15642, doesn't cause your program to collapse in a pool of tears.

#### Poor man's profiling

Enter number: 832039
..........................514229 ........................196418 ......................75025 ....................28657 ..................10946 ................4181 ..............1597 ............610 ..........233 ........89 ......34 ....13 ..5 2


Simply adding putchar( '.' ); inside the function's while() loop, we can see the effect of recalculating the (shortened) Fibonacci sequence values to find these desired values. And this is the 'ceiling' of only 106 (considering only the first ~30 Fibonacci numbers).

Eventually, a long long will be necessary to go for more Fibonacci numbers. Given the finite maximums of a long and a long long, what are the maximum Fibonacci numbers that can be represented without recourse to more advanced techniques of representing very large integer values? Would it be worthwhile calculating as many of these constants as possible ONE TIME, then having those as a compile time array of values to use for this and other explorations of number theory?

(FYI: There are 182 dots (iterations) in that 'profiling' string, and there should be about 28 more if the function didn't shortcut by skipping 0+1 and 1+1.)

With the recent posting of a very compact Python solution of the OP's problem, it behooves C to also present its possibilities of concise expression: C here

• Maybe if( scanf( "%d", &n ) != 1 ) { --> if( scanf( "%d", &n ) != 1 || n <= 0 ) { (with an error message) to handle not only non-numeric input, but also out of range (at least 1 side of the range). As is, code prints only '\n' when input 0. Commented Jul 7 at 12:37
• @chux-ReinstateMonica Yes, there's much that could be improved about the code I've presented here. Thank you. My primary purpose was to remove the LL bits, protect against entry of "foobar", and 'publish' the (tiny) count of Fibonacci numbers that could be calc'd and stored and searched quickly... OP seems interested in other parts of the original challenge, too... The line between SO and CR gets blurry!! :-) Cheers! Commented Jul 7 at 12:46
• Ugh... I'd like to play around with the "Added interest" code, but godbolt has such a shitty UI (at least on my phone) that I never even figured out how to copy the code. I hate that site. Commented Jul 8 at 13:38
• @nocomment To each their own... :-) Cheers! Commented Jul 8 at 13:40
• Node *first; shall be Node *first = NULL;. Otherwise, a test for first == NULL invokes UB.

• find_largest_le_fib_n is redoing the same work over and over again. It seems better to precompute an array of Fibonacci numbers in the range of 1,000,000 once, and binary search it. You can even do it off-line - there are not too many of them.

• malloc may fail. Make sure to test its return value.

• The problem statement does not specify an order of numbers in the representation. An example says 3 8 89, while your code produces 89 8 3. If such order is OK, you don't need a linked list at all.

• How would you propose storing the numbers if not in a linked list? Commented Jul 7 at 5:58
• @sbottingota Since the problem statement you've posted suggests "in any order", there's no need to store the discovered numbers. Simply output each as it is found, and carry on... Commented Jul 7 at 6:57
• @Fe2O3 I know, but as questions 1b-1d are also about zeckendorf representations, I wanted to not have to immediately print them out to stdout. Do you know any way of doing this other than a linked list? Commented Jul 7 at 8:02
• @sbottingota FWIW: that number (53,316,291,173) is Fib #54 (based on 0, 1, 1,...). Much smaller than I expected! Suggest that populating an array with 54 values, then simply scanning across it will be advantageous. (If you're really clever, you may be able to deduce a formula that predicts how many terms are needed for each value's Zeckendorf representation... Study the Wikipedia page on the subject; esp. the diagram at the top-right of the page... Cheers! Commented Jul 7 at 12:59
• @Fe2O3 I don't think we need Knuth for that one :-) We have 51 Fibonacci numbers to choose from, and want to choose 3 but not neighbors. That's simply 49C3. Commented Jul 8 at 20:32

In my opinion you did not just choose an unnecessarily complicated algorithm/implementation but also an unnecessarily complicated language. In that round, "any language" was allowed. And you only had three hours and there were lots more questions, so better keep it simple to save time.

Simpler algorithm/implementation in a simpler language (Python, Attempt This Online!):

n = int(input())
while n:
a, b = 1, 2
while b <= n:
a, b = b, a+b
print(a, end=' ')
n -= a


Although the equivalent C version isn't that much longer (Attempt This Online!):

#include <stdio.h>

int main() {
int n;
scanf("%d", &n);
while (n) {
int a = 1, b = 2;
while (b <= n) {
int sum = a + b;
a = b;
b = sum;
}
printf("%d ", a);
n -= a;
}
}


More efficient algorithm (really not needed, though, as it is super fast already) without a list, instead reversing the calculation (Attempt This Online!):

n = int(input())
a, b = 1, 2
while b <= n:
a, b = b, a+b
while n:
if a <= n:
print(a, end=' ')
n -= a
a, b = b-a, a

• @Fe2O3 Same reason: Save time. Remember the context, only three hours for plenty of questions. Don't waste time with unnecessary stuff like that. Commented Jul 8 at 12:12
• May I please know what the issue is? Commented Jul 8 at 15:37
• Not my downvote, but I believe the issue is that you're telling OP to use a different language instead of reviewing the posted code. I understand that the problem can be solved easily by changing languages, but that was not the point of the question. Commented Jul 8 at 16:51
• @Harith It's already there in C, and how is pseudocode better than Python? Commented Jul 8 at 16:53
• I find pseudocode language-agnostic. Others may feel differently. Commented Jul 8 at 16:57