NonFibonacci

NonFibonacci, also written as non-Fibonacci, refers to the natural numbers that are not Fibonacci numbers. Under the common definition F0 = 0, F1 = 1 and Fn = Fn-1 + Fn-2, the Fibonacci sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, and so on. The non-Fibonacci numbers are all positive integers not equal to any Fibonacci number. The sequence of initial terms begins 4, 6, 7, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 35, ...

There are infinitely many non-Fibonacci numbers; their density among the natural numbers is 1, since the number of Fibonacci numbers up to N is only about log_phi(N) and grows much more slowly than N. Between consecutive Fibonacci numbers F_k and F_{k+1} there are F_{k+1} - F_k - 1 = F_{k-1} - 1 non-Fibonacci numbers.

Computation and testing: To determine if a given n is non-Fibonacci, one may test whether n is a Fibonacci number. A standard test is that n is a Fibonacci number iff 5n^2 + 4 or 5n^2 - 4 is a perfect square. Therefore, n is a non-Fibonacci number if neither expression is a perfect square. Alternatively, one can generate Fibonacci numbers up to n and check for membership.

See also Fibonacci numbers; Zeckendorf’s representation; sequences and their complements. The concept is primarily of interest in number theory and recreational mathematics, where it helps illustrate the distribution of a sparse subsequence within the integers.