# 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.

## Examples:

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, 2019 at 17:51

# Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]

• You can save a couple of bytes with @* (and then drop the final @#&) Jun 14, 2017 at 18:14

# JS (ES6), 57 bytes

n=>(y=y=>((5*(n**2)+y)**0.5),~~y(4)==y(4)|~~y(-4)==y(-4))


Uses carusocomputing's method. Alot golfier than my other answer.

### Ungolfed

n=>{
y=y=>((5*(n**2)+y)**0.5);//carusocomputing's method in a function
return ~~y(4) === y(4) || ~~y(-4) === y(-4);//~~x === Math.floor(x)
}


## 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, 2017 at 17:51
• ÅFsåO¹_~ fixes it but thats another byte. feelsbadman Jun 14, 2017 at 19:58
• @Datboi Actually can be fixed still 7 bytes. Jun 15, 2017 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, 2017 at 20:08

# 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, 2017 at 20:35
• I misread the input, somehow, as saying positive number, rather than non-negative. Jun 15, 2017 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, 2019 at 8:53 • @ngn thanks, updated! Sep 9, 2019 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, 2019 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, 2019 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  # dc, 34 bytes d0r^+0 1[d3R+d4Rd_5R>s]dssx0r4R-^p  Try it online! Prints 1 if the number at the top of the stack is a fibonacci number, 0 otherwise. # Bash, 87 bytes read z;f=0;g=1;h=1 for((;;)){ h=$(($f+$g))
if [ $z ==$f ];then echo 1;fi
f=$g;g=$h
}


Attention endless loop, no break - stop the code after some seconds manually

Try it online!

• You can shorten this to 49 bytes, but I don't consider an endless loop to be a valid output method. Halting upon printing the result only increases it to 52 bytes. Note that in both of these, $h contains an unevaluated addition which is then automatically evaluated in the for. Aug 29, 2022 at 21:16 # Prolog (SWI), 36 bytes \N:-1+N+0. Y+N+X:-X<N,X+Y+N+Y;X=:=N.  Try it online! # Thunno 2, 5 bytes ĖÆF$Ƈ


Attempt This Online!

#### Explanation

ĖÆF$Ƈ # Implicit input Ė # Push [0..input] ÆF # For each n, get the nth Fibonacci number # (starting at 0->0, 1->1, 2->1, etc.)$Ƈ  # Is the input in this list?
# Implicit output


# C (gcc), 76, 52, 71 bytes,

## GTP4 after some serious tutoring finally 58 bytes

f(n,a,b){for(a=b=1;a<n;b+=a,a=b-a);return n==a||n==b||!n;}

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

f(n,i,j){for(i=0,j=1;j<n;i=j,j+=i);return j==n||!n;}


Try it online!

• Here is 3 bytes of that solution in the for loop. Dec 15, 2018 at 19:00
• you need to reset i=0 if you're going to call it with a lower value, otherwise the function is only guaranteed to work once
– c--
Jul 9, 2022 at 22:27

# Desmos, 58 41 bytes

-17 bytes thanks to Aiden Chow!

f(n)=0^{mod((5nn+[4,0^n4-4])^{.5},1).min}


Try it on Desmos!

Checks if either $$\5n^2+4\$$ or $$\5n^2-4\$$ is a perfect square.

• 42 bytes Aug 19, 2023 at 2:00
• oh wait you can save a byte by going 0^n4-4 instead of -4+0^n4 lol Aug 19, 2023 at 2:17

# 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.