7
\$\begingroup\$

Introduction

If \$\newcommand{\fib}{\operatorname{fib}}\fib(x)\$ calculates the \$x\$th Fibonacci number, write a program that calculates \$\fib(\fib(m))\$ for any integer value of \$m \ge 0\$. (Of course, there will be practical limits based on the language, so lesser limits are acceptable. Also, it's okay to stop at \$m = 20\$, even if the language could in theory go higher.) Any means of calculation is acceptable.

Challenge

Write a program or function, in as few bytes of code as possible, that for any given positive integer input, will return the same output as function fibfib in the following Python code:

fibs = [0, 1]

def fib(n):
    global fibs

    while len(fibs) <= n:
        fibs.append(fibs[-2]+fibs[-1])

    return fibs[n]

def fibfib(m):
    return fib(fib(m))

You do not have to use the same or a similar algorithm; the output just has to be the same.

Example Input and Output

 0 -> 0
 1 -> 1
 2 -> 1
 3 -> 1
 4 -> 2
 5 -> 5
 6 -> 21
 7 -> 233
 8 -> 10946
 9 -> 5702887
10 -> 139583862445
15 -> 13582369791278266616906284494806735565776939502107183075612628409034209452901850178519363189834336113240870247715060398192490855
20 -> 2830748520089123910580483858371416635589039799264931055963184212634445020086079018041637872120622252063982557328706301303459005111074859708668835997235057986597464525071725304602188798550944801990636013252519592180544890697621702379736904364145383451567271794092434265575963952516814495552014866287925066146604111746132286427763366099070823701231960999082778900856942652714739992501100624268073848195130408142624493359360017288779100735632304697378993693601576392424237031046648841616256886280121701706041023472245110441454188767462151965881127445811201967515874877064214870561018342898886680723603512804423957958661604532164717074727811144463005730472495671982841383477589971334265380252551609901742339991267411205654591146919041221288459213564361584328551168311392854559188581406483969133373117149966787609216717601649280479945969390094007181209247350716203986286873969768059929898595956248809100121519588414840640974326745249183644870057788434433435314212588079846111647264757978488638496210002264248634494476470705896925955356647479826248519714590277208989687591332543300366441720682100553882572881423068040871240744529364994753285394698197549150941495409903556240249341963248712546706577092214891027691024216800435621574526763843189067614401328524418593207300356448205458231691845937301841732387286035331483808072488070914824903717258177064241497963997917653711488021270540044947468023613343312104170163349890
\$\endgroup\$
6
  • 7
    \$\begingroup\$ This is A007570 in the OEIS. \$\endgroup\$
    – Giuseppe
    May 20 at 18:21
  • 6
    \$\begingroup\$ This isn't a duplicate; the linked question is just fib(x); this is fib(fib(x)). \$\endgroup\$
    – Someone
    May 21 at 1:21
  • 6
    \$\begingroup\$ This is a duplicate, because every answer to the linked fibonacci challenge can be trivially modified to give an answer to this challenge (just apply the function twice), and every answer to this challenge can be trivially modified in reverse (just remove the code which applies the function twice). They are not interestingly distinct enough challenges. \$\endgroup\$
    – pxeger
    May 21 at 6:06
  • 6
    \$\begingroup\$ @pxeger I'm not 100% convinced of that. For example, the OEIS page links a paper which gives a direct recurrence for fib(fib(n)). An implementation of that may be competitive because it avoids the overhead of having to set up two separate functions which is significant in some languages. \$\endgroup\$
    – loopy walt
    May 21 at 14:17
  • 4
    \$\begingroup\$ I don't agree that it's a duplicate, and don't agree with @pxeger's reasoning. Answers that output the infinite sequence in the other question can't be easily modified. And just because an answer can be easily modified, it doesn't follow that it can be easily modified competitively. As @loopy walt points out, declaring a new fib(fib(x)) function can be longer than building a new function, and the likely chance to re-use of some code elements could provide some new golfing opportunities. \$\endgroup\$ May 21 at 14:44

24 Answers 24

8
\$\begingroup\$

Jelly, 4 3 bytes

ÆḞ⁺

Attempt This Online!

ÆḞ⁺
  ⁺ # Twice:
ÆḞ  # Nth fibonacci

-1 byte thanks to Unrelated String

05AB1E, 4 bytes

ÅfÅf

Try it online!

ÅfÅf
Åf   # Nth fibonacci
  Åf # Nth fibonacci

flax, 4 bytes

;f;f
;f;f
  ;f # Nth fibonacci
;f   # Nth fibonacci

Try it online!

Actually, 2 bytes

FF

Try it online!

FF
F  # Nth fibonacci
 F # Nth fibonacci
\$\endgroup\$
1
  • \$\begingroup\$ The Jelly can be 3: ÆḞ⁺ \$\endgroup\$ May 21 at 22:13
6
\$\begingroup\$

Factor + benchmark.fib3, 37 bytes

[ [ 0 ] [ 1 - fib 1 - fib ] if-zero ]

Try it online!

Huh?

Factor comes with a suite of benchmarks. One of these is to implement the fibonacci function in seven different ways. Naturally, fib is the shortest one of these; it has an off-by-one error, it doesn't handle 0 correctly, and it's very slow because it uses the naive recursive algorithm.

Regardless of these problems, fixing them is still shorter than rolling our own. If we were to do so, however, it would only cost 3 more bytes:

Factor + combinators.extras, 40 bytes

[ [ 0 1 rot [ tuck + ] times . ] twice ]

Try it online!

\$\endgroup\$
5
\$\begingroup\$

Wolfram Language (Mathematica), 20 bytes

Nest[Fibonacci,#,2]&

Try it online!

Slightly shorter than the naive Fibonacci@Fibonacci@#&.

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

J, 49 45 bytes* *(you can actually score like 14 but that's boring)

-4 bytes thanks to ovs! (also thanks for this for 33 bytes, which uses newer J features!)

1{,@f=:{&(2 2 2$#:151x)`(-&2+/ .*&f<:)@.(>&1)

Try it online! Uses the matrix method mentioned on the OEIS page.

Explanation

This applies to the less golfed version, but fundamentally remains the same. I will continue to explain the less golfed version as it is more intuitive what is going on.

f=:{&(2 2 2$#:151x)`(-&2(+/ .*)&f<:)@.(>&1)
1{,@f

First, we define a helping verb f which recursively computes the matrix. f consists of two part: seed generation and recursion calculation. If the input is greater than 1 (>&1), then (@.) we calculate recursion; otherwise, we call the seed function. As I think it looks nicer by replacing the current f with the recursive verb $:, I shall explain that version, though they remain functionally equivalent.

f=:{&(2 2 2$#:151x)`(-&2(+/ .*)&$:<:)@.(>&1)
   <-----seed-----> <---recursion--->
   <-----seed----->                     if not(input > 1):
   {&(            )                       index the input into the following array
            #:151x                          get the bits of 151 (1 0 0 1 0 1 1 1)
      2 2 2$                                and create a 2x2x2 array
                                          the result is 1 0,:0 1 for 0, and 0 1,:1 1 for 1
                    <---recursion--->   if input > 1:
                    (-&2          <:)     compute input-2 and input-1
                        (     )&$:        call this verb on each, then
                         +/ .*            perform matrix multiplication

Since, however, f computes a matrix, and we are only interested in one member of that matrix, our actual verb is the last line 1{,@f, which simply takes the top-right element of the matrix.

* J, 14 bytes

(+/@:!&i.-)^:2

Try it online!

Of course, the first highlighted method is much longer than taking the trivial approach of modifying the existing shortest Fibonacci in J thanks to @miles and applying it twice. While this approach is about ~30x slower than the first, it's the length which matters. Nonetheless, I consider it trivial, which is why it is not the most-featured solution in my answer.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ You don't need the parentheses around the matrix multiplication and you can actually inline the definition of f \$\endgroup\$
    – ovs
    May 22 at 6:55
  • \$\begingroup\$ Nice to see someone use the matrix method--now to wait until there's a language where it might maybe be the shortest \$\endgroup\$ May 22 at 7:48
  • 1
    \$\begingroup\$ 33 with ^: instead of recursion, requires newer J than on TIO for the direct definition. Maybe a tacit version would be shorter. \$\endgroup\$
    – ovs
    May 22 at 8:35
  • \$\begingroup\$ @ovs ah, right, the matrix multiplication is parsed with higher preference. good note about the inlining! i don't think i knew it was parsed like that. and... that new version of J looks like wizardry lol, i don't understand what's even going on in that one \$\endgroup\$ May 23 at 1:34
5
\$\begingroup\$

R, 50 bytes

function(n,s=5^.5,`?`=round)?((r=s/2+.5)^?r^n/s)/s

Try it online!

Adapted from J.Doe's answer to the Fibonacci function or sequence.
Based on the closed-form formula for the fibonacci sequence, applied to itself.
The chance to assign the function (round) and variable (s/2+.5) that will be re-used means that we can re-perform the closed-form calculation on itself for less bytes than a 'trivial' adaption of simply appending a 'do it twice' function ;g=function(n)f(f(n)) (even in R ≥4.1 where defining a new function can be much golfier using \ instead of function *).


Note that a shorter R solution to the older challenge is user5957401's answer, which can be further golfed-down to 25 23 bytes**: repeat show(F<-T+(T=F)). However, as a full program, this is less easy to 'do it twice'.
If we re-arrange it into function form (function(n){while(n<-n-1)T=F+(F=T);T}), we can exploit the fact that the answer is already assigned to a variable to conditionally return this, or run the function again on this, for 60 58 bytes: f=function(n,m=T){while(n<-n-1)T=F+(F=T);`if`(m,f(T,0),T)}.
This is again shorter than simply appending a 'do it twice' function, but longer than the closed-form approach above (although appending a 'do it twice' function wins in R ≥4.1 *).

Finally, plannapus's answer (golfed-down by Robert S.) used the classic recursive approach. When adapted to run twice this is only one byte longer than the modified shortest fibonacci answer, with 59 bytes: f=function(n)`if`(n<3,1,f(n-1)+f(n-2));g=function(n)f(f(n)).
Boringly, though, this one is just the 'trivial' adaptation of appending ;g=function(n)f(f(n)).

*Thanks to pajonk for pointing out the golfing differences when using R ≥4.1
**23-byte fibonacci function inspired by Giuseppe's answer here

\$\endgroup\$
2
  • \$\begingroup\$ Good job analyzing all the approaches! Worth noting, that some of the conclusions may be different in R>=4.1, where defining a function is less costly. \$\endgroup\$
    – pajonk
    May 21 at 19:06
  • \$\begingroup\$ @pajonk - Ah, that's a very good point. Indeed, that does change the ranking a bit, although the closed-form-on-itself still wins. This kind of subtlety is exactly what makes golfing interesting. Thanks for pointing it out. \$\endgroup\$ May 21 at 19:30
4
\$\begingroup\$

Haskell, 24 bytes

The single-Fibonacci part was borrowed from R. Martinho Fernandes.

map(f!!)f
f=0:scanl(+)1f

Try it online!

\$\endgroup\$
4
\$\begingroup\$

JavaScript (Node.js), 115 bytes

f=n=>n<4?n+3n>>2n:(f(--n)**2n-(u=-1n)**(F=y=>y<2?y:F(--y)+F(--y))(n-=2n)*f(--n)*f(n+=3n)-u**F(--n)*f(--n)**2n)/f(n)

Attempt This Online! (includes benchmark)

Way longer than Radvylf's, but is way, way, faster. ATO for Radvylf's with benchmark, which times out.

Formula found at this paper.

Python, 131 bytes

f=lambda n:n>3and(f(n-1)**2-(-1)**F(n-3)*f(n-4)*f(n-1)-(-1)**F(n-2)*f(n-3)**2)//f(n-3)or n+3>>2
F=lambda y:y>1and F(y-1)+F(y-2)or y

Attempt This Online!

Same concept.

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

Vyxal, 5 bytes

2(‹∆f

Try it Online!

How?

2(‹∆f
2(    # Execute twice:
  ‹   # Decrement to make this 0-indexed
   ∆f # Nth fibonacci number
\$\endgroup\$
2
  • \$\begingroup\$ Oh interesting, Vyxal's ∆f is 1, 1, 2, 3, 5, ...? \$\endgroup\$ May 20 at 18:15
  • \$\begingroup\$ @RadvylfPrograms Yep. Idk why. \$\endgroup\$
    – Steffan
    May 20 at 18:16
3
\$\begingroup\$

SageMath, 28 bytes

lambda n,f=fibonacci:f(f(n))

Try it online!

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

Husk, 4 bytes

‼!İf

Try it online!

‼     # twice = apply function twice:
 !    #   index = value at index (of input) of
  İ   #   infinite sequence of
   f  #   fiboncci numbers
\$\endgroup\$
3
\$\begingroup\$

MathGolf, 2 bytes

ff

Try it online!

ff
f  # Nth fibonacci
 f # Nth fibonacci
\$\endgroup\$
3
\$\begingroup\$

Python NumPy, 66 bytes

lambda n:ptp(x**ptp(x**n))
from numpy import*
x=mat("1 1;1 0","O")

Attempt This Online!

While this isn't really competitive (the numpy import is just too expensive, as is setting up the auxiliary matrix) I thought this is interesting. Perhaps it can be ported to one of the other matrix languages.

How?

The standard recurrence a,b <---| a+b,a can be conveniently expressed by the matrix \$ M = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \$. Doing n iterations then is as easy as taking the n-th power: $$ M^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} $$

Thus we could simply do (x**(x**n)[0,1])[0,1]. We save a few bytes using ptp instead which in turn uses that F_n = F_n+1 - F_n-1. (Note that this incorrectly returns 1 for input 0 because F_-1 breaks the pattern F_n <= F_n+1, so ptp does not pick the right elements in that case.).

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

Wolfram Language (Mathematica), 15 bytes

#@*#&@Fibonacci

Try it online!

      Fibonacci     fib
#@*#&@                fib ∘ fib (composition)
\$\endgroup\$
2
\$\begingroup\$

Python, 47 bytes

from sympy import*
lambda n,g=fibonacci:g(g(n))

Attempt This Online!

Without builtin:

Python, 52 bytes

lambda n:g(g(n))
g=lambda y:y>1and g(y-1)+g(y-2)or y

Attempt This Online!

Ruby, 39 bytes

->n{(g=->y{y>1?g[y-1]+g[y-2]:y})[g[n]]}

Attempt This Online!

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

Batch, 123 bytes

@set/af=h=0,g=i=1
@for /l %%a in (1,1,%1)do @set/aj=h+i,h=i,i=j
@for /l %%a in (1,1,%h%)do @set/ah=f+g,f=g,g=h
@echo %f%

Explanation: Regular Batch variable expansion with % happens before the line is parsed, so the %h% has to be on a separate line to the code that sets h, but set/a is a special case and can access the current value of variables so works fine inside a loop.

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

JavaScript (Node.js), 35 bytes

x=>(f=y=>y<2?y:f(--y)+f(--y))(f(x))

Simple recursive solution (now intended for use with bigints, thanks to Steffan for pointing out that's necessary).

\$\endgroup\$
7
  • \$\begingroup\$ You probably need to use BigInts, because JS can't reliably handle numbers over 2**53-1. It actually times out for n >= 10, though. My solution, which doesn't time out, needed BigInts to not show NaN and Infinity. \$\endgroup\$
    – Steffan
    May 21 at 18:12
  • \$\begingroup\$ it doesn't even cost bytes to change to bigint, just change y-1 and y-2 both to --y \$\endgroup\$
    – Steffan
    May 21 at 20:25
  • \$\begingroup\$ @Steffan Done, thanks! \$\endgroup\$ May 22 at 0:23
  • \$\begingroup\$ And all without a single bigint literal. claps. Even though you shouldn't need them, because you'd hit the recursion limit waayyy before hitting problems with int precision. \$\endgroup\$
    – emanresu A
    May 22 at 2:31
  • \$\begingroup\$ @emanresuA = fib(20) is 6765, so you need a recursive depth of 6765 to calculate fib(fib(20)) (which I assume is comfortably beyond int precision). Surely JavaScript has (or can be set to have) a recursion depth limit higher than that? \$\endgroup\$ May 22 at 7:20
2
\$\begingroup\$

C (gcc) with -lgmp and -m32, 266 265 259 241 bytes

  • -1 thanks to ceilingcat
  • -6 thanks to MackTuesday

As no native type supports f(f(20)), I used GMP for the math. Uses iteration to compute the Fibonacci sequence.

#import<gmp.h>
#define q mpz_set
f(i,r){mpz_t k,l,s,t;for(mpz_inits(k,l,s,t,0);mpz_cmp(k,i)<1;mpz_add_ui(k,k,1))mpz_cmp_ui(k,1)>0?mpz_add(l,s,t),q(s,t),q(t,l):q(mpz_get_ui(k)?t:s,k);q(r,t);}g(i,r){mpz_t a;mpz_init_set_ui(a,i);f(a,r);f(r,r);}

Unfortunately, TIO doesn't have the 32-bit version of GMP installed so it's 259 bytes in 64-bit mode:

#import<gmp.h>
#define q mpz_set
f(i,r)mpz_t i,r;{mpz_t k,l,s,t;for(mpz_inits(k,l,s,t,0);mpz_cmp(k,i)<1;mpz_add_ui(k,k,1))mpz_cmp_ui(k,1)>0?mpz_add(l,s,t),q(s,t),q(t,l):q(mpz_get_ui(k)?t:s,k);q(r,t);}g(i,r)mpz_t r;{mpz_t a;mpz_init_set_ui(a,i);f(a,r);f(r,r);}

Try it online!

Ungolfed (without GMP, assuming int is big enough):

int f(int i) {
  int j[2]={0}, k=0, l;

  for(; k<i+1; k++)
    if(k<2) j[k]=k;
    else {
      l=j[0]+j[1];
      j[0]=j[1];
      j[1]=l;
    }

  return j[1];
}

int g(int i) { return f(f(i)); }
\$\endgroup\$
1
  • \$\begingroup\$ You can shave off a few more bytes with "#define q mpz_set" and the appropriate substitutions. \$\endgroup\$ May 22 at 4:14
2
\$\begingroup\$

Octave, 32 bytes

@(n,m=[1 1;1 0])(m^(m^n)(2))(2);

Try it online!

Port of my Python answer.

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

Desmos, 49 45 bytes

pp-p~1
f(n)=(p^n-(1-p)^n)/5^{.5}
g(n)=f(f(n))

Just applies Binet's Formula twice. Did not include the last two test cases as the output is too large for Desmos to handle.

Try It On Desmos!

Try It On Desmos! - Prettified

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

Retina 0.8.2, 42 bytes

.+
$*
+`11(1*)
1$1,$1
,

+`11(1*)
1$1,$1
1

Try it online! Note: Very slow, so will probably time out on TIO for inputs more than 8. Explanation: Based on my Retina 0.8.2 answer to Fibonacci function or sequence.

.+
$*

Convert to unary.

+`11(1*)
1$1,$1

Recursively replace n with n-1 and n-2, until each unary integer has been replaced down to 1 and 0.

,

Sum the 1s in unary, resulting in the Fibonacci of the input.

+`11(1*)
1$1,$1

Calculate the Fibonacci of the Fibonacci.

1

Sum and convert to decimal.

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

Retina, 41 bytes

2{K`0,1
"$-1"+`\d+,(\d+)
$1,$.(*_$1*
,.+

Try it online! Link includes test cases. Explanation:

2{

Repeat the whole program twice.

K`0,1

Replace the input with the two integers 0 and 1.

"$-1"+`

Repeat the number of times given by the stage before the previous stage. On the first iteration this is the input, while on the second it is the result of the first loop.

\d+,(\d+)
$1,$.(*_$1*

Replace the first integer with the second and the second with their sum.

,.+

Delete the second integer.

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

Charcoal, 27 bytes

NθF²«≔E²κυFθ≔⟦⌈υΣυ⟧υ≔⌊υθ»Iθ

Try it online! Link is to verbose version of code. Explantion:

Nθ

Input n.

F²«

Repeat twice.

≔E²κυ

Start with the two integers 0 and 1.

Fθ

Repeat n times.

≔⟦⌈υΣυ⟧υ

Replace the first integer with the second and the second with their sum.

≔⌊υθ

Save the first integer for the next pass or the result.

»Iθ

Output the result.

Although the above code calculates the result quickly enough for inputs of n up to about 20, here is a 42-byte version which is fast even for large values of n:

≔⮌E²E³¬⁼ιλυFN⊞υE³ΣE²ΠE…⮌υ²§ξ⁺ν⊘⁺λπI§§υ±²¦¹

Try it online! Link is to verbose version of code. Explanation:

≔⮌E²E³¬⁼ιλυ

Start with \$ ((F_{F_0-1}, F_{F_0}, F_{F_0+1}), (F_{F_1-1}, F_{F_1}, F_{F_1+1})) \$ which is [[1, 0, 1], [0, 1, 1]].

FN

Repeat n times.

⊞υE³ΣE²ΠE…⮌υ²§ξ⁺ν⊘⁺λπ

Calculate \$ (F_{F_{i+2}-1}, F_{F_{i+2}}, F_{F_{i+2}+1}) \$ from the previous terms. There are a number of ways of doing this e.g. \$ F_{F_{i+2}-1} = F_{F_i-1}F_{F_{i+1}-1} + F_{F_i}F_{F_{i+1}} \$.

I§§υ±²¦¹

Output the middle term of the penultimate result which is \$ F_{F_n} \$ as desired.

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

Japt, 5 bytes

MgMgU

Try it here

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

Raku, 27 bytes

[o] {(0,1,*+*...*)[$_]}xx 2

Try it online!

  • 0, 1, *+* ... * is the lazy, infinite Fibonacci sequence.
  • [$_] looks up a number in the sequence by its index.
  • { ... } wraps the lookup in an anonymous function.
  • xx 2 replicates that function twice, producing a list of two elements.
  • [o] reduces that list with function composition.
\$\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.