Repeat your program to print Fibonacci numbers

Question

Write a program fragment so that, when repeated N times it prints the Nth Fibonacci number. For example, if your program is print(x) then:

• print(x) should print 1
• print(x)print(x) should print 1
• print(x)print(x)print(x) should print 2
• print(x)print(x)print(x)print(x) should print 3
• print(x)print(x)print(x)print(x)print(x) should print 5
• etc.

First 2 items are 1 then each consecutive item in the sequence is the sum of the previous two.

You may include a non-repeated header and footer, but a smaller header and footer will always beat an answer with a larger sum of header+footer. For example, a 1000 byte answer with no header wins from a 20 byte answer with a 1 byte footer. However, a 0 byte header 20 byte body will win from both.

With header length being equal, smallest number of bytes, in each language, wins.

Tips

Output in unary
Use shell escape codes like \r to erase the previous print.
Use your languages implicit output feature

Example Submission

Python, 0 header/footer, 97 body

if"k"not in globals():k=["","x"];print("x",end="")
else:k.append(k[-1]+k[-2]);print(k[-3],end="")

Output in unary

Attempt This Online!

Comments are entirely valid, but solutions that don't use comments are extra impressive.

• noodle person: Could a submission be an anonymous function which outputs the nth fibonacci number when its body is repeated n times? Like if (a,b)=>a outputted 1, (a,b)=>a(a,b)=>a outputted 2, etc. would that be okay? Or should it be a full program
• mousetail: @noodleman that would be OK if any repeat of the string creates a single function that takes no input
• Arnauld: May the program return the result by exit code?
• mousetail: @Arnauld Yes, you can use any standard output method as long as you output exactly one unambiguous value
• thejonymyster: Great challenge

Answer 1

><>, 13 bytes

\\n;
1:
0@
 +

Try it online!

When repeated, it looks like this:

\\n;
1:
0@
 +\\n;
1:
0@
 +\\n;
1:
0@
 +

The first column sets up the stack, the second runs the Fibonacci loop, and the horizontal path prints and exits. Extra copies of 1 0s are ignored.

Answer 2

POSIX sh: (Dash, Bash, Zsh), ^{(削除) 42 36 (削除ここまで)} 32 bytes (0 bytes header/footer)

-6 bytes by switching to unary, -4 bytes by swapping n and n-1 to remove an ${empty-"fallback"}

set 1ドル2ドル ${1-1}
trap echo\ 1ドル 0

Try it online! (削除) Try it online! Try it online! (削除ここまで)

Zsh can save 1 byte by using trap '<<<1ドル' 0.

Explanation:

${var-string} substitutes "string" if $var is unset. On the first loop, 1ドル2ドル is elided, so the first positional argument is set by ${1-1}, which triggers its the unset-fallback to 1. On each subsequent loop, the first argument is a concatenation of the two, and the second argument is the first argument from the previous iteration.

We use trap [snippet] 0 to only output upon EXIT.

Answer 3

K (ngn/k), 13 bytes

 ://0,1+':*+0

Try it online!

There is a leading space. Similar strategy to my APL and J answers, but it was more tricky to find the equivalent for K.

Monadic + is "transpose". A scalar changes to a 1x1 matrix, and a list changes to a 1-row matrix. Then monadic * unwraps one layer to get a list in both cases.

:// is "apply :/ (rightmost element) until it converges". 0 :// is "apply the same thing zero times", which is essentially a no-op.

Answer 4

APL (Dyalog), 19 (削除) 29 (削除ここまで) bytes (削除) 1 byte (削除ここまで) No header (削除) and (削除ここまで) or footer

⊃{⍬≡⍵:1⋄(+/2↑⍵),⍵}⍬

Try it on TryAPL.org!

Thanks to Bubbler for pointing out that the header and footer could be incorporated into the function

With a header/footer, the body could be significantly shorter, but that's counter to the metric of success.

• Bubbler: You can include ⊃ and ⍬ in the repeated body so the entire code becomes ⊃{t←⍬≡⍵:,0⋄1=⍴⍵:1,0⋄(+/2↑⍵),⍵}⍬. It works because ⍬⊃ returns the RHS unchanged.

Answer 5

