# Fibonacci reversed!

## Introduction

We all know and love our Fibonacci sequence and have seen a myriad of challenge on it here already. However, we're still lacking a very simple case which this answer is going to provide: Reversed fibonacci! So given F_n your job is to find n.

## Specification

### Input

Your input will be a non-negative integer, which is guaranteed to be part of the fibonacci sequence.

### Output

The output must be a non-negative integer as well.

### What to do?

The introduction already said: Given a fibonacci number, output its index. Fiboancci number hereby is defined as F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) and you're given F(n) and must return n.

### Potential Corner Cases

0 is a valid in- and output.
If given "1" as input you may either output "1" or "2", as you prefer.
You may always assume that your input actually is a fibonacci number.
You may assume that the input is representable as a 32-bit signed integer.

### Who wins?

This is code-golf so the shortest answer in bytes wins!
Standard rules apply of course.

## Test-cases

0 -> 0
2 -> 3
3 -> 4
5 -> 5
8 -> 6
13 -> 7
1836311903 -> 46

• Slight nit-pick: shouldn't this be considered inverse fibonacci en.m.wikipedia.org/wiki/Inverse_function – Michael Jul 18 '16 at 0:17
• So, iccanobiF?! – user54200 Jul 18 '16 at 11:24
• @Michael this is not inverse Fibonacci, because there's no inverse to Fibonacci function because it is not injective (because the "1" appears twice). The reverse originally came from the idea of "reverse table look-ups" which is what I expected people to do here (e.g. I expected them to do it to solve the problem). – SEJPM Jul 18 '16 at 14:19
• The function here could be considered a right inverse of the "Fibonacci function" from the non-negative integers to the set of Fibonacci numbers. The existence of a right inverse does not imply injectivity. – Dennis Jul 18 '16 at 17:31
• @SEJPM: I kinda did expect a task like "write a program that spells out the fibonacci sequence backwards", though. – Bergi Jul 20 '16 at 3:58

## Actually, 1 byte

f


Yes, there's a builtin for this, since November 16, 2015.

Try it online

For fun, without the builtin, it's 9 bytes:

╗1F╜=╓i


Try it online!

Explanation:

╗1F╜=╓i
╗          push input to register 0
1F╜=╓   push list containing first value x (starting with x = 0) where:
F         fib(x)
╜=       is equal to the input
i  flatten the list

• I have one thought and one thought only when I see this: ಠ_ಠ – Addison Crump Jul 17 '16 at 19:51
• I don't really understand why you would "waste" a symbol for such a ridiculously specific purpose – Fatalize Jul 17 '16 at 19:54
• @Fatalize The Fibonacci and inverse Fibonacci functions were among the first that I added. Even now, there are 39 completely unused single-byte commands (and who knows how many overloads that could be utilized). The 256 symbols, combined with the fact that there are 5 types in Actually (Integer, Real, String, Iterable, Function), means there are up to 1280 possible unary functions, and 6400 possible binary functions. There's a lot of room for seemingly-useless commands. – user45941 Jul 17 '16 at 19:56
• @Mego Are you just trying to compete with Mathematica for the most builtins? – gcampbell Jul 18 '16 at 10:07
• Actually, it's just a byte... lol, love this language name. – nicael Jul 18 '16 at 20:45

# Mathematica, 25 bytes

InverseFunction@Fibonacci


Function. Pretty self-explanatory if you ask me.

# Python, 3634 32 bytes

lambda n:len(str(66*n**6))//1.24


### Previous versions:

f=lambda n:len(str(66*n**6))//1.24
f=lambda n:(n*n*7).bit_length()//1.4


## Explanation

The core idea is to invert the formula

fibonacci(n) ~ ( (1 + sqrt(5)) / 2)**n / sqrt(5)


which tells us that

log fibonacci(n) ~ n log((1 + sqrt(5)) / 2) - log(sqrt(5))


to get

f(n) ~ (log(n) + log(sqrt(5))) / log((1 + sqrt(5))/2)


The golfing optimizations are:

• Use len(str(n)) to compute log base 10 without importing log (old version used .bit_length() to compute log base 2)
• Raise n to a power, so that the approximation of the logarithm can distinguish between successive Fibonacci numbers
• Multiplying by a constant scales up the values to get them in the correct range

Then the divisor was truncated to as little precision as I could manage and the multiplier chosen to give the correct results for all 32-bit fibonacci numbers.

