Am I a Fibonacci Number?

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.

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

Scoring:

This is , lowest byte count wins.

• 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? Jan 26 '19 at 17:51

CJam, 37 bytes

ri1T{\1$+_3$-g"1T 0_ 1"S/=~}g]W=

CJam has no Fibonnaci built-in. On the bright side, this does use g twice, and I think this is the first time I've ever used it!

k, 20 bytes

{*x=*|(*x>)(|+\)\1 1}

Generates fibonacci numbers until it overshoots. Then it checks the last one it generated for equality. 1 is truthy, 0 is falsey.

Try it online.

Mathematica, 30 bytes

Or@@EvenQ[2Sqrt[5#^2+{4,-4}]]&

Java 8, 94 bytes

x->{int i=0;for(;c(i++)<=x;);return c(i-2)==x;}int c(int n){return n<1?0:n<2?1:c(n-1)+c(n-2);}

Explanation:

Try it here. (NOTE: It's a bit slow for very large test-cases.)

x->{                 // Method (1) with integer parameter and boolean return-type
int i=0;           //  Index
for(;c(i++)<=x;);  //  Loop as long as the Fibonacci number is smaller or equal to the input
return c(i-2)==x;  //  And then return if the input equals the previous Fibonacci number
}                    // End of method (1)

// Method to get nth Fibonacci number
int c(int n){        // Method (2) with integer parameter and integer return-type
return n<1?        //  If n==0:
0                //   Return 0
:n<2?             //  Else if n==1
1                //   Return 1
:                 //  Else:
c(n-1)+c(n-2);   //   Return recursive calls with n-1 and n-2
}                    // End of method (2)

05AB1E, 7 bytes

ÅFå¤¹_~

Try it online!

• Actually, this randomly seems to return 2, 3 and 4. Try for input of 13 and above. Jun 14 '17 at 17:51
• ÅFsåO¹_~ fixes it but thats another byte. feelsbadman Jun 14 '17 at 19:58
• @Datboi Actually can be fixed still 7 bytes. Jun 15 '17 at 8:16

><>, 40 83 bytes

Added 43 bytes so that it takes the correct input

i:0(?vc4*-
v&a~<
+>l2(?v$&:a*&* v ~&< >10r:&1)?v1n; =?v&:&)?v>:{+::&:& >1n;n0< A less golfy version would be: // Read input i:0(?vc4*- >~a&v >l2(?v$&:a*&*+
>&~04.
// Determine if in Fibonacci
10r:&1)?v1n;
>:{+::&:&=?v&:&)?v
>1n;n0<
• Finally, a ><> answer. Jun 14 '17 at 20:08
• Umm, sorry, but you need to be able to take input from 0-1,000,000,000, inclusive. ASCII doesn't go anywhere near that high. Jun 14 '17 at 20:17
• Opps, didn't see that requirement. I'll try to fix it, although reading numerical inputs with ><> can be weird Jun 15 '17 at 13:01

AWK, 56 63 61 bytes

{for(n[++j]++;n[j]<$1;n[++j]=n[j]+n[j-1]){}$0=$0?n[j]==$1:1}1

Try it online!

Brute force is fun. :) If you want it to work for arbitrarily large numbers, add a -M argument, but that is outside the scope of the problem.

7 bytes added to account for 0 as input, but shaved a couple off using the ternary operator.

• Umm, this doesn't return truthy for 0, which, according to the question, is included in the Fibonacci Sequence. Jun 14 '17 at 20:35
• I misread the input, somehow, as saying positive number, rather than non-negative. Jun 15 '17 at 17:03

Actually, 2 bytes

fu

Try it online!

Pushes either a positive number for truthy or 0 for falsy.

Cubix, 22 24 bytes

0 is truthy, nothing is falsey

@0O1I!^/@.W<rq\?-p+;;u

Try it online!

@ 0
O 1
I ! ^ / @ . W <
r q \ ? - p + ;
; u
. .

Watch it run

I may be able to get a couple more out of this ... found them with a change to the initial redirect into the loop

• I get the integer to check
• ! check for 0 input
• ^O@ if zero, output and halt
• /01 initialise the stack for doing the sequence
• W<W change lane onto the redirect back to self, then change lane into looping section
• +p-? bring the check value to the top, subtract and check
• /@ On a positive result reflect and halt
• \^O@ On a zero result reflect, output and halt
• u;\qr; Remove the check, move check value to bottom, rotate the sum, remove the low value. Continue into loop.

Java, 40 bytes

r->Math.abs((r*Math.sqrt(5)-~r)%2*r-r)<2

This is a straight Java port of @xnor's answer.

D, 57 bytes

A nice, clean, no-nonsense solution:

int f(int n,int x=0,int y=1){return y<n?f(n,y,x+y):y==n;}

This one is 58 bytes but doesn't use recursion, and so might be more practical for larger inputs:

alias f=(n){int x,y=1;for(;y<n;y+=x,x=y-x){}return y==n;};

And here's one where the function declaration itself is only 54 bytes, though it depends on the mach library.

import mach.range : r=recur, l=last;
import mach.math.vector : v=vector;
const z=v(0,1);

// The 54-byte function
alias f=n=>z.r!(a=>v(a.y,a.x+a.y),a=>a.y>n).l(z).y==n;

alias f=n=>(
vector(0,1) // Seed the sequence
.recur!(v=>vector(v.y,v.x+v.y),v=>v.y>n) // Compute Fib numbers until N
.last(vector(0,1)).y == n // If the last number was N, return true
// Value in parens "last(...)" is a fallback for n==0 and empty seq.
);

><>, 33+3 = 36 bytes

3 bytes added for the -v flag

10:{:}=?!v1n;
)?v:@+10.\:{:}
n0/;

Try it online!

Or 54 bytes without using the -v flag

0ic4*-:0(?v$a*+10. :{:}=?!v1n;\10 v:@+d1.\:{:})? \0n; Try it online! Japt, 8 7 bytes ÆMgXÃøU Test it Explanation Implicit input of integer U. Æ Ã Generate an array of integers from 0 to U-1 and pass each through a function where X is the current element. MgX Get the Xth Fibonacci number. øU Check if the array contains (ø) the original input U. Implicitly return the boolean result. C, 36 bytes f(x,a,b){return x>b?f(x,b,a+b):x==b} It puts some warnings, and requires at least 32-bit integers. Newer C standards probably won't even compile it. It should be called as f(142857,0,1). Bonus: it can calculate Fibonacci-ness with different initial values, too. Ruby, 64 41 40 bytes ->n,a=b=1{a,b=b,a+b;a<n ?redo:a>n ?p: 1} Try it online! cQuents, 8 bytes =0,1?Z+Y Try it online! Explanation =0,1 Set sequence start to 0,1 ? Mode: Query (assumes increasing sequences) Z+Y Each item is the previous two summed Brachylog, 16 14 bytes 1;0⟨t≡+⟩ⁱhℕ↙.! Try it online! Takes input through the output variable and outputs through success or failure, and in the case of success the input variable is unified with 1. 1;0 Starting with [1,0], ⁱ iterating ⟨ ≡ ⟩ replacing ⟨t ⟩ the first element of the pair with the last element ⟨ +⟩ and the last element with the sum of the pair h until the first element ℕ↙ is greater than or equal to . the output variable, ! and stopping then, h the first element of the pair is equal to the output variable. ℕ↙.! is necessary for it to terminate on false test cases. k4, 30 26 bytes -4 thanks to ngn! {x in(x>*|:){x,+/-2#x}/!2} the above is a simple while iterator. (cond){func}/arg. {x,+/-2#x} / x join sum over last 2 elements of x (i.e. append next Fib) (x>*|:) /!2 / while outer func input is greater than last element (x>*|:) of inner func output, pass inner func output to inner func x in / check if x is in array. returns boolean • last@ -> *|:, 0 1 -> !2 – ngn Sep 7 '19 at 8:53 • @ngn thanks, updated! Sep 9 '19 at 8:20 • would it still work if you moved the first arg to the left of { }/? {x,+/-2#x}/[x>*|:;!2] -> (x>*|:){x,+/-2#x}/!2 – ngn Sep 9 '19 at 8:26 • yeah it does. that was my first approach but i couldn't get it to work. not sure what's different now. thanks again, will update! Sep 9 '19 at 8:38 CSASM v2.1.2.3, 259 bytes func main: push 0 pop$1
push 1
pop $2 in "" conv i32 pop$a
push $a push 1 comp.lte push$f.o
brfalse c
.lbl b
push 1
print
ret
.lbl a
push 0
print
ret
.lbl c
clf.o
push $1 dup push$2
pop $1 pop$2
push $1 push$a
comp.gt
push $f.o brtrue a push$1
push $a comp push$f.o
brtrue b
br c
ret
end

Commented and ungolfed:

func main:
; Seed the sequence ($1 = new value,$2 = old value)
push 0
pop $1 push 1 pop$2

; Get the input, convert it to an integer and store it in the accumulator
in ""
conv i32
pop $a ; If$a <= 1, print truthy (1)
push $a push 1 comp.lte push$f.o
brfalse loop

.lbl isFib
; Print a truthy value
push 1
print
ret
.lbl notFib
; Print a falsy value
push 0
print
ret

; Keep generating new Fibonacci numbers until $1 is >=$a
.lbl loop
; Clear the Comparison flag
clf.o

; Get the next Fibonacci pair:
; $2 =$1, $1 =$1 + $2 push$1
dup
push $2 add pop$1
pop $2 ; If$1 > $a, the input wasn't a Fibonacci number push$1
push $a comp.gt push$f.o
brtrue notFib

; If $1 ==$a, the input was a Fibonacci number
push $1 push$a
comp
push \$f.o
brtrue isFib

; Still need to generate more numbers
br loop
ret
end

Swift, 66 bytes

func f(n:Int){var a=0,b=1,c=0;while n>a{c=a;a=b;b=c+b};print(n<a)}

Try it out! - NOTE: Prints False as truthy and True for falsy.

JS (ES6), 78 bytes

n=>{y=n?0:1;f=x=>x<3?1:f(x-1)+f(x-2);for(x=0;x<n+2;x++)f(x)==n?y=1:0;return y}

Ungolfed:

var f = n => {
var y = n ? 0 : 1;
f=x=>x<3?1:f(x-1)+f(x-2);//from this: https://codegolf.stackexchange.com/a/25142/70700
for (var x = 0; x < n + 2; x++){
if(f(x) == n){
y = 1;
}else{
y = 0;
}
}
return y;
};

Groovy, 4443 37 bytes

{n->[-4,4].any{!((n*n*5+it)**0.5%1)}}

If (5*(n**2)±4)**0.5 is ever an integer, the number is a fibbonacci number.

C (gcc), 76 bytes

F(n){return n<2?n:F(n-1)+F(n-2);}i;f(n){for(i=0;F(i)<n;i++);return F(i)==n;}

Try it online!

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!

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.

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. :)

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.

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

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!

Python 3, 59 Bytes

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