Lambda calculus (Ben Lynn's Nat), 46 bytes

(\n.n(\px.Sp(BxSB))K(KI)I)\f.(\l.SB(lf)f)\g.KI

Try it online! (Instructions: delete all the code there, copy the body n times and the footer on a single line, choose Nat, click Compile and then Run and see the Output.)

The observation that

Just realized that codes like I\f.f (a trailing lambda abstraction, which puts the next iteration inside its body) are accepted. This may change the conclusion about zero padding.

was correct, and there was indeed a solution without any padding.

The solution above has a structure of

x \f. y \g. z

and has the following property:

(\f. y \g. z) == 1
(\f. y \g. z x \f. y \g. z) == 2
(\f. y \g. z x \f. y \g. z x \f. y \g. z) == 3
...

z was chosen to be KI so that we can ignore x and the equation to solve simply becomes

(\f. y \g. n) == succ n == SBn

which can be solved with y = \l.SB(lf)f. Then, x should be a function that takes n and outputs nth fibonacci number. This is solved using 2014MELO03's construction of iterating a pair.

---

Lambda calculus (Ben Lynn's Nat), 39 bytes, 1 byte footer

(\a.a(\zbxf.f(a(SB)b)a)(\f.fI(KI)))(KI)

Footer:

K

Try it online! (Instructions: delete all the code there, copy the body n times and the footer on a single line, choose Nat, click Compile and then Run and see the Output.)

How I got to this solution

First, (削除) there is no solution without any header or footer (削除ここまで). This is because:

• any lambda term would be in the structure of x1 x2 .. xn
• one copy must evaluate to 1 = I
• but then 2 copies of the code evaluates to x1 x2 .. xn x1 x2 .. xn = I x1 x2 .. xn = x1 x2 .. xn = I, which is true for any number of copies, and 1 is clearly not fib(i) for larger i (number of copies).

_{This logic is false due to the subtlety of the grammar of Nat. See the no-padding solution at the top.}

Given this, I aimed to find a solution with a single combinator as the footer. I chose K because it fits particularly well here; specifically, if repetitions of x1 x2 .. xn evaluate to a pair, applying K on it extracts the first element. Then to simplify the problem, I assumed that n = 2, i.e. the repeating part is f x for some f and x. It can be an answer if it satisfies the following: ((x, y) refers to the Church pair of x and y.)

• f x evaluates to (1, 0).
• (a, b) f x = f a b x evaluates to (a+b, a).

Given that a in the second case is always a Church natural number ≥ 1, I decided to set x to zero (= KI). Then I can use a simple discriminator that returns u for 0 and v for 1 or greater:

0 (\z. v) u = u
a (\z. v) u = v -- when a >= 1

If the first argument is 0, we need to return (1, 0), so u = \f. f I (KI). Otherwise we take two more arguments b and x, ignore x, and construct a new pair \f. f (a succ b) a. This completes the construction of the answer above.

About choosing the interpreter and the LC language: I initially wanted to compile this to SKI calculus, but I didn't have a good one, and the three copies of a in a single lambda would surely make a mess. So I reached out for a regular LC interpreter instead, and found Nat. After getting some syntax errors (I was trying to use s for a function name), I realized that it does support SKIBC combinators out of the box, so I went with it.

Answer 6

Charcoal, 14 bytes

PI⌈⊞Oυ∨¬υΣ✂υ±2

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

 υ Predefined empty list
 ¬ Is empty
 ∨ Logical Or
 υ Predefined empty list
 ✂ Sliced from
 2 Literal integer `2`
 ± Count back from the end
 Σ Take the sum
 ⊞O Push to
 υ Predefined empty list
 ⌈ Take the maximum (i.e. the entry just added)
 I Cast to string
P Overwrite without moving the cursor

Try it online! Link is to 10 repetitions of the succinct code.

Answer 7

Python, (削除) 44 (削除ここまで) (削除) 40 (削除ここまで) 35 bytes (no header or footer)

-5 bytes, thanks to @CursorCoercer

simplified version of example code

a=1;b=0
print(end=a*"x")
a,b=b,a+b#

Attempt This Online!

2x, 3x, 4x

first few values

Python, 11 bytes body, 15 bytes header+footer

the trivial python solution

a,b=0,1
a,b=b,a+b
print(a)

Attempt This Online!

2x:

a,b=0,1
a,b=b,a+b
a,b=b,a+b
print(a)

Attempt This Online!

3x:

a,b=0,1
a,b=b,a+b
a,b=b,a+b
a,b=b,a+b
print(a)

Attempt This Online!

• CursorCoercer: 35 bytes

Answer 8

Go, 55 bytes (2 bytes footer)

import."fmt";func f(){a:="x";b:=""
Print(a);a,b=b,a+b//

}

Try it online!
Try it online! x2
Try it online! x3
Try it online! x4

Go, 30 bytes (8 bytes footer)

func()(b int){a:=1
a,b=b,a+b//

return}

Try it online!
Try it online! x2
Try it online! x3
Try it online! x4

-16 thanks to @JoKing

Answer 9

Befunge-98 (PyFunge), 16 bytes

#q_1\\:01p+01g5j

Try it online once

Try it online twice

Try it online three times

Try it online five times

Try it online ten times

Explanation

This outputs the result as an exit code. Most operating systems only show the least significant byte of this number (mod 256 on TIO), but as per the Funge spec, it's returning the full number. It would add a couple of bytes to print to stdout.

Below f1, f2 and f3 are three consecutive Fibonacci numbers.

Only run on first and last "loop":
#q_ Quit with 2nd on stack as exit code if top of stack is non-zero.
 1\ Push 1, swap with 2nd on stack (implicitly 0).
The main "loop", entering with f1 on top and f2 below:
 \ Swap top 2 of stack, f2 now on top.
 : Duplicate f2.
 01p Store f2 at (0,1) in funge space.
 + Add f1 and f2 to get f3.
 01g Get f2 from (0,1) in funge space.
 5j Skip the next 5 instructions.

#q_1\ is skipped for all copies of the code except the first. On the first one, the stack is empty (top of stack implicitly 0), so it continues to the right. At the end of the last copy, 5j just skips 5 whitespace and runs the first copy again, this time with the second-highest number generated on top (non-zero).

Answer 10

Haskell, 27 bytes body, 7 bytes footer

g=f!!1;f=[f!!1,sum f]where f=[0,1]

The last 7 bytes (f=[0,1]) is the footer.

Attempt This Online

• mousetail: This seems to output 2 numbers instead of 1
• ParsaAlizadeh: Added 7 more bytes to print only 1 number.

Answer 11

C++ (gcc), (削除) 143 (削除ここまで) 125 bytes

-18 bytes thanks to @ceilingcat

Explanation: it uses the constructor of a class to do the Fibonacci increment operation, and then sets up a variable number of global instances of that class to be initialized before main. The catch being that all those variables have to be named differently, and there's a bit of preprocessor magic needed to get the __LINE__ macro combined into the variable names.

int m,n=1;struct A{A(){m+=n;n=m-n;}};int main(){__builtin_printf("%d",m);}
#define Y(x)A a##x;
#define X(x)Y(x)
X(__LINE__)//

Try it online!

• Daniel Schepler: OK, I had the idea to create a header with #if __LINE__<2 which allowed a proper #include (or #import for golfing); but that ended up increasing the size significantly.

Answer 12

APL(Dyalog Unicode), ^{(削除) (削除ここまで)}11 bytes ^SBCS

⊃1,⍨2+/0,⍨⍬

Try it on APLgolf!

Inspired by boltcapt's answer. This constructs a list of fibonacci numbers in reverse, starting from empty list ⍬, and outputs the first element ⊃. When the program is repeated, ⍬⊃ returns the whole array on the right side unchanged.

1,⍨2+/0,⍨ when the current list contains f_n, f_{n-1}, ..., f_1
 (e.g. n=5: [5 3 2 1 1])
0,⍨ append 0 [5 3 2 1 1 0] (f_n, f_{n-1}, ..., f_1, f_0)
2+/ pairwise sum [8 5 3 2 1] (f_{n+1}, f_n, ..., f_2)
1,⍨ append 1 [8 5 3 2 1 1] (f_{n+1}, f_n, ..., f_1)

Answer 13

J, 11 bytes

]/0 1,2+/0円

Attempt This Online!

Similar to my APL solution. The fibonacci generator is the same, except that the list is now in increasing order. ]/y returns the rightmost element of y, but x]/y returns y unmodified.

x (f"a b)/ y evaluates the cartesian product of a-cells of x and b-cells of y. ] has default rank of infinity on both sides, so x (]"_ _)/ y takes whole x on the left and whole y on the right, and returns an array containing the single item x ] y, which is y.

Answer 14

sclin, 23 bytes

0 1.
tuck dup n>o +2@~

Try it here! Has a trailing newline.

Example:

0 1.
tuck dup n>o +2@~
0 1.
tuck dup n>o +2@~
0 1.
tuck dup n>o +2@~

Explanation

• 0 1 initial conditions
• tuck dup n>o store, output term
• + add
• 2@~ execute second line down (i.e. skip next line)

Pleasantly surprised that the line-based mechanics of sclin came in handy this time.