• it should be 32 bytes, because f= is not counted. – Leaky Nun Jul 18 '16 at 6:07
• As the comment above already said, anonymous functions/unnamed lambdas are allowed by default. Also, if you restrict your answer to Python 2 and require a long argument, lambda n:~-len(66*n**6)//1.24 should work. – Dennis Jul 18 '16 at 6:46

# 05AB1E, 3 bytes

Code:

ÅFg


Explanation:

ÅF   # Generate all Fibonacci numbers <= input.
g  # Get the length of this list.


Uses the CP-1252 encoding. Try it online!.

# Julia, 2726 18 bytes

!n=log(3n+.7)÷.48


This uses the inverse of Binet's formula, with just enough precision for 32-bit integers; it actually works up to F(153) = 42,230,279,526,998,466,217,810,220,532,898 > 2105.

Try it online!

### How it works

Binet's formula states the following.

Restricting F to the set of Fibonacci, the map n → Fn has a right inverse F → nF.

We have that

and all that is left to do is dealing with the edge case 0.

Since the input is restricted to 32-bit integers, we can use short decimal literals instead of the constants in the formula.

• log φ = 0.481211825059603447… ≈ 0.48

Unfortunately, 0.5 isn't precise enough.

• √5 = 2.2360679774997896964… ≈ 3

That might seem like an awful approximation at first glance, but we're taking logarithms and since log 3 - log √5 = 0.29389333245105…, the result before rounding will be off by a small constant factor.

• 0.5 ≈ 0.7

Because of the excess from the previous approximation, we could actually omit this term altogether and still get correct results for F > 0. However, if F = 0, the logarithm will be undefined. 0.7 turned out to be the shortest value that extends our formula to F = 0.

# Jelly, 14 11 bytes

5½×lØp+.Ḟ»0


Try it online!

This is my first ever Jelly answer! This uses the algorithm from the MATL answer. Thanks to Dennis for shaving off 3 bytes!

Explanation:

   lØp      # Log Base phi
5½          # Of the square root of 5
×         # Times the input
+     # Plus
.    # 0.5
Ḟ   # Floored


This gets the right answer, now we just need to handle the special case of '0'. With '0' as an arg, we get -infinity, so we return

»      # The maximum of
0     # Zero
# And the previous calculated value.

• +1 because the comments on the explanation are the end of a limerick. – Daniel Jul 18 '16 at 21:05

# JavaScript, 54506950 42 bytes

b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c


Surely it isn't going to win, just for fun :)

Ok, checking for zero consumes 19 bytes. WTF? Stupid-me.

Demo! To see the last test case, you have to scroll the console a bit.

a=b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c;
console.log('0: '+a(0));
console.log('2: '+a(2));
console.log('3: '+a(3));
console.log('5: '+a(5));
console.log('8: '+a(8));
console.log('13: '+a(13));
console.log('1836311903: '+a(1836311903));

Thanks @edc for shortening by 8 bytes.

• simple b=>{for(j=1,i=c=0;b-i;c++)i=j+(j=i);return c} 45, golfed b=>(j=>{for(i=c=0;b-i;c++)i=j+(j=i)})(1)|c 42. – edc65 Jul 17 '16 at 20:51
• @edc Wow, that's clever, thanks <3 – nicael Jul 17 '16 at 22:05

# Perl 6 33 30  27 bytes

{first *==$_,:k,(0,1,*+*...*>$_)}
{first *==$_,:k,(0,1,*+*...*)} {first$_,:k,(0,1,*+*...*)}

Try it

### Explanation:

# lambda with implicit ｢$_｣ parameter { first # find the first element$_,           # where something is equal to the block's argument
:k,           # return the key rather than the value

# of the Fibonacci sequence
( 0, 1, * + * ... * )
# ^--^ first two values
#       ^---^ lambda used to generate the next in the series
#             ^-^ generate until
#                 ^ Whatever
}


### Test:

#! /usr/bin/env perl6
use v6.c;
use Test;

# using the safer version that stops generating
# values bigger than the input
my &fib-index = {first $_,:k,(0,1,*+*...*>$_)}

my @tests = (
0 => 0,
2 => 3,
3 => 4,
5 => 5,
8 => 6,
13 => 7,
1836311903 => 46,
1836311904 => Nil, # this is why the safe version is used here
12200160415121876738 => 93,
19740274219868223167 => 94,
354224848179261915075 => 100,
);

plan +@tests + 1;

