Am I a Fibonacci Number?

Question

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 code-golf, lowest byte count wins.

Answer 1

Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]

Answer 2

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)
}

Answer 3

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!

Answer 4

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.

Answer 5

Mathematica, 30 bytes

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

Answer 6

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 `n`th 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)

Answer 7

05AB1E, 7 bytes

ÅF夹_~

Try it online!

Answer 8

><>, 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<

Answer 9

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.

Answer 10

Actually, 2 bytes

fu

Try it online!

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

Answer 11

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.

Answer 12

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.

Answer 13

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;

// Exploded for readability
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.
);

---

Answer 14

><>, 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!

Answer 15

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.

Answer 16

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.

Answer 17

Ruby, 64 41 40 bytes

->n,a=b=1{a,b=b,a+b;a<n ?redo:a>n ?p: 1}

Try it online!

Answer 18

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

Answer 19

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.

Answer 20

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

Answer 21

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
add
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

Answer 22

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.

Answer 23

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!

Answer 24

Prolog (SWI), 36 bytes

\N:-1+N+0.
Y+N+X:-X<N,X+Y+N+Y;X=:=N.

Try it online!

Answer 25

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

Answer 26

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

Thanks GPT4 with a bit of prompt engineering

Way off, just plain wrong, good for the three test inputs but...

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!

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

Answer 28

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.

Answer 29

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;
};

Answer 30

Groovy, 44 43 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.