30
\$\begingroup\$

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.

\$\endgroup\$
5
  • \$\begingroup\$ 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 \$\endgroup\$ Commented Aug 22, 2023 at 19:25
  • 3
    \$\begingroup\$ @noodleman that would be OK if any repeat of the string creates a single function that takes no input \$\endgroup\$
    – mousetail
    Commented Aug 22, 2023 at 19:30
  • \$\begingroup\$ May the program return the result by exit code? \$\endgroup\$
    – Arnauld
    Commented Aug 23, 2023 at 8:16
  • 1
    \$\begingroup\$ @Arnauld Yes, you can use any standard output method as long as you output exactly one unambiguous value \$\endgroup\$
    – mousetail
    Commented Aug 23, 2023 at 8:17
  • \$\begingroup\$ Great challenge \$\endgroup\$ Commented Aug 24, 2023 at 3:27

44 Answers 44

1
2
3
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Commented Aug 30, 2023 at 1:19
3
\$\begingroup\$

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.

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

Uiua, 16 bytes, no header/footer

&pf;⍥⊃⊂∘tag"""1"

Outputs in unary. Try it online! x3 (outputs 11) x6 (outputs 11111111)

Since Uiua prints the entire stack at the end of execution and there is no straightforward way to exit the program in the middle, I decided to print in unary so I can just accumulate all the outputs across iterations. A similar approach was done in my Cascade no-padding answer.

tag (a niladic function that initially evaluates to 0 and is incremented each time it is called) acts as the counter in other answers, allowing to generate the n-th term of the delayed Fibonacci sequence 1, 0, 1, 1, 2, 3, ..., whose cumulative sum is the Fibonacci sequence itself.

&pf;⍥⊃⊂∘tag"""1"
    ⍥⊃⊂∘tag"""1"  delayed Fibonacci generator:
              """1"   initial two terms 1 and 0 in unary
    ⍥     tag        repeat n times: (n = 0, 1, ..., repetition - 1)
      ⊃⊂∘           change [b a] with [b+a b] in unary
   ;               discard the next term
&pf                print without newline
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 14 bytes

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

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

        υ       Predefined empty list
       ¬        Is empty
      ∨         Logical Or
           υ    Predefined empty list
          ✂     Sliced from
             ²  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.

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

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!

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

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

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

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

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

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

\$\endgroup\$
2
  • \$\begingroup\$ This seems to output 2 numbers instead of 1 \$\endgroup\$
    – mousetail
    Commented Aug 25, 2023 at 13:06
  • \$\begingroup\$ Added 7 more bytes to print only 1 number. \$\endgroup\$ Commented Aug 25, 2023 at 18:17
2
\$\begingroup\$

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!

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Aug 24, 2023 at 16:02
2
\$\begingroup\$

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.

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

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)
\$\endgroup\$
2
\$\begingroup\$

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.

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

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.

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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