for @tests -> $_ ( :key($input), :value($expected) ) { cmp-ok fib-index($input), &[eqv], $expected, .gist } cmp-ok fib-index((0,1,*+*...*)[1000]), &[eqv], 1000, 'works up to 1000th element of Fibonacci sequence'  1..13 ok 1 - 0 => 0 ok 2 - 2 => 3 ok 3 - 3 => 4 ok 4 - 5 => 5 ok 5 - 8 => 6 ok 6 - 13 => 7 ok 7 - 1836311903 => 46 ok 8 - 1836311904 => Nil ok 9 - 12200160415121876738 => 93 ok 10 - 19740274219868223167 => 94 ok 11 - 354224848179261915075 => 100 ok 12 - works up to 1000th element of Fibonacci sequence  • You can replace first *==$_ with just first $_, because a number is a valid smart-matcher. – smls Feb 27 '17 at 18:43 • 24 bytes by using the ... operator instead of first – Jo King Aug 28 '19 at 22:56 # Jelly, 8 bytes 1+Ð¡0 ¢i  Try it online! Note that this approach is too inefficient for the last test case. ### How it works ¢i Main link. Argument: n ¢ Call the helper link niladically (i.e., without arguments). This yields the sequence of the first n positive Fibonacci numbers, i.e., [1, 1, 2, 3, 5, ...]. i Find the first index of n (1-based, 0 if not found). 1+Ð¡0 Helper link. No arguments. 1 Set the left argument to 1. 0 Yield 0. +Ð¡ Add both arguments, replacing the left argument with the sum and the right argument with the previous value of the left argument. Yield the array of all intermediate values of the left argument.  ## Pyke, 5 bytes .f.bq  Try it here! .f - first number where .b - fib(n) q - ^ == input  ## Python, 29 bytes g=lambda n:n>.7and-~g(n/1.61)  Recursively divides the input by the golden-ratio approximation 1.61 until it's below 0.7, and outputs the number of divisions. For 0, the code outputs False, which equals 0 in Python. This can be avoided for 2 bytes g=lambda n:n//.7and 1+g(n/1.61)  ## JavaScript (ES6), 39 33 bytes f=(n,j=0,k=1)=>n>j?f(n,k,j+k)+1:0  Even with ES7, the inverse Binet formula takes 47 bytes: x=>Math.log(x*5**.5)/Math.log(.5+1.25**.5)+.5|0 x=>Math.log(x*5**.5)/Math.log((1+5**.5)/2)+.5|0 x=>Math.log(x*(p=5**.5))/Math.log((1+p)/2)+.5|0  • Just distribute the log and precompute all constants... – charlie Jul 19 '16 at 17:33 • IMHO, if you call recursively the lambda by name, f(n,k,j+k), you should include the assignment f= and count it as +2 bytes. The rule for unnamed lambdas should not apply here. – charlie Jul 21 '16 at 12:48 • @charlie Sorry, I always forgot about that. Fixed. – Neil Jul 21 '16 at 13:27 ## Sage, 49 bytes lambda x,s=sqrt(5):x and int(log(x*s,(1+s)/2)+.5)  Thanks to TuukkaX for the suggestion about saving sqrt(5) as s to shave off a few bytes. This approach using an inverse of Binet's formula offers several improvements over the previous approach: it's faster (constant-time versus quadratic time), it actually works for larger inputs, and it's shorter! Python users may wonder why I'm using sqrt(5) instead of the shorter 5**.5 - it's because 5**.5 is computed with C's pow function, and loses precision due to floating point issues. Many mathematical functions (including sqrt and log) are overloaded in Sage to return an exact, symbolic value, which don't lose precision. • I don't know Sage at all but could you save bytes by holding the sqrt(5) in a variable and use it twice, instead of typing sqrt(5) twice? – Yytsi Jul 18 '16 at 11:27 # MATL, 14 bytes t?5X^*17L&YlYo  Try it online! This uses an inverse of Binet's formula, and so it's very fast. Let F denote the n-th Fibonacci number, and φ the golden ratio. Then The code uses this formula with two modifications: • Instead of adding 1/2 and then rounding down, the code simply rounds towards the nearest integer, which takes up fewer bytes. • Input F=0 needs to be treated as a special case. ### How it's done t % Take input F implicitly. Make a copy ? % If (copy of) F is positive 5X^ % Push sqrt(5) * % Multiply by F 17L % Push phi (predefined literal) &Yl % Two-input logarithm: first input is argument, second is base Yo % Round towards nearest integer % Else the input, which is 0, is left on the stack % End if implicitly % Display implicitly  • Alternate approach: O1G:"yy+]vGmfq – James Jul 18 '16 at 22:06 • 11 bytes: t?17L&YlXkQ – jimmy23013 Aug 31 '19 at 8:47 • @jimmy23013 Nice approach! You should definiely post that as a separate answer – Luis Mendo Aug 31 '19 at 10:42 • I don't think it is worth another answer, as it is just a way to remove the 5X^*. (I have done this before.) And I don't know MATL enough to possibly keep improving it. – jimmy23013 Aug 31 '19 at 17:12 # Python, 38 bytes f=lambda n,a=0,b=1:n^a and-~f(n,b,a+b)  Test it on Ideone. ## JavaScript, 22 bytes n=>Math.log(n)/.48+2|0  • I didn't think this would work when I saw it, but apparently -Infinity|0 is 0 in JavaScript. Go figure. – Dennis Jul 20 '16 at 16:43 • @Dennis: In JS, bitwise operators take only last 32 bits and -Infinity = FFF00000 00000000. I was glad to find out, it spares 3 bytes for not having to prepend an explicit zero test like n&&. Apart from that, the main purpose of |0 is a substitute for Math.trunc() (like ÷ in Julia). – charlie Jul 21 '16 at 12:38 # C, 62 58 bytes g(c,a,b){return c-a?g(c,b,a+b)+1:0;}f(c){return g(c,0,1);}  Detailed int g(int c, int a, int b) { if (c == a) { return 0; } else { return g(c, b, a+b) + 1; } } int f(c) { return g(c, 0, 1); }  # Java 7, 70 bytes int c(int n){int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;}  https://ideone.com/I4rUC5 • Welcome to PPCG, nice first answer! – Leaky Nun Jul 24 '16 at 7:20 • int c(int n){int a=0,b=1,c=0,t;for(;a<n;t=b,b+=a,a=t)c++;return c;} (not tested) – Leaky Nun Jul 24 '16 at 7:21 • int c(int n){int a=0,b=1,c=0;while(a<n){c++;b+=a;a=b-a;}return c;} (not tested) – Leaky Nun Jul 24 '16 at 7:31 • int c(int n){int a=0,b=1,c=0;for(;a<n;b+=a,a=b-a)c++;return c;} (not tested) – Leaky Nun Jul 24 '16 at 7:32 ## TSQL, 143 bytes Input goes in @n as in DECLARE @n INT = 1836311903; DECLARE @O BIGINT=0;WITH F(R,P,N)AS(SELECT @O,@O,@O+1 UNION ALL SELECT R+1,N,P+N FROM F WHERE N<=@n)SELECT MAX(R)FROM F OPTION(MAXRECURSION 0);  ## Haskell, 45 bytes f x=round$log(sqrt 5*x+0.9)/log((sqrt 5+1)/2)


