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
\$\begingroup\$

Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]
\$\endgroup\$
1
  • \$\begingroup\$ You can save a couple of bytes with @* (and then drop the final @#&) \$\endgroup\$ Jun 14, 2017 at 18:14
1
\$\begingroup\$

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)
}
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Mathematica, 30 bytes

Or@@EvenQ[2Sqrt[5#^2+{4,-4}]]&
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
1
1
\$\begingroup\$

05AB1E, 7 bytes

ÅF夹_~

Try it online!

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

><>, 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<
\$\endgroup\$
1
  • \$\begingroup\$ Finally, a ><> answer. \$\endgroup\$
    – Gryphon
    Jun 14, 2017 at 20:08
1
\$\begingroup\$

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.

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

Actually, 2 bytes

fu

Try it online!

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

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

Ruby, 64 41 40 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ last@ -> *|:, 0 1 -> !2 \$\endgroup\$
    – ngn
    Sep 7, 2019 at 8:53
  • \$\begingroup\$ @ngn thanks, updated! \$\endgroup\$
    – scrawl
    Sep 9, 2019 at 8:20
  • \$\begingroup\$ would it still work if you moved the first arg to the left of { }/? {x,+/-2#x}/[x>*|:;!2] -> (x>*|:){x,+/-2#x}/!2 \$\endgroup\$
    – ngn
    Sep 9, 2019 at 8:26
  • \$\begingroup\$ 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! \$\endgroup\$
    – scrawl
    Sep 9, 2019 at 8:38
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Deadcode
    Aug 29, 2022 at 21:16
1
\$\begingroup\$

Prolog (SWI), 36 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ Here is 3 bytes of that solution in the for loop. \$\endgroup\$
    – NK1406
    Dec 15, 2018 at 19:00
  • \$\begingroup\$ 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 \$\endgroup\$
    – c--
    Jul 9, 2022 at 22:27
1
\$\begingroup\$

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 42 bytes \$\endgroup\$
    – Aiden Chow
    Aug 19, 2023 at 2:00
  • \$\begingroup\$ oh wait you can save a byte by going 0^n4-4 instead of -4+0^n4 lol \$\endgroup\$
    – Aiden Chow
    Aug 19, 2023 at 2:17
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
};
\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

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.