Crikey Math

Having fun exploring mathematics

  • Home
  • About
  • Blog
  • Contribute
en English
af Afrikaanssq Albanianam Amharicar Arabichy Armenianaz Azerbaijanieu Basquebe Belarusianbn Bengalibs Bosnianbg Bulgarianca Catalanceb Cebuanony Chichewazh-CN Chinese (Simplified)zh-TW Chinese (Traditional)co Corsicanhr Croatiancs Czechda Danishnl Dutchen Englisheo Esperantoet Estoniantl Filipinofi Finnishfr Frenchfy Frisiangl Galicianka Georgiande Germanel Greekgu Gujaratiht Haitian Creoleha Hausahaw Hawaiianiw Hebrewhi Hindihmn Hmonghu Hungarianis Icelandicig Igboid Indonesianga Irishit Italianja Japanesejw Javanesekn Kannadakk Kazakhkm Khmerko Koreanku Kurdish (Kurmanji)ky Kyrgyzlo Laola Latinlv Latvianlt Lithuanianlb Luxembourgishmk Macedonianmg Malagasyms Malayml Malayalammt Maltesemi Maorimr Marathimn Mongolianmy Myanmar (Burmese)ne Nepalino Norwegianps Pashtofa Persianpl Polishpt Portuguesepa Punjabiro Romanianru Russiansm Samoangd Scottish Gaelicsr Serbianst Sesothosn Shonasd Sindhisi Sinhalask Slovaksl Slovenianso Somalies Spanishsu Sudanesesw Swahilisv Swedishtg Tajikta Tamilte Teluguth Thaitr Turkishuk Ukrainianur Urduuz Uzbekvi Vietnamesecy Welshxh Xhosayi Yiddishyo Yorubazu Zulu

Integers as (unique) sums of Fibonacci numbers

October 3, 2017 By Gary Ernest Davis

Did you know that 100000000000 = 86267571272 + 12586269025 + 1134903170+ 9227465 + 1346269+ 514229 + 121393 + 46368 +610 + 144 + 55 and that all the numbers in the sum on the right are Fibonacci numbers?

Not only that:

  • no two of these Fibonacci numbers is consecutive in the set of all Fibonacci numbers;
  • this is the only way to write 100000000000 as a sum of non-consecutive Fibonacci numbers;
  • the software and code used to calculate this did the calculation in under one-tenth of a second.

The bloke who first twigged to this was Eddie (Edouard) Zeckendorf in 1939, but not published until 33 years later in the Fibonacci Quarterly:  Zeckendorf, E. (1972). A generalized Fibonacci numeration. Fibonacci Quart, 10, 365-372.

Eddie Zeckendorf’s result gets a whole Wikipedia page, as does Eddie himself, who was a Belgian doctor, army officer (retiring as Colonel) and mathematician.

Although Eddie (Edouard) Zeckendorf came up with the decomposition, now known by his name, in 1939 he was beaten to the punch in publication by a Dutch mathematician Cornelis Gerrit Lekkerkerker by some 20 years.

Although Eddie snoozed and let Gerrit beat him to the punch, this decomposition is now generally known as the Zeckendorf decomposition.

I feel, however, to be fair to the good Dr. Lekkerkerker we should , at the very least, refer to this as the Zeckendorf-Lekkerkerker decomposition, or ZL-decomposition for short (just because  “Zeckendorf-Lekkerkerker” is quite a Belgian-Dutch mouthful).

The ZL-decomposition of a positive integer n can be implemented as a greedy algorithm in which we search for the largest Fibonacci number below n, subtract this from n, and then do it over until we stop at a Fibonacci number.

For example, if n=70, we know, from a list of Fibonacci numbers, that 55 is the largest Fibonacci number below  70, and then 70-55 = 15, and the largest Fibonacci number below 15 is 13, and the largest Fibonacci number below 15-13 is 2, so we end up with 70 = 55 + 13 +2 as a unique sum of non-consecutive Fibonacci numbers.

But this approach relies on a pre-existing list, and if n is big we will have to generate a big list of Fibonacci numbers on the fly.

If we had a way of recognizing Fibonacci numbers we could start with n and work our way down through n-1, n-2, n-3, … until we hit a Fibonacci number: potentially slow, but at least we wouldn’t have to generate a table on the fly.

There is indeed a simple way of recognizing if a given positive integer k is a Fibonacci number.

A positive integer k is a Fibonacci number if, and only if, one or both of 5k^2-4,  5k^2+4   is a perfect square.

This was proven, and published in 1972, by Ira Gessel, then a 21 year old mathematics student at Harvard.

So this gives a nifty, computationally cheap, way of recognizing exactly which positive integers are Fibonacci numbers without having to generate and scan a list of Fibonacci numbers.

Thanks Ira!

But scanning the integers n-1, n-2, n-3, … below a given n to see which is first a Fibonacci number is a slow business: if n = 100000000000 we have to take 13732428728  steps before we hit the Fibonacci number  86267571272.

There is, it turns out, a much faster way.

This faster way relies on the fact that the k^{th} Fibonacci number \textrm{F}_k is just the floor of (the largest integer below) \frac{\phi^k}{\sqrt{5}}+1/2 , where \phi= \frac{1+\sqrt{5}}{2}.

Denoting the floor of a real number x by \lfloor x\rfloor this gives us a very simple, and quick way to calculate the largest Fibonacci number \textrm{F}_k \leq n:

  • first calculate k= \lfloor \log_{\phi}(n\sqrt{5}+1/2)\rfloor ;
  • then compute \textrm{F}_k = \lfloor \phi^k/\sqrt{5}+1/2\rfloor.

So our greedy algorithm for the ZL-decomposition now goes:

  • Input n;
  • Compute k and F_k as above;
  • Replace n with n-F_k ;
  • Repeat until we get a Fibonacci number for k ;
  • Output F_{k_1}, \ldots , F_{k_p} with n=F_{k_1}+ \ldots + F_{k_p}

and this is fast!

http://www.crikeymath.com/wp-content/uploads/2017/09/crikey.wav

 

Filed Under: Uncategorized

Recent Posts

  • Does the DNA test say guilty or not guilty?
  • The Turtleback Diagram for Conditional Probability
  • Numbers that, base 2, are blindingly obviously divisible by 3
  • A mysterious sequence of 1s and 2s
  • Does one have to be a genius to do mathematics? Neither necessary nor sufficient.
  • Alexander Bogomolny
  • Binary disjoints of an integer
  • A cycle of length 5 for iterated squaring modulo a prime
  • The diagonal of the Wythoff array
  • Leonardo Bigollo, accountant, son of Bill Bonacci

Archives

Copyright © 2023 · Dynamik Website Builder on Genesis Framework · WordPress · Log in