58
\$\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
  • 7
    \$\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\$
    – MilkyWay90
    Jan 26, 2019 at 17:51

70 Answers 70

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\$
    – Wheat Wizard
    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\$
1 2
3

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.