Problem of the Day -- Is Fibonacci

Is Fibonacci

Coming up on another great week! We'll start off with a simple one.

Given a number less than 2^30, determine if the number is a Fibonacci Number or not. If it is return true, else false. Bonus points for optimized calculations of the Fibonacci Numbers.

Permalink: http://problemotd.com/problem/is-fibonacci/

Comments:

safi - 10 years, 7 months ago

def fib(n):
    if n==0:
        return True
    pre0 = 0
    pre1 = 1
    now = 0
    while True:
        now = pre0 + pre1
        pre0 = pre1
        pre1 = now
        if n == now:
            return True
        elif now > n:
            return False

reply permalink

Pearce Keesling - 10 years, 7 months ago

Here is an estimate which I hope remains accurate that high, but I'm not sure. The formula is all that really matters, but I wrote it in ruby just to make my life easy.
```
def fib(n)
    (1.61803398875^n-(-1.61803398875)^(n*-1))/sqrt(5)
end
```
reply permalink

Pearce Keesling - 10 years, 7 months ago

I realized I hadn't fixed my operators :P.

def fib(n)
        (1.61803398875**n-(-1.61803398875)**(n*-1))/(5**(0.5))
end

puts fib(ARGV[0].to_i);

reply permalink

Karl - 10 years, 7 months ago
Whaaaaaaaat :D.

I don't want to waste your time - I know that's Ruby but could you provide a brief little snippet as to what each thing is for? (why that number, the double asterisk, asterisk minus, etc.)

Thanks :D.

reply permalink
Pearce Keesling - 10 years, 7 months ago

Sorry, I didn't see that for a few days haha. The number is the golden ratio. I totally stole this formula from wolfram alpha. The formula is here, http://www.wolframalpha.com/share/clip?f=d41d8cd98f00b204e9800998ecf8427e2snclf2p88.

Phi is the golden ratio.

the double asterisks are power notation (ruby version of ^), the *-1 is just to make n negative.

reply permalink
Anonymous - 10 years, 7 months ago
(from Wikipedia) I guess from Binet's formula one can assert that given a Fibonacci number x , one or both of the expressions 5x² +4 and 5x² - 4 should yield a perfect square number.

Reference: http://en.wikipedia.org/wiki/Fibonacci_number#Recognizing_Fibonacci_numbers

Should be pretty simple to implement.

reply permalink

Nick Krichevsky - 10 years, 7 months ago

A bit long, but it works

from math import sqrt
from random import randint

def checkFib(n):
    num=5*(n**2)+4
    #A shoddy way for checking perfect squares
    if int(sqrt(num))==sqrt(num):
        return True
    else:
        num=5*(n**2)-4
        if int(sqrt(num))==sqrt(num):
            print num
            return True
    return False
fibCheck=randint(1,2**30)
if checkFib(fibCheck):
    print fibCheck, "is a fibonacci number"
else:
    print fibCheck, "is not a fibonacci number"

reply permalink

Anonymous - 10 years, 7 months ago

This is in Clojure.

(defn new-fib-generator []
  (let [acc (atom [0 1])
        swap-acc (fn [[x y]] [y (+ x y)])]
    (fn []
      (first (swap! acc swap-acc)))))

(let [all-fibs (repeatedly (new-fib-generator))
      fibs (set (take-while (partial > Integer/MAX_VALUE) all-fibs))]
  (defn fib? [n] (contains? fibs n)))

(fib? 377)  ; => true
(fib? 378)  ; => false

reply permalink

Pyro - 10 years, 7 months ago

def fibronacci(list):
    list.append(list[len(list)-2]+list[len(list)-1])
    return list

i=1
aux=False
fib=[0,1]
n=int(raw_input("Number?\n"))
while n>fib[i] and aux==False:
    fib=fibronacci(fib)
    i+=1
    if fib[i]==n:
        aux=True

print aux
if aux:
    print "Fibronacci number:", (i)

reply permalink

ujjl - 10 years, 7 months ago

Haskell

isFibonacci :: Int -> Bool
isFibonacci num = isFibon num 0 1

isFibon :: Int -> Int -> Int -> Bool
isFibon x a b
    | x == a || x == b  = True
    | x < b             = False
    | otherwise         = isFibon x b (a + b)

reply permalink

Jack The Stripper - 10 years, 7 months ago

I had tumbleweed in mind when writing this:

fib = function(x) {
  var tumbleA = 1;
  var tumbleB = 1;
  for (i = 1; tumbleA < x & tumbleB < x; i++) {
    var temp = tumbleB;
    tumbleB += tumbleA;
    tumbleA = temp;
    if (tumbleB == x)
      return true;
  }
  return false;
}

reply permalink

Anonymous - 10 years, 6 months ago

#python 2.7
import math
def fibonnaci(x):
    y = (5*(x**2)+4)**(0.5)
    z = (5*(x**2)-4)**(0.5)

    if (math.floor(y) == y) or (math.floor(z) == z):
        Fibonacci = True
    else:
        Fibonacci = False

    return Fibonacci

reply permalink

Problem of the Day A new programming or logic puzzle every Mon-Fri

Is Fibonacci

Comments:

Problem of the Day
A new programming or logic puzzle every Mon-Fri