# Sesos, 28 bytes

Hexdump:

0000000: 16f8be 766ef7 ae6d80 f90bde b563f0 7ded18 3ceffa  ...vn..m.....c.}..<..
0000015: b1c1bb af9f3f ff                                  .....?.


Try it online!

(Exponential time because in Sesos copying a number needs exponential time.)

Assembly used to generate the binary file:

set numin
set numout
get
jmp
sub 1
fwd 1
fwd 1
rwd 2
jnz    ;input input
fwd 4
add 1  ;input input 0 1
fwd 2
add 1  ;input input 0 1 0 1
rwd 4
jmp
jmp    ;input input-curr curr next iterations
sub 1
jnz    ;input 0 curr next iterations
fwd 3
jmp
sub 1
fwd 2
rwd 2
jnz    ;input 0 curr next 0 0 iterations+1
rwd 1
jmp
sub 1
fwd 1
fwd 1
rwd 2
jnz    ;input 0 curr 0 next next iterations+1
rwd 1
jmp
sub 1
fwd 1
sub 1
fwd 2
rwd 3
jnz    ;input 0 0 -curr next curr+next iterations+1
rwd 2
jmp
sub 1
fwd 2
fwd 1
rwd 3
jnz    ;0 0 input input-curr next curr+next iterations+1
fwd 3
jnz
fwd 3
put


# Java 8 61 bytes

Same as @dainichi answer only made shorter by using Java 8 lambdas. The answer is a valid rvalue expression.

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


