50
\$\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
  • 2
    \$\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 '19 at 17:51

62 Answers 62

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\$ – Magic Octopus Urn Jun 14 '17 at 17:51
  • \$\begingroup\$ ÅFsåO¹_~ fixes it but thats another byte. feelsbadman \$\endgroup\$ – Datboi Jun 14 '17 at 19:58
  • \$\begingroup\$ @Datboi Actually can be fixed still 7 bytes. \$\endgroup\$ – Erik the Outgolfer Jun 15 '17 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\$
3
  • \$\begingroup\$ Finally, a ><> answer. \$\endgroup\$ – Gryphon Jun 14 '17 at 20:08
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Gryphon Jun 14 '17 at 20:17
  • \$\begingroup\$ Opps, didn't see that requirement. I'll try to fix it, although reading numerical inputs with ><> can be weird \$\endgroup\$ – AGourd Jun 15 '17 at 13:01
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 '17 at 20:35
  • \$\begingroup\$ I misread the input, somehow, as saying positive number, rather than non-negative. \$\endgroup\$ – Robert Benson Jun 15 '17 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 '19 at 8:53
  • \$\begingroup\$ @ngn thanks, updated! \$\endgroup\$ – scrawl Sep 9 '19 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 '19 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 '19 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\$
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\$
0
\$\begingroup\$

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!

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

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!

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

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.

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

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

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

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

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

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

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!

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

Python 3, 59 Bytes

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.