Recognizing Fibonacci Numbers

April 20, 2018

One approach is to enumerate the Fibonacci numbers until you reach the target, then compare:

(define (fibonacci? x)
  (if (< x 1) #f
    (let loop ((prev 1) (fib 1))
      (if (< fib x) (loop fib (+ fib prev))
        (= fib x)))))
> (fibonacci? 13)
#t
> (fibonacci? 15)
#f

If you know number theory, you know that a number nis a Fibonacci number if and only if one of 5n² ± 4 is a perfect square:

(define (fibonacci? x)
  (let ((5xx (* 5 x x)))
    (or (square? (+ 5xx 4))
        (square? (- 5xx 4)))))
> (fibonacci? 13)
#t
> (fibonacci? 15)
#f

Isn’t number theory grand? You can run the program at https://ideone.com/XqUP3W

Advertisements

Pages: 1 2

9 Responses to “Recognizing Fibonacci Numbers”

  1. Milbrae said

    I found a nice hint here: https://www.geeksforgeeks.org/check-number-fibonacci-number/

    from math import sqrt
    
    def issquare(n):
        return int(sqrt(n))**2 == n
    
    def isfib(n):
        return issquare(5*n*n + 4) or issquare(5*n*n - 4)
    
    if __name__ == "__main__":
        data = [1,2,3,5,7,9,10,13,19,21,28,100]
        for f in data:
            print (str(f) + " -> Fibonacci = " + str(isfib(f)))
    

    Sample output:
    1 -> Fibonacci = True
    2 -> Fibonacci = True
    3 -> Fibonacci = True
    5 -> Fibonacci = True
    7 -> Fibonacci = False
    9 -> Fibonacci = False
    10 -> Fibonacci = False
    13 -> Fibonacci = True
    19 -> Fibonacci = False
    21 -> Fibonacci = True
    28 -> Fibonacci = False
    100 -> Fibonacci = False

  2. Zack said

    Here is my implementation in Julia (not the best implementation but, hey, it’s Friday).

    Functions:

    function CreateFibonacciSequence(n::Int64)
    if n == 1; return [n, n]; end
    c = 3
    Z = [1, 1]

    while Z[end] < n
        z = Z[end] + Z[end-1]
        Z = vcat(Z, z)
    end
    
    return Z
    

    end

    function IsFibonacci(n::Int64)
    if n == 1; return true; end
    F = CreateFibonacciSequence(n)
    return F[end] == n
    end

    Testing:

    IsFibonacci(14)
    false

    IsFibonacci(13)
    true

    IsFibonacci(1)
    true

  3. Zack said

    Actually, I just realized that the c variable in the first function is redundant. Apologies for that…

  4. chaw said

    Here is a solution in standard (R7RS) Scheme that is similar to
    @programmingpraxis’s solution but also works with the “negafibonacci”
    extension of F_n for n < 0.

    (import (scheme base)
            (scheme write)
            (only (srfi 1) iota every any)
            (srfi 8))
    
    (define (perfect-square? n)
      (and (not (negative? n))
           (integer? n)
           (receive (root rem) (exact-integer-sqrt n)
             (zero? rem))))
    
    ;; This version works for x = F_n with n<0 as well.
    ;; For the reasoning, see the proof [Gessel, Ira (October 1972),
    ;; "Fibonacci is a Square", The Fibonacci Quarterly, 10 (4): 417-19].
    (define (fib? x)
      (let ((t (* 5 (square x))))
        (or (perfect-square? (+ t 4))
            (and (>= x 0)
                 (perfect-square? (- t 4))))))
    
    ;;; Testing...
    
    ;; The n'th Pingala-Fibonaaci number, for integer n (including
    ;; extension to negative n).
    (define (fib n)
      (cond ((zero? n)
             0)
            ((negative? n)
             ((if (even? n) - +) (fib (- n))))
            (else
             (let loop ((i 1) (a 0) (b 1))
               (if (>= i n)
                   b
                   (loop (+ i 1) b (+ a b)))))))
    
    (define (test)
      (and (every fib? (map fib (iota 21 -10)))
           (not (any fib? (map - (map fib (iota 10 -3 -2)))))))
    
    (display (test)) 
    (newline)
    

  5. Globules said

    A Haskell version.

    import Math.NumberTheory.Powers.Squares (isSquare)
    import Text.Printf (PrintfArg, printf)
    
    -- True if and only if the argument is a Fibonacci number.  This test is from
    -- the Wikipedia article on Fibonacci numbers.
    isFib :: Integral a => a -> Bool
    isFib n = let s = 5 * n * n in isSquare (s + 4) || isSquare (s - 4)
    
    testIsFib :: (Integral a, PrintfArg a) => a -> IO ()
    testIsFib n = printf "%-5s %d\n" (show $ isFib n) n
    
    main :: IO ()
    main = do
      mapM_ testIsFib [0 .. 13 :: Int]
      
      -- http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html
      let fib300 :: Integer
          fib300 = 222232244629420445529739893461909967206666939096499764990979600
      testIsFib fib300
      testIsFib (fib300 + 1)
    
    $ ./isfib
    True  0
    True  1
    True  2
    True  3
    False 4
    True  5
    False 6
    False 7
    True  8
    False 9
    False 10
    False 11
    False 12
    True  13
    True  222232244629420445529739893461909967206666939096499764990979600
    False 222232244629420445529739893461909967206666939096499764990979601
    
  6. Paul said

    @Milbrae: your implementation does not really work for for large numbers as issquare is not correct for large numbers. Fibonacci number 76 is 5527939700884757. For this number and (almost) all next numbers your method fails. If you use an issquare function based on an isqrt method for integer numbers, than it works. Below is an example:

    def isqrt(n):
        if n < 0:
            raise ValueError("x must be non-negative")
        if n == 0:
            return 0
        x = 2 ** ((n.bit_length() - 1) // 2 + 1)    # x > sqrt(n)
        y = x - 1
        while y < x:
            x = y
            y = (x + n//x) // 2
        return x
    
    # Quadratic residues mod to filter out 99% of all cases
    d64 = frozenset((0, 1, 4, 9, 16, 17, 25, 33, 36, 41, 49, 57))
    d63 = frozenset((0, 1, 4, 7, 9, 16, 18, 22, 25, 28, 36, 37, 43, 46, 49, 58))
    d25 = frozenset((0, 1, 4, 6, 9, 11, 14, 16, 19, 21, 24))
    d31 = frozenset((0, 1, 2, 4, 5, 7, 8, 9, 10, 14, 16, 18, 19, 20, 25, 28))
    d23 = frozenset((0, 1, 2, 3, 4, 6, 8, 9, 12, 13, 16, 18))
    d19 = frozenset((0, 1, 4, 5, 6, 7, 9, 11, 16, 17))
    d17 = frozenset((0, 1, 2, 4, 8, 9, 13, 15, 16))
    d11 = frozenset((0, 1, 3, 4, 5, 9))
    
    def is_square(n):
        return (n % 64 in d64 and n % 63 in d63 and n % 25 in d25 and
                n % 31 in d31 and n % 23 in d23 and n % 19 in d19 and
                n % 17 in d17 and n % 11 in d11 and isqrt(n)**2 == n)
    
  7. codepad link –
    http://codepad.org/8dlred0k

    Python Code —>

    import math
    num = input()
    num = float(num)

    n1 = 5numnum – 4
    n2 = 5numnum + 4

    def checksqr(N): #function for perfect sqaure

    sq = math.sqrt(N)
    flr = math.floor(sq)
    res = sq - flr
    return res
    

    r1 = checksqr(n1)
    r2 = checksqr(n2)

    if(r1 ==0) or (r2==0):
    print(“Fibonacci”)
    else:
    print(“Not Fibonacci”)

  8. V said

    In Ruby using simple method.

    
    def fib?(n)
      return false if n < 0
      return true if n == 0
      
      prev = 0
      curr = 1
      
      loop do
        temp = prev + curr
        prev = curr
        curr = temp
        return true if curr == n
        return false if curr > n
      end
    end
    
    # Test
    
    (0..21).each do |n|
      r = fib?(n) ? "✅" : "❌"
      puts "#{n} #{r}"
    end
    
    

    Outputs:

    0 ✅
    1 ✅
    2 ✅
    3 ✅
    4 ❌
    5 ✅
    6 ❌
    7 ❌
    8 ✅
    9 ❌
    10 ❌
    11 ❌
    12 ❌
    13 ✅
    14 ❌
    15 ❌
    16 ❌
    17 ❌
    18 ❌
    19 ❌
    20 ❌
    21 ✅

  9. Daniel said

    Here’s a solution in C using GMP.

    /* fibonacci.c */
     
    // Build
    //   $ gcc -o fibonacci fibonacci.c -lgmp
     
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>
    
    #include <gmp.h>
    
    bool calc_is_fibonacci(const mpz_t n) {
      mpz_t x;
      mpz_init(x);
      mpz_set(x, n);
      mpz_pow_ui(x, x, 2);
      mpz_mul_ui(x, x, 5);
      bool output = false;
      mpz_add_ui(x, x, 4);
      output = mpz_perfect_square_p(x);
      if (!output) {
        mpz_sub_ui(x, x, 8);
        output = mpz_perfect_square_p(x);
      }
      mpz_clear(x);
      return output;
    }
    
    int main(int argc, char* argv[]) {
      if (argc < 2) {
        fprintf(stderr, "Usage: fibonacci <INT> [<INT> ...]\n");
        return EXIT_FAILURE;
      }
      for (size_t i = 1; i < argc; ++i) {
        mpz_t n;
        mpz_init(n);
        mpz_set_str(n, argv[i], 10);
        bool is_fib = calc_is_fibonacci(n);
        gmp_printf("%Zd,%d\n", n, is_fib);
        mpz_clear(n);
      }
      return EXIT_SUCCESS;
    }
    

    Example Usage:

    $ ./fibonacci {0..20}
    0,1
    1,1
    2,1
    3,1
    4,0
    5,1
    6,0
    7,0
    8,1
    9,0
    10,0
    11,0
    12,0
    13,1
    14,0
    15,0
    16,0
    17,0
    18,0
    19,0
    20,0
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: