45
\$\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\$
  • \$\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 at 17:51

59 Answers 59

35
\$\begingroup\$

Neim, 2 bytes

f𝕚

Explanation:

f       Push an infinite fibonacci list
 𝕚      Is the input in that list?

Works the same as my It's Hip to be Square answer, but uses a different infinite list: f, for fibonacci.

Try it!

\$\endgroup\$
  • 1
    \$\begingroup\$ Wow! Impressive score. \$\endgroup\$ – Gryphon Jun 14 '17 at 17:01
  • 2
    \$\begingroup\$ That's great, but not 2 bytes. In UTF-8 it's represented as "66 F0 9D 95 9A" \$\endgroup\$ – sm4rk0 Jun 16 '17 at 14:05
  • 9
    \$\begingroup\$ @sm4rk0 That's great, but you're wrong. Neim uses a custom codepage, so the byte representation of this is 66 D5 \$\endgroup\$ – Okx Jun 16 '17 at 15:06
  • \$\begingroup\$ Doesn't this loop forever if the input is not in the list? If so, does that count as falsey? \$\endgroup\$ – Enrico Borba Jun 16 '17 at 15:09
  • \$\begingroup\$ @EnricoBorba Neim knows that the nth element in this infinite list will always be equal to or less than the n+1th element in the list. Therefore, it can catch itself and it will not run forever. Have you tried the program it? :P \$\endgroup\$ – Okx Jun 16 '17 at 15:12
15
\$\begingroup\$

JavaScript (ES6), 34 bytes

f=(n,x=0,y=1)=>x<n?f(n,y,x+y):x==n

Recursively generates the Fibonacci sequence until it finds an item greater than or equal to the input, then returns item == input.

\$\endgroup\$
  • \$\begingroup\$ NB: naive recursive calculation of the Fibonacci sequence is O(Fib(n)) - approximately O(1.6 ^ n) \$\endgroup\$ – Alnitak Jun 16 '17 at 8:47
  • \$\begingroup\$ f=n=>n?n>2?f(n-1)+f(n-2):1:0 28bytes \$\endgroup\$ – jackkav Apr 13 '18 at 6:43
  • \$\begingroup\$ @jackkav Thanks, but the challenge is to determine if the input is a Fibonacci number. \$\endgroup\$ – ETHproductions Apr 13 '18 at 14:21
12
\$\begingroup\$

Retina, 23 bytes

^$|^(^1|(?>\2?)(\1))*1$

Try it online!

Input in unary, outputs 0 or 1.

Explanation

The Fibonacci sequence is a good candidate for a solution with forward references, i.e. a "backreference" that refers either to a surrounding group or one that appears later in the regex (in this case, we're actually using both of those). When matching numbers like this, we need to figure out a recursive expression for the difference between sequence elements. E.g. to match triangular numbers, we usually match the previous segment plus one. To match square numbers (whose differences are the odd numbers), we match the previous segment plus two.

Since we obtain the Fibonacci numbers by adding the second-to-last element to the last one, the differences between them are also just the Fibonacci numbers. So we need to match each segment as the sum of the previous two. The core of the regex is this:

(         # This is group 1 which is repeated 0 or more times. On each
          # iteration it matches one Fibonacci number.
  ^1      # On the first iteration, we simply match 1 as the base case.
|         # Afterwards, the ^ can no longer match so the second alternative
          # is used.
  (?>\2?) # If possible, match group 2. This ends up being the Fibonacci
          # number before the last. The reason we need to make this optional
          # is that this group isn't defined yet on the second iteration.
          # The reason we wrap it in an atomic group is to prevent backtracking:
          # if group 2 exists, we *have* to include it in the match, otherwise
          # we would allow smaller increments.
  (\1)    # Finally, match the previous Fibonacci number and store it in
          # group 2 so that it becomes the second-to-last Fibonacci number
          # in the next iteration.
)*

Now this ends up adding the Fibonacci numbers starting at 1, i.e. 1, 1, 2, 3, 5, .... Those add up to 1, 2, 4, 7, 12, .... I.e. they are one less than the Fibonacci numbers, so we add a 1 at the end. The only case this doesn't cover is zero, so we have the ^$ alternative at the beginning to cover that.

\$\endgroup\$
  • 2
    \$\begingroup\$ Very elegant! I'd just like to point out, for completeness's sake, that it can be shortened to 20 bytes in PCRE using a possessive quantifier: ^$|^(^1|\2?+(\1))*1$ \$\endgroup\$ – Deadcode Jan 21 at 19:47
  • 1
    \$\begingroup\$ @Deadcode I do miss those a lot in .NET ;) \$\endgroup\$ – Martin Ender Jan 21 at 22:30
  • \$\begingroup\$ Save 1 byte by removing the unnecessary second ^. \$\endgroup\$ – Neil Feb 8 at 1:08
11
\$\begingroup\$

Regex (ECMAScript flavour), 392 358 328 224 206 165 bytes

The techniques that need to come into play to match Fibonacci numbers with an ECMAScript regex (in unary) are a far cry from how it's best done in most other regex flavors. The lack of forward/nested backreferences or recursion means that it is impossible to directly count or keep a running total of anything. The lack of lookbehind makes it often a challenge even to have enough space to work in.

Many problems must be approached from an entirely different perspective, and seem unsolvable until the arrival of some key insight. It forces you to cast a much wider net in finding which mathematical properties of the numbers you're working with might be able to be used to make a particular problem solvable.

In March 2014, this is what happened for Fibonacci numbers. Looking at the Wikipedia page, I initially couldn't figure out a way, though one particular property seemed tantalizingly close. Then the mathematician teukon outlined a method that made it quite clear it would be possible to do, using that property along with another one. He was reluctant to actually construct the regex. His reaction when I went ahead and did it:

You're crazy! ... I thought you might do this.

As with my other ECMAScript unary math regex posts, I'll give a warning: I highly recommend learning how to solve unary mathematical problems in ECMAScript regex. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See that post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

So do not read any further if you don't want some unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.

The challenge I initially faced: A positive integer x is a Fibonacci number if and only if 5x2 + 4 and/or 5x2 - 4 is a perfect square. But there is no room to calculate this in a regex. The only space we have to work in is the number itself. We don't even have enough room to multiply by 5 or take the square, let alone both.

teukon's idea on how to solve it (originally posted here):

The regex is presented with a string of the form ^x*$, let z be its length. Check whether or not z is one of the first few Fibonacci numbers by hand (up to 21 should do). If it is not:

  1. Read a couple of numbers, a < b, such that b is not larger than 2a.
  2. Use forward look-aheads to build a2, ab, and b2.
  3. Assert that either 5a2 + 4 or 5a2 - 4 is a perfect square (so a must be Fn-1 for some n).
  4. Assert that either 5b2 + 4 or 5b2 + 4 is a perfect square (so b must be Fn).
  5. Check that z = F2n+3 or z = F2n+4 by using the earlier built a2, ab, and b2, and the identities:
    • F2n-1 = Fn2 + Fn-12
    • F2n = (2Fn-1 + Fn)Fn
In brief: these identities allow us to reduce the problem of checking that a given number is Fibonacci to checking that a pair of much smaller numbers are Fibonacci. A little algebra will show that for large enough n (n = 3 should do), F2n+3 > Fn + 5Fn2 + 4 so there should always be enough space.

And here is a mockup of the algorithm in C which I wrote as a test before implementing it in regex.

So with no further ado, here is the regex:

^((?=(x*).*(?=x{4}(x{5}(\2{5}))(?=\3*$)\4+$)(|x{4})(?=xx(x*)(\6x?))\5(x(x*))(?=(\8*)\9+$)(?=\8*$\10)\8*(?=(x\2\9+$))(x*)\12)\7\11(\6\11|\12)|x{0,3}|x{5}|x{8}|x{21})$

Try it online!

And the pretty-printed, commented version:

^(
  (?=
    (x*)                   # \2+1 = potential number for which 5*(\2+1)^2 ± 4
                           # is a perfect square; this is true iff \2+1 is a Fibonacci
                           # number. Outside the surrounding lookahead block, \2+1 is
                           # guaranteed to be the largest number for which this is true
                           # such that \2 + 5*(\2+1)^2 + 4 fits into the main number.
    .*
    (?=                    # tail = (\2+1) * (\2+1) * 5 + 4
      x{4}
      (                    # \3 = (\2+1) * 5
        x{5}
        (\2{5})            # \4 = \2 * 5
      )
      (?=\3*$)
      \4+$
    )
    (|x{4})                # \5 = parity - determined by whether the index of Fibonacci
                           #               number \2+1 is odd or even
    (?=xx (x*)(\6 x?))     # \6 = arithmetic mean of (\2+1) * (\2+1) * 5 and \8 * \8,
                           #      divided by 2
                           # \7 = the other half, including remainder
    \5
    # require that the current tail is a perfect square
    (x(x*))                # \8 = potential square root, which will be the square root
                           #      outside the surrounding lookahead; \9 = \8-1
    (?=(\8*)\9+$)          # \10 = must be zero for \8 to be a valid square root
    (?=\8*$\10)
    \8*
    (?=(x\2\9+$))          # \11 = result of multiplying \8 * (\2+1), where \8 is larger
    (x*)\12                # \12 = \11 / 2; the remainder will always be the same as it
                           #       is in \7, because \8 is odd iff \2+1 is odd
  )
  \7\11
  (
    \6\11
  |
    \12
  )
|
  x{0,3}|x{5}|x{8}|x{21}   # The Fibonacci numbers 0, 1, 2, 3, 5, 8, 21 cannot be handled
                           # by our main algorithm, so match them here; note, as it so
                           # happens the main algorithm does match 13, so that doesn't
                           # need to be handled here.
)$

