# 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? – MilkyWay90 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. – Magic Octopus Urn Jun 14 '17 at 17:51
• ÅFsåO¹_~ fixes it but thats another byte. feelsbadman – Datboi Jun 14 '17 at 19:58
• @Datboi Actually can be fixed still 7 bytes. – Erik the Outgolfer 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. – Gryphon 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. – Gryphon 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 – AGourd 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. – Gryphon Jun 14 '17 at 20:35
• I misread the input, somehow, as saying positive number, rather than non-negative. – Robert Benson 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! – scrawl 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! – scrawl 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). – Wheat Wizard Jul 5 '17 at 17:46