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

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