Ungolfed:

interface F
{
int c(int n);
}

public class Main
{

public static void main(String[] args)
{
F f = n->{int a=0,b=1,c=0,t;while(a<n){c++;t=b;b+=a;a=t;}return c;};
}
}


# Pyth, 13 bytes

J1tf>=Z+~JZZQ


Test suite.

Approximation in Python 2:

Z=0;J=1;T=1;Q=input()
while not J+Z>Q:
temp=J
J=Z
Z=temp+J
T += 1
print(T-1)


### alternative approach, 18 bytes

L?<b2bsyMtBtbs.IyG


Test suite.

This uses .I for inverse.

# Java 7, 89 bytes

int c(int n){int i=-1;while(f(++i)<n);return i;}int f(int n){return n<2?n:f(n-1)+f(n-2);}


Ungolfed & test cases:

Try it here. (Time limit exceeded for last test case, but it works in about 30-45 seconds on my PC.)

class Main{
static int c(int n){
int i = -1;
while(f(++i) < n);
return i;
}

static int f(int n){
return n < 2
? n
: f(n - 1) + f(n - 2);
}

public static void main(String[] a){
System.out.println(c(0));
System.out.println(c(2));
System.out.println(c(3));
System.out.println(c(5));
System.out.println(c(8));
System.out.println(c(1836311903));
}
}


Output:

0
3
4
5
6
46


## Perl 5.10, 48 bytes

Basically looking for the right n so that F(n) = input.

-a switch adds one byte.

$b++;while($_>$a){$c=$a;$a+=$b;$b=$c;$n++}say\$n


Try it here!

# J, 3227 17 bytes

i.~0,+/@(!|.)\@i.


Computes the first n Fibonacci numbers and then finds the index of n in that list.

## Usage

Extra commands are used for formatting multiple input/output. The last test case is omitted since it will require much more time to compute.

   f =: i.~0,+/@(!|.)\@i.
(,.f"0) 0 1 2 3 5 8 13
0 0
1 1
2 3
3 4
5 5
8 6
13 7


## Explanation

i.~0,+/@(!|.)\@i.  Input: n
i.  Get the range [0, 1, ..., n-1]
\@    For each prefix of that range
|.         Reverse the prefix
!           Find the binomial coefficient between each value in the original
prefix and the reversed prefix
+/@             Sum those binomial coefficients
This will create the Fibonacci numbers from 1 to n
0,              Prepend a 0 to the list of Fibonacci numbers
i.~                Find the index of n in that list and return


# Mathematica, 30 bytes

Round@Log[5^.5/2+.5,.8+5^.5#]&


Pure function; returns 2 if the input is 1.

Doesn't beat the other Mathematica entry, but showcases an unusual method: It's a (very cool) fact that the Nth Fibonacci number is the closest integer to [1/sqrt(5) times the Nth power of the golden ratio] ("Binet's formula").

Therefore the inverse function will be the base-[golden ratio] logarithm of [sqrt(5) times the Fibonacci number in question]. The .8+ is a hack to make sure we don't take the logarithm of 0, without screwing up the other values.

# Japt, 10 bytes

Lo æ@U¥MgX


Try it online!

## Explanation

Lo æ@U¥MgX
Lo           // Creates a range from 0 to 99
æ@        // Iterates through the range. Returns the first item X where:
U¥      //   Input ==
MgX   //   Xth Fibonacci number


# Brachylog, 14 bytes

≜∧0;1⟨t≡+⟩ⁱ↖?h


Try it online!

Takes input through the output variable and outputs through the input variable.

≜                 Label the input variable, trying 0, 1, -1, 2...,
0               then starting with 0
∧                (which is not necessarily the input variable)
;1             paired with 1,
⟨t≡ ⟩        replace the first element of the pair with the last element
⟨ ≡+⟩        and the last element of the pair with the sum of the elements
ⁱ↖?     a number of times equal to the input variable,
h    such that the first element of the pair is the output variable.


I'm not entirely sure why ≜ is necessary.

## Javascript (using external library) (84 bytes)

n=>_.Until((i,a)=>{l=a.length;if(a[l-1]!=n){return i<=1?i:a[l-1]+a[l-2]}}).Count()-1


• 53 Bytes by using code from here n=>{a=c=t=0,b=1;while(a<n){c++;t=b;b+=a;a=t}return c} Try it online! – pixma140 Aug 29 '19 at 13:17