The multiplication algorithm is not explained in those comments, but is briefly explained in a paragraph of my abundant numbers regex post.

I was maintaining six different versions of the Fibonacci regex: four that ratchet from shortest length to fastest speed and use the algorithm explained above, and two others that use a different, much faster but much more lengthy algorithm, which as I found can actually return the Fibonacci index as a match (explaining that algorithm here is beyond the scope of this post, but it's explained in the original discussion Gist). I don't think I would maintain that many very-similar versions of a regex again, because at the time I was doing all my testing in PCRE and Perl, but my regex engine is fast enough that concerns of speed are not as important anymore (and if a particular construct is causing a bottleneck, I can add an optimization for it) – though I'd probably again maintain one fastest version and one shortest version, if the difference in speed were big enough.

The "return the Fibonacci index minus 1 as a match" version (not heavily golfed):

Try it online!

All of the versions are on github with the full commit history of golf optimizations:

regex for matching Fibonacci numbers - short, speed 0.txt (the shortest but slowest one, as in this post)
regex for matching Fibonacci numbers - short, speed 1.txt
regex for matching Fibonacci numbers - short, speed 2.txt
regex for matching Fibonacci numbers - short, speed 3.txt
regex for matching Fibonacci numbers - fastest.txt
regex for matching Fibonacci numbers - return index.txt

\$\endgroup\$
9
\$\begingroup\$

Python 3, 48 bytes

lambda n:0in((5*n*n+4)**.5%1,abs(5*n*n-4)**.5%1)

Try it online!

\$\endgroup\$
  • 1
    \$\begingroup\$ Being Python should it not work, given enough resources, for arbitrarily large inputs? \$\endgroup\$ – Jonathan Allan Jun 14 '17 at 17:49
  • 2
    \$\begingroup\$ I always had the impression we could use whatever algorithm we wanted as long, as it works in practice if the calculations fits in the data type and in theory given infinite precision. Sure, using only int would set the bar higher (still not arbitrarily large), but we also don't force C answers to use 64-bit integers (or 128-bit with gcc). At any rate, being allowed to use the same algorithm in one language but not another seems nonsensical. \$\endgroup\$ – Dennis Jun 15 '17 at 4:34
  • \$\begingroup\$ The algorithmic view does make sense (I had always thought it was the input domain that dictated the "fit in data type" criteria). The only thing to watch for is the grey area between what is the idea of the algorithm and its implementation. Here one could check if either of the integers are square without casting to floats. I guess that an internal cast as a side-effect is acceptable so long as it is part of a legitimate, working algorithm (...and I'm pretty sure an algorithm that relied on the cast would not be acceptable). \$\endgroup\$ – Jonathan Allan Jun 15 '17 at 5:03
  • \$\begingroup\$ @JonathanAllan Since the maximum value to handle is 1e9, I dont think arbitrarily large inputs would be a problem. \$\endgroup\$ – JAD Jun 16 '17 at 13:24
  • 1
    \$\begingroup\$ @JarkoDubbeldam yes, that detail was actually changed after my comment was made. \$\endgroup\$ – Jonathan Allan Jun 16 '17 at 13:28
7
\$\begingroup\$

Python 2, 48 44 bytes

f=lambda n,a=0,b=1:n>a and f(n,b,a+b)or n==a

Try it online

Thanks to Jonathan Allan for saving 4 bytes

\$\endgroup\$
  • \$\begingroup\$ This can be 47 bytes, if truthy values can be False and falsy values True: TIO! \$\endgroup\$ – Mr. Xcoder Jun 14 '17 at 17:20
  • \$\begingroup\$ Could also use n-a in place of n==a and have -1 and 0 as your return values. \$\endgroup\$ – Magic Octopus Urn Jun 14 '17 at 18:06
  • \$\begingroup\$ @carusocomputing I had that in my edit history, but it doesn't work, because for larger test values, you might have -101 or some other result instead of -1. \$\endgroup\$ – mbomb007 Jun 14 '17 at 21:47
  • \$\begingroup\$ @Mr.Xcoder do you really think that saving 1 byte is worth everybody's sanity? \$\endgroup\$ – frarugi87 Jun 16 '17 at 14:23
  • 1
    \$\begingroup\$ @frarugi87 Saving a byte is always worth it \$\endgroup\$ – Mr. Xcoder Jun 16 '17 at 14:25
7
\$\begingroup\$

05AB1E, 8 7 bytes

>ÅF¹å¹m

Explanation:

>ÅF       # Generate Fibbonacci numbers up to n+1
   ¹å     # 0 if original isn't in the list, 1 if it is
     ¹m   # 0**0 = 1 if input was 0 (hotfix for 0).
          # or 0**n if not fibb / 1**n if it is a fibb.

Try it online!

-1 thanks to Jonathan Allan for the 0-not-a-fibonacci-number workaround.

\$\endgroup\$
  • \$\begingroup\$ Actually, won't be updating to 6 bytes. Can't believe there's NO way to append a 0 to a list in under 3 bytes. \$\endgroup\$ – Magic Octopus Urn Jun 14 '17 at 17:24
  • \$\begingroup\$ @JonathanAllan the "generate fibbonacci function" in 05AB1E doesn't contain 0. \$\endgroup\$ – Magic Octopus Urn Jun 14 '17 at 18:56
  • \$\begingroup\$ @JonathanAllan I understand now, nice idea. Took me a minute to figure out what was actually happening there. \$\endgroup\$ – Magic Octopus Urn Jun 14 '17 at 19:04
  • \$\begingroup\$ Isn't it enough to generate upto n (saving a byte) as ÅF is inclusive and ¹å would result in 0 either way for n=0? \$\endgroup\$ – Emigna Jun 15 '17 at 10:19
  • \$\begingroup\$ 0AF = []. 1AF = [1,1]. So apparently not. \$\endgroup\$ – Magic Octopus Urn Jun 15 '17 at 13:26
5
\$\begingroup\$

Perl 6, 23 bytes

{$_∈(0,1,*+*...*>$_)}
\$\endgroup\$
  • \$\begingroup\$ {(0,1,*+*...^*>$_).tail==$_} was what I was going to initially post. I may have gotten around to Set operators eventually. \$\endgroup\$ – Brad Gilbert b2gills Jun 14 '17 at 17:36
5
\$\begingroup\$

Seriously, 3 bytes

,fu

Try it online!

Returns the index +1 in the list of Fibonacci numbers if truthy, otherwise returns falsy.

Explanation:

,fu
,   read input
 f  0-indexed index of that number in the fibonacci sequence (-1 if not in the sequence)
  u increment. (Makes the -1 value falsy and the 0-value truthy)
\$\endgroup\$
  • 9
    \$\begingroup\$ Seriously rude ^^ \$\endgroup\$ – Jonathan Allan Jun 14 '17 at 18:01
5
\$\begingroup\$

Jelly,  8 7  6 bytes

-r‘ÆḞċ

Try it online!

How?

-r‘ÆḞċ - Link: non negative number, n
-      - literal -1      = -1
 r     - inclusive range = [-1,0,1,2,3,4,5,...,n]
  ‘    - increment n     = [ 0,1,2,3,4,5,6,...,n+1]
   ÆḞ  - Fibonacci       = [ 0,1,1,2,3,5,8,...,fib(n+1)]
     ċ - count occurrences of n (1 if n is a Fibonacci number, 0 otherwise)

Notes:

  • the increment, , is needed so this works for 2 and 3, since they are the 3rd and 4th Fibonacci numbers - beyond 3 all Fibonacci numbers are greater than their index.
  • the - is needed (rather than just ‘R) so this works for 0 since 0 is the 0th Fibonacci number;
\$\endgroup\$
  • \$\begingroup\$ Umm, this looks too much like my answer... \$\endgroup\$ – Erik the Outgolfer Jun 14 '17 at 17:20
  • \$\begingroup\$ Oh, I golfed mine down to yours, except mine works for 3 :) \$\endgroup\$ – Jonathan Allan Jun 14 '17 at 17:22
  • \$\begingroup\$ Oh whoops...Fibonacci is weird. (btw deleted my answer then if u say so) \$\endgroup\$ – Erik the Outgolfer Jun 14 '17 at 17:26
  • \$\begingroup\$ Are you sure about that last note? When I run the Fibonacci atom on a list starting from 0, 0 is included in the output. \$\endgroup\$ – scatter Jun 14 '17 at 18:08
  • 1
    \$\begingroup\$ It doesn't appear to be relevant based on the wording of the challenge, but if you use the count atom with 1 as your argument on the list of Fibonacci numbers the result is 2 (not 1). \$\endgroup\$ – FryAmTheEggman Jun 14 '17 at 18:55
4
\$\begingroup\$

C#, 109 bytes

bool f(int n){int[]i=new[]{0,1,0};while(i[0]<n||i[1]<n){i[i[2]%2]=i[0]+i[1];i[2]++;}return n==i[0]||n==i[1];}

Definitely could be improved, but I didn't have time.

\$\endgroup\$
  • \$\begingroup\$ Welcome to PPCG! \$\endgroup\$ – Martin Ender Jun 14 '17 at 19:36
  • 1
    \$\begingroup\$ I wrote my own answer only to realize that it was the same as yours. You can use lambda expressions and simple variables to get this: n=>{int a=0,b=1,c=0;while(a<n&b<n)if(++c%2>0)a=a+b;else b=a+b;return a==n|b==n;} (just 80 bytes). Try it online! \$\endgroup\$ – Charlie Jun 14 '17 at 20:08
  • 1
    \$\begingroup\$ @CarlosAlejo Save a further 2 bytes on that with a+=b instead of a=a+b and b+=a instead of b=a+b. \$\endgroup\$ – TheLethalCoder Jun 15 '17 at 8:18
4
\$\begingroup\$

><>, 21 19+3 = 24 22 bytes

i1\{=n;
?!\:@+:{:}(

Input is expected to be on the stack at program start, so +3 bytes for the -v flag.

Try it online!

This works by generating Fibonacci numbers until they are greater than or equal to the input number, then checking the last generated number for equality with the input. Outputs 1 if it was a Fibonacci number, 0 otherwise.

To ensure that 0 is handled correctly, the seed is -1 1 - the first number generated will be 0 rather than 1.

Thanks to @cole for pointing out that i can be used to push -1 onto the stack when STDIN is empty. Very clever!

Previous version:

01-1\{=n;
}(?!\:@+:{:
\$\endgroup\$
  • \$\begingroup\$ Now I feel stupid for wasting bytes continuously checking each generated number along the way. Nicely done! \$\endgroup\$ – Emigna Jun 16 '17 at 8:56
  • 1
    \$\begingroup\$ 22 bytes using i instead of 01-. \$\endgroup\$ – cole Jan 21 '18 at 1:43
  • \$\begingroup\$ @cole of course, using i as -1 when there is no input to STDIN, I'd not considered that. Nicely done! \$\endgroup\$ – Sok Jan 21 '18 at 22:54
4
\$\begingroup\$

ZX81 BASIC 180 151 100 ~94 tokenized BASIC bytes

With thanks to Moggy on the SinclairZXWorld forums, here is a much neater solution that saves more bytes.

 1 INPUT I
 2 FOR F=NOT PI TO VAL "1E9"
 3 LET R=INT (VAL ".5"+(((SQR VAL "5"+SGN PI)/VAL "2")**I)/SQR VAL "5")
 4 IF R>=I THEN PRINT F=R
 5 IF R<I THEN NEXT F

This will output 1 if a Fibonacci number is entered, or zero if not. Although this saves bytes, it's much slower than the old solutions below. For speed (but more BASIC bytes) remove the VAL wrappers around the string literal numbers. Here is the old(er) solutions with some explanations:

 1 INPUT A$
 2 LET A=SGN PI
 3 LET B=A
 4 LET F=VAL A$
 5 IF F>SGN PI THEN FOR I=NOT PI TO VAL "1E9"
 6 LET C=A+B
 7 LET A=B
 8 LET B=C
 9 IF B>=F THEN GOTO CODE "£"
10 IF F THEN NEXT I
12 PRINT STR$(SGN PI*(B=F OR F<=SGN PI)) AND F>=NOT PI;"0" AND F<NOT PI

The amendments above saves further BASIC bytes to condensing the IF statements into a single PRINT in line 12; other bytes were saved by using the VAL keyword and, and using GOTO CODE "£", which in the ZX81 character set is 12. Strings save more bytes over numbers as all numeric values are stored as floats so therefore take more space on the VAR stack.

enter image description here

\$\endgroup\$
  • \$\begingroup\$ Actually, I could save another 6 tokenized BASIC bytes by removing line 6 altogether and changing line 5 to 5 IF R<F THEN NEXT I - my bad! \$\endgroup\$ – Shaun Bebbers Feb 4 at 23:56
3
\$\begingroup\$

Mathematica, 37 bytes

!Fibonacci@n~Table~{n,0,#+1}~FreeQ~#&

-4 bytes from @ngenisis

\$\endgroup\$
  • \$\begingroup\$ Fibonacci[0] gives 0, so you can save 4 bytes by including 0 in the Table range. You can save another byte using infix notation for Table: !Fibonacci@n~Table~{n,0,#+1}~FreeQ~#& \$\endgroup\$ – ngenisis Jun 14 '17 at 18:55
3
\$\begingroup\$

MATL (16 bytes)

2^5*4-t8+hX^tk=s

Try it online!

Not the golfiest solution, but wanted to use the direct method of checking if "5*x^2+/-4" is a perfect square.

Explanation:

2^5*    % 5 times the input squared
4-      % push the above minus 4
t8+     % push the above plus 8 (+4 overall)
hX^     % concatenate them into an array and then take the sqrt().
tk      % push a copy of the array that is rounded using floor().
=       % test if the sqrt's were already integers
s       % sum the results, returns 0 if neither was a perfect square.

Note:

In the "0" case it returns "2" because both 4 and -4 are perfect squares, same with 1 which produces "1 1". Consider any non-zero output as "truthy", and 0 as "falsy".

\$\endgroup\$
3
\$\begingroup\$

Pari/GP, 32 bytes

n->!prod(x=0,n+1,fibonacci(x)-n)

Try it online!

\$\endgroup\$
3
\$\begingroup\$

C# (.NET Core), 51 bytes

bool f(int n,int a=0,int b=1)=>a<n?f(n,b,a+b):a==n;

Try it online!

-6 bytes thanks to @Oliver!

This solution uses a pretty straightforward recursive function.

  • The variable n is the number to be tested.
  • The variables a and b are the 2 most recent numbers in the sequence.
  • Checks if the first of the 2 most recent number is less than input. When this is the case, a recursive call is made to the next numbers in the series.
  • Otherwise, check whether the first number is equal to input and return the result.

The TIO link demonstrates this working for 1134903170 which exceeds the maximum value required by the challenge.

\$\endgroup\$
  • \$\begingroup\$ It's nice to see C# solutions lately :) - I think you can simply check if a<n for 51 bytes \$\endgroup\$ – Oliver Jan 23 at 0:07
  • \$\begingroup\$ Thanks! And nice tip :) \$\endgroup\$ – dana Jan 23 at 0:22
2
\$\begingroup\$

Jelly, 5 bytes

ȷḶÆḞi

Try it online!

Returns 0 for non-Fibonacci numbers, and the 1-indexed position of the number in the Fibonacci sequence for Fibonacci numbers.

Explanation:

ȷḶÆḞi
ȷ        The literal number 1000
 Ḷ       Range [0,1,...,999]
  ÆḞ     Get the ith Fib number; vectorizes [1,1,2,3,5,...,<1000th Fib number>]
    i    Get the first index of element in list, or 0 if not found
\$\endgroup\$
  • \$\begingroup\$ Doesn't work for 0. \$\endgroup\$ – Okx Jun 14 '17 at 17:23
  • \$\begingroup\$ @ComradeSparklePony Are you sure? That works for me. \$\endgroup\$ – scatter Jun 14 '17 at 17:26
  • 1
    \$\begingroup\$ Doesn't work for 0 or anything bigger than 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875. \$\endgroup\$ – Erik the Outgolfer Jun 14 '17 at 17:27
  • 1
    \$\begingroup\$ @Mr.Xcoder General consensus is that you must be able to handle what your natural datatype supports, and Jelly supports arbitrary-precision integers. \$\endgroup\$ – Erik the Outgolfer Jun 14 '17 at 17:28
  • 1
    \$\begingroup\$ Still doesn't work for anything over 26863810024485359386146727202142923967616609318986952340123175997617981700247881689338369654483356564191827856161443356312976673642210350324634850410377680367334151172899169723197082763985615764450078474174626. \$\endgroup\$ – Erik the Outgolfer Jun 14 '17 at 17:30
2
\$\begingroup\$

Dyalog APL, 17 bytes

0∊1|.5*⍨4 ¯4+5××⍨

Try it online!

\$\endgroup\$
2
\$\begingroup\$

R, 43 40 bytes

pryr::f(x%in%DescTools::Fibonacci(0:45))  

pryr::f creates a function:

function (x) 
x %in% DescTools::Fibonacci(0:45)

Uses DescTools::Fibonacci to create the first x+1 fibonacci numbers and checks for inclusion. x+1 because the third fibnum is 2, and that wouldn't be enough to check for inclusion of 3.

Luckily Desctools::Fibonacci(0)=0, so that is a nice freebee.

-3 bytes thanks to MickyT

\$\endgroup\$
  • \$\begingroup\$ -1:x+1 will save you a byte, but 0:45 will save you three and cover the required range \$\endgroup\$ – MickyT Jun 14 '17 at 20:39
  • \$\begingroup\$ @MickyT Oh, I must've overlooked the required range specification. Thanks :) \$\endgroup\$ – JAD Jun 14 '17 at 20:42
  • \$\begingroup\$ An alternative approach, only 36 bytes: pryr::f(any(!(5*n^2+c(-4,4))^.5%%1)). \$\endgroup\$ – rturnbull Jun 16 '17 at 8:12
  • \$\begingroup\$ I got it down to 32 bytes, see here. \$\endgroup\$ – rturnbull Jun 16 '17 at 9:58
  • \$\begingroup\$ I'm not so familiar with code golf rules -- does allowing non-base packages make sense? I could write arbitrary R code into a package, install it, and run it the same way you have run the function from pryr. \$\endgroup\$ – mb7744 Jun 16 '17 at 12:58
2
\$\begingroup\$

Haskell, 31 bytes

f=0:scanl(+)1f
(`elem`take 45f)

Try it online! This exploits the fact that the input will be in the range from 0 to 1,000,000,000, hence we need to check only the first 45 Fibonacci numbers. f=0:scanl(+)1f generates an infinite list of Fibonacci numbers, take 45f is the list of the first 45 Fibonacci numbers and elem checks whether the input is in this list.


Unrestricted version: 36 bytes

f=0:scanl(+)1f
g n=n`elem`take(n+3)f

Try it online! For any n, taking the first n+3 Fibonacci numbers will guarantee that n will be in this list if it's a Fibonacci number.

Note that this approach is incredible inefficient for high numbers that are not Fibonacci numbers, because all n+3 Fibonacci numbers need to be computed.

\$\endgroup\$
2
\$\begingroup\$

PHP, 44 bytes

for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;

Try it online!

PHP, 58 bytes

for($x=0,$y=1;$x<$argn;$x=$y,$y=$t)$t=$x+$y;echo$x==$argn;

Try it online!

\$\endgroup\$
  • 2
    \$\begingroup\$ Golfed more: for(;0>$s=$x-$argn;)$x=+$y+$y=$x?:1;echo!$s;. \$\endgroup\$ – user63956 Jun 15 '17 at 3:43
  • \$\begingroup\$ @user63956 Thank You for the learning effort with the chaining variables assignment \$\endgroup\$ – Jörg Hülsermann Jun 15 '17 at 10:45
2
\$\begingroup\$

Javascript (ES6 without the ** operator), 44 bytes

f=(x,c=x*(Math.sqrt(5)-1)/2%1)=>x*(c-c*c)<.5

Relies on the ratio between successive Fibonacci numbers approaching the golden ratio. The value of c is the fractional part of the input divided by the golden ratio - if the input is Fibonacci then this will be very close to 1 and the value of c-c² will be very small.

Not as short as some of the other JS answers but runs in O(1) time.

\$\endgroup\$
  • \$\begingroup\$ Are you sure it is exact? \$\endgroup\$ – peterh Sep 14 '17 at 0:01
  • \$\begingroup\$ Doesn't work for the fibonacchi number 16558014 \$\endgroup\$ – Black Owl Kai Jan 21 at 14:12
2
\$\begingroup\$

Julia 0.4, 29 bytes

!m=in(0,sqrt(5*m*m+[4,-4])%1)

Try it online!


If this isn't how you do a Julia answer, let me know. I'm unsure of how input works on TIO.

\$\endgroup\$
  • 1
    \$\begingroup\$ You'd have to make it a regular function (counting !m=) or a lambda (counting m->). More importantly, this fails for 0 as is. \$\endgroup\$ – Dennis Jun 14 '17 at 18:55
2
\$\begingroup\$

Java, 72 69 68 63 59 55 50 49 bytes

n->{int a=0,b=1;for(;a<n;a=b-a)b+=a;return a==n;}

Test it yourself!

Alternative (still 49 bytes)

n->{int a=0,b=1;for(;a<n;b=a+(a=b));return a==n;}

Not very original: it's the plain and basic iterative version.

This works for numbers up to 1,836,311,903 (47th fibonacci number) included. Above that, the result is undefined (including a potential infinite loop).

Thanks to Kevin Cruijssen and David Conrad for helping golfing :)

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice approach. Btw, you can golf a byte by changing n==0 to n<1. In the question it states "A non-negative integer between 0 and 1,000,000,000". \$\endgroup\$ – Kevin Cruijssen Jun 15 '17 at 10:45
  • 1
    \$\begingroup\$ @KevinCruijssen I golfed not 1, but 5 bytes with that clause! :-P Thanks, I hadn't noticed it. \$\endgroup\$ – Olivier Grégoire Jun 15 '17 at 11:12
  • 1
    \$\begingroup\$ You don't need a temp variable for the Fibonacci sequence. You can calculate successive pairs with b+=a;a=b-a; \$\endgroup\$ – David Conrad Jun 16 '17 at 7:31
  • 1
    \$\begingroup\$ You're doing black magic, @DavidConrad! I'm telling you! Black magic! :) \$\endgroup\$ – Olivier Grégoire Jun 16 '17 at 7:40
2
\$\begingroup\$

Common Lisp, 61 54 bytes

(defun f(x)(do((a 0 b)(b 1(+ a b)))((>= a x)(= a x))))

Try it online!

The reduction in size with respect to the previous version:

(defun f(x)(do((a 0 b)(b 1 c)(c 1(+ b c)))((>= a x)(= a x))))

was triggered by the idea that to generate the sequence of the Fibonacci numbers only two variables are necessary, not three.

\$\endgroup\$
2
+100
\$\begingroup\$

Alchemist, 205 134 bytes

Big thanks to ASCII-only for rather clever merging of states, saving 71 bytes!!

_->In_x+c+u
u+b->u+a+d
u+0b->v
v+c->v+b+d
v+0c->w
w+a+x->w+y
w+0a+0x->Out_"1"
w+a+0x->Out_"0"
w+0a+x+y->w+2x
w+0a+0y+d->w+c
w+0d+0a->u

Try it online or verify in batch!

Ungolfed

# read input, initialize (c = 1)
_ -> In_x + c + s0

# a,d <- b
s0 +  b -> s0 + a + d
s0 + 0b -> s1

# b,d <- c
s1 +  c -> s1 + b + d
s1 + 0c -> s2

s2 +  a +  x -> s2 + y            # y <- min(a,x)
s2 + 0a + 0x -> Out_"1"           # if (a == x): was Fibonacci
s2 +  a + 0x -> Out_"0"           # if (a >  x): stop (we exceeded target)
s2 + 0a +  x +  y -> s2 + 2x      # if (a <  x): x += a (since y = a) / restore x
s2 + 0a      + 0y +  d -> s2 + c  # once that's done; c <- d
s2 + 0a           + 0d->s0        # and finally loop
\$\endgroup\$
  • \$\begingroup\$ Wip: tio.run/##JcpBCsMgFATQvcfIdhCsB8i@qx5BjD/… \$\endgroup\$ – ASCII-only Jan 29 at 11:21
  • \$\begingroup\$ 139. you can remove some 0 checks for fewer bytes at the cost of nondeterminism \$\endgroup\$ – ASCII-only Jan 30 at 6:16
  • \$\begingroup\$ 129 \$\endgroup\$ – ASCII-only Jan 30 at 6:22
  • \$\begingroup\$ @ASCII-only: That's pretty nice! Fails for 0 though, but not adding the b-atom on initialization fixes it (and saves 2 bytes) :D Thanks \$\endgroup\$ – ბიმო Jan 31 at 15:16
1
\$\begingroup\$

Mathematica, 33 bytes

AtomQ@*InverseFunction[Fibonacci]
\$\endgroup\$
  • \$\begingroup\$ You can save a couple of bytes with @* (and then drop the final @#&) \$\endgroup\$ – Martin Ender Jun 14 '17 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\$

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.