59
\$\begingroup\$

Your Task:

Write a program or function to check if a number that is inputted is a Fibonacci number. A Fibonacci number is a number contained in the Fibonacci sequence.

The Fibonacci Sequence is defined as: F(n) = F(n - 1) + F(n - 2)

With the seeds being F(0) = 0 and F(1) = 1.

Input:

A non-negative integer between 0 and 1,000,000,000 that may or may not be a Fibonacci number.

Output:

A truthy/falsy value indicating whether or not the input is a Fibonacci number.

Examples:

0-->truthy 1-->truthy 2-->truthy 12-->falsy 

Scoring:

This is , lowest byte count wins.

\$\endgroup\$
1
  • 8
    \$\begingroup\$ The programming language I'm using only supports numbers up to 9999 (Geometry Dash). Is it okay if I assume that it does support numbers up to 1000000, theoretically? \$\endgroup\$ Commented Jan 26, 2019 at 17:51

71 Answers 71

1 2
3
0
\$\begingroup\$

C (gcc), 50 bytes

a,b,c;f(n){for(a=0,b=1;n>(c=a);b=c)a+=b;n=(n==c);} 

Try it online!

\$\endgroup\$
0
\$\begingroup\$

Clojure, 61 bytes

(def s(lazy-cat[0 1](map +(rest s)s)))#((set(take(inc %)s))%) 

This actually constructs the Fibonacci sequence s, grabs enough elements from it and checks if the input is found. Returns nil for falsy and the input number for truthy.

\$\endgroup\$
0
\$\begingroup\$

Javascript, 89 bytes

function f(n){s=Math.sqrt;c=Math.ceil;x=5*n**2;a=s(x-4);b=s(x+4);return c(a)==a||c(b)==b} 

This uses the fact that all fibonacci numbers have the property that 5x^2+4 or 5x^2-4 must be square. It takes the square root of these numbers and checks if they equal their ceiling value.

Javascript, 69 bytes (if it doesn't need to be a function)

s=Math.sqrt;c=Math.ceil;x=5*n**2;a=s(x-4);b=s(x+4);n=c(a)==a||c(b)==b 

This one does the exact same thing, except instead of calling a function, you set n to the number to test, and n is set to true/false based on the result.

This is my first code golf entry, so let me know if there's anything to improve here. :)

\$\endgroup\$
0
\$\begingroup\$

QBIC, 24 bytes

≈g<:|g=p+q┘p=q┘q=g]?g=a 

Explanation

≈g<:| WHILE g (running fibonacci total) is less than input g=p+q Get the next fib by adding p (n-2, starts as 0) and q (n-1, starts as 1) ┘ (Syntactic linebreak) p=q increase n-2 ┘ (Syntactic linebreak) q=g increase n-1 ] WEND ?g=a PRINT -1 if g equals input (is a fib-number), or 0 if not. 
\$\endgroup\$
0
\$\begingroup\$

Swift, 72 bytes

func f(i:Int,a:Int=0,b:Int=1)->Bool{return a<i ?f(i:i,a:b,b:a+b) :i==a} 

Un-golfed:

func f(i:Int, a:Int=0, b:Int=1)->Bool{ return a<i ? f(i: i, a: b, b: a+b) : i==a } 

I am recursively calling f until a is equal to or greater then i. Then, I check to see if i and a are equal.

You can try it here

\$\endgroup\$
0
\$\begingroup\$

Python 3, 56 53 50 bytes

  • Thanks to @Fedone for 3 bytes: as a function
def f(m): a=b=1 while a<m:b,a=a,a+b print(a==m) 

Try it online!

\$\endgroup\$
1
0
\$\begingroup\$

Python 3, 59 Bytes

f=5*int(input())**2 print(not((f+4)**0.5%1and(f-4)**0.5%1)) 
\$\endgroup\$
1
  • \$\begingroup\$ You don't need the space between and and (f-4). \$\endgroup\$ Commented Jul 5, 2017 at 17:46
0
\$\begingroup\$

[Python 3], 48 bytes

m=0;k=1;exec("k,m=m,m+k\nif k==n:print(1)\n"*n) 

If n is the input, we generate the first n Fibonacci numbers and check if our input is one of them.

\$\endgroup\$
0
\$\begingroup\$

MathGolf, 4 bytes

⌠rf╧ 

Try it online!

Explanation

We need to increment the input twice before creating the range because we know that \$F_{n+1} \geq n,\forall n \geq 0\$.

⌠ increment twice r range(0, n) f pop a, push fibonacci(a) (maps to the range) ╧ pop a, b, a.contains(b) (check if input is in list) 
\$\endgroup\$
0
\$\begingroup\$

brev, 46 bytes

(c(fn(or(= x z)(and(< x z)(f y(+ x y)z))))0 1) 
\$\endgroup\$
0
\$\begingroup\$

AWK, 43 bytes

$0=(5*$1^2+4)^.5!~/\./||(5*$1^2-4)^.5!~/\./ 

Attempt This Online!

Prints 1 for truthy or nothing for falsey.

Slightly longer version will print 0 for falsey:

1,$0=(5*$1^2+4)^.5!~/\./||(5*$1^2-4)^.5!~/\./ 

Attempt This Online!

\$\endgroup\$
1 2
3

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.