ooh spoilers

Sorry, I haven't been paying attention.  What is SoC again? Square of Code?  Like this?

```
^^5clet~^^5ccatcode~` 0~`,1
~`.2~`:6~`)13 def):1,~`:113
 gdef.~`'10) --, count2.)*%
*, interactionmode.)'('(:1%
;:2, unless ifnum:1'='0':1'
 expandafter( the numexpr:1
+:2;,:1. fi.-**0'(1;1*- bye
```

---

Serious version:

The above abuses TeX to produce the sequence with the smallest possible effort from my part.  The important part of the code boils down to:
```
\def\fib#1;#2{\unless\ifnum#1=0 #1
  \expandafter\x\the\numexpr#1+#2;{#1}\fi}
\fib1;1
```
`\fib` prints `#1` then does a recursive call of `\fib #1+#2;{#1}`, thus printing the next number in the sequence, rinse and repeat.  The stop condition abuses the fact that `\numexpr` returns zero on an `! Arithmetic overflow`, so it doesn't have to worry about maths: just crunch numbers until something explodes, then stop.  The Square of Code version contains some fancy manipulation of `\interactionmode` to make TeX hide the Arithmetic overflow error and finish the run successfully¹.

¹ Terms and conditions may apply.

I consider the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number) to start with terms 0 and 1 (the subsequent terms are therefore 1 and 2, so this doesn't change much as compared to a definition in which the first terms are 1 and 2—this only shifts the indices).

Following are four expandable ways to obtain the first 46 terms of the sequence (only 45 in the first implementation because it computes F_{n+2} *before* doing the termination test and, in case the test is negative, delivering F_{n+1}). The examples below use standard TeX arithmetic via `\count` registers; this is what limits the greatest term we can compute. The four implementations provided in this answer use tail recursion and are presented in increasing order of optimization.

# First implementation

In this implementation, we pass from step to step the remaining number of terms to deliver as an integer denotation (this is the first argument of `\fibo_next:nnn`).

```
\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% #1: number of values left to print
% #2: F_{n+1}
% #3: F_{n}.
\cs_new:Npn \fibo_next:nnn #1#2#3
  {
    \int_compare:nNnF {#1} = { 0 }
      {
        ,~ #3
        \fibo_next:ffn { \int_eval:n { #1-1 } } { \int_eval:n { #2 + #3 } } {#2}
      }
  }

\cs_generate_variant:Nn \fibo_next:nnn { ffn }

\cs_new:Npn \fibo_numbers:n #1
  {
    0 \fibo_next:ffn { \int_eval:n { #1-1 } } { 1 } { 1 }
  }

% Number of values to print (at least 1)
\NewExpandableDocumentCommand \fibo { m }
  {
    \fibo_numbers:n {#1}
  }

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 45 } } }

\ExplSyntaxOff

\begin{document}

\fibo{45}

\end{document}
```

![image.png](/image?hash=2062bcdd701230cb7505a89743c2483a1795f3760a76d985fd6d282cdeb2dd1e)

# Second implementation

Instead of using integer arithmetic to update the remaining number of terms to deliver and to compare it to zero, the following code leaves the desired number of `m` character tokens ahead in the input stream and gobbles one at each step (one could use virtually anything instead of `m`). The recursion stops when `\quark_if_recursion_tail_stop:N` finds the `\q_recursion_tail` quark after the last `m` has been consumed; then it gobbles everything up to and including `\q_recursion_stop`, which immediately follows `\q_recursion_tail` in our code.

```
\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
  {
    0
    % Initiate the recursion and add the trailing markers. Each step will eat
    % one 'm' until \__fibo_next:nnN reaches the \q_recursion_tail marker.
    \__fibo_numbers:f { \prg_replicate:nn { #1-2 } { m } }
  }

\cs_new:Npn \__fibo_numbers:n #1
  {
    \__fibo_next:nnN { 1 } { 1 }
    #1                   % a number of 'm' character tokens (possibly none)
    \q_recursion_tail \q_recursion_stop
  }

\cs_generate_variant:Nn \__fibo_numbers:n { f }

% #1: F_{n+1}
% #2: F_{n}
% #3: sentinel token (either 'm' or \q_recursion_tail)
\cs_new:Npn \__fibo_next:nnN #1#2#3
  {
    ,~ #2
    \quark_if_recursion_tail_stop:N #3
    \__fibo_next:fnN { \int_eval:n { #1 + #2 } } {#1}
  }

\cs_generate_variant:Nn \__fibo_next:nnN { f }

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
  {
    \fibo_numbers:n {#1}
  }

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}
```

![image.png](/image?hash=663994d61d5f7f1179b356f78ccbaa655f1778dedf5949a8d4a97c8f2cb55cce)

# Third implementation

This is almost the same as an [optimization of the previous code by Skillmon](https://topanswers.xyz/transcript?room=347&id=141537&year=2022&month=7#c141537). The main idea is to avoid all the termination tests performed on the third argument of `\__fibo_next:nnN` in the previous implementation. Instead, we generate a suitable number of `\__fibo_numbers_auxii:w` tokens before the recursion starts. Each of these will trigger the computation and delivery of a new term of the sequence. After the last `\__fibo_numbers_auxii:w` has been consumed, `\use_none_delimit_by_q_stop:w` is grabbed as the third argument of `\__fibo_numbers:wnN`; when expanded, it removes everything left thereafter in the input stream by the last expansion of `\__fibo_numbers:wnN`, up to and including the `\q_stop` token left by `\fibo_numbers:n`.

```
\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
  {
    0
    \exp_after:wN \__fibo_numbers:w
    \prg_replicate:nn { #1 - 2 } { \__fibo_numbers_auxii:w }
    \use_none_delimit_by_q_stop:w \q_stop
  }

\cs_new:Npn \__fibo_numbers:w { \exp_after:wN \__fibo_numbers_aux:w }

\cs_new:Npn \__fibo_numbers_aux:w { \__fibo_numbers:wnN 1; 1 }

% #1: F_{n+1}
% #2: F_{n}
% #3: either \__fibo_numbers_auxii:w or \use_none_delimit_by_q_stop:w
\cs_new:Npn \__fibo_numbers:wnN #1; #2#3
  {
    ,~ #2
     #3 #1 + #2 \scan_stop: ; {#1}
  }

\cs_new:Npn \__fibo_numbers_auxii:w
  {
    \exp_after:wN \exp_after:wN \exp_after:wN
    \__fibo_numbers:wnN \int_eval:w
  }

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
  {
    \fibo_numbers:n {#1}
  }

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}
```

Same output as the previous code.

# Fourth implementation

This is basically what Skillmon proposed [here](https://topanswers.xyz/transcript?room=347&id=141538#c141538)—I only performed some minor renaming and reformatting. This implementation is the same as the previous one, except that it spares a few expansion steps by directly using `\the\numexpr`[^note-on-the-numexpr] instead of `\int_eval:w` (the latter expands to `\tex_the:D \__int_eval:w` in one step, which is equivalent via aliases to `\the\numexpr`).

```
\documentclass{article}
%\usepackage{l3benchmark}

\ExplSyntaxOn

% Generate the first n Fibonacci numbers, separated by commas. n must be at
% least 2. This function is restricted-expandable (works inside \edef but not
% within f-expansion).
\cs_new:Npn \fibo_numbers:n #1
  {
    0
    \exp_after:wN \__fibo_numbers:w
    \prg_replicate:nn { #1 - 2 } { \__fibo_numbers_auxii:wnN }
    \use_none_delimit_by_q_stop:w \q_stop
  }

\cs_new:Npn \__fibo_numbers:w { \exp_after:wN \__fibo_numbers_aux:w }

\cs_new:Npn \__fibo_numbers_aux:w { \__fibo_numbers:wnN 1; 1 }

\cs_new_eq:NN \__fibo_numexpr:w \tex_numexpr:D

% #1: F_{n+1}
% #2: F_{n}
% #3: either \__fibo_numbers_auxii:w or \use_none_delimit_by_q_stop:w
\cs_new:Npn \__fibo_numbers:wnN #1; #2#3
  {
    ,~ #2
     #3 \int_use:N \__fibo_numexpr:w #1 + #2 \scan_stop: ; {#1}
  }

\cs_new:Npn \__fibo_numbers_auxii:wnN
  {
    \exp_after:wN \__fibo_numbers:wnN
  }

% Number of values to print (must be at least 2)
\NewExpandableDocumentCommand \fibo { m }
  {
    \fibo_numbers:n {#1}
  }

%\benchmark:n { \tl_set:Nx \l_tmpa_tl { \fibo_numbers:n { 46 } } }

\ExplSyntaxOff

\begin{document}

\fibo{46}

\end{document}
```

Same output as above.

[^note-on-the-numexpr]: Actually, `\int_use:N \__fibo_numexpr:w` where `\int_use:N` is an alias for `\the` and `\__fibo_numexpr:w` for `\tex_numexpr:D`, i.e. `\numexpr`.

*no spoiler to be seen*

I'm sure we will see some of the ultra efficient algos here soon, so here the simple way ~~(using the `\int_set_eq:NN` I learnt about this morning :) )~~:

```
\documentclass{article}

\begin{document}

Today’s challenge is to print as many Fibonacci numbers as you like

Short recap in case someone is not familiar with Fibonacci numbers:

Fibonacci numbers are a sequence in which each new term is generated by summing up the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

\ExplSyntaxOn

\int_new:N \l_sam_old_int
\int_new:N \l_sam_new_int

\int_set:Nn \l_sam_old_int { 1 }
\int_set:Nn \l_sam_new_int { 2 }

\int_step_inline:nn {43}
{ 

  \par \int_use:N \l_sam_old_int
  
  \int_set:Nn \l_sam_new_int { \l_sam_new_int + \l_sam_old_int } 
  \int_set:Nn \l_sam_old_int { \l_sam_new_int - \l_sam_old_int }
  
}

\ExplSyntaxOff

\end{document}
```

No idea for a spoiler-less introduction.

This is an implementation that calculates the *n*-th Fibonacci number directly (but doesn't produce a sequence of them). It uses fast matrix exponentiation for the calculation. This is based on Python code I found [here](https://stackoverflow.com/a/23462371/6783373).

More than the first 45 Fibonacci numbers can't be produced by TeX integers. You can change `\__fib_eval:n` to use `\fp_eval:n` instead, but then you'll get problems with floating point precision for bigger Fibonacci numbers as well.

```
\documentclass{article}

\ExplSyntaxOn
\cs_new_eq:NN \__fib_eval:n \int_eval:n
\cs_new:Npn \__fib_to_bin:n
  { \exp_after:wN \use_none:n \exp:w \exp_end_continue_f:w \int_to_bin:n }
\NewExpandableDocumentCommand \fib { m }
  {
    \exp_last_unbraced:Ne \__fib:nnnN { 1 1 0 \__fib_to_bin:n {#1} }
      \q_recursion_stop
  }
\cs_new:Npn \__fib:nnnN #1#2#3#4
  {
    \use_none_delimit_by_q_recursion_stop:w #4 \__fib_done:w \q_recursion_stop
    \exp_args:Nf \__fib:nnnnN { \__fib_eval:n { #2 * #2 } } {#1} {#2} {#3} #4
  }
\cs_new:Npn \__fib:nnnnN #1#2#3#4
  {
    \exp_last_unbraced:Ne \__fib_aux:nnnnN
      {
        { \__fib_eval:n { #2 * #2 + #1 } }
        { \__fib_eval:n { (#2 + #4) * #3 } }
      }
      {#1} {#4}
  }
\cs_new:Npn \__fib_aux:nnnnN #1#2#3#4#5
  {
    \token_if_eq_charcode:NNTF #5 1
      {
        \exp_last_unbraced:Ne \__fib:nnnN
          {
            { \__fib_eval:n {#1 + #2} }
          }
          {#1}
          {#2}
      }
      {
        \exp_last_unbraced:Ne \__fib:nnnN
          {
            {#1}
            {#2}
            { \__fib_eval:n { #4 * #4 + #3 } }
          }
      }
  }
\cs_new:Npn \__fib_done:w #1 \__fib:nnnnN #2#3#4#5 \q_recursion_stop {#4}
\ExplSyntaxOff

\begin{document}
\ExplSyntaxOn
\int_step_inline:nn { 45 } { \fib{#1}~ }
\ExplSyntaxOff
\end{document}
```

![soc5-fibonacci-1.png](/image?hash=6123a304e3c217890cba555e3a6690ad81a43d3ae02c7ed2e931f63b4ccad8d0)

With lualatex:

```
\documentclass{article}
\usepackage{luacode}
\begin{luacode}
function fibo(max)
  tex.print("Fibonacci Numbers \\par")
  local a = 0
  local b = 1
  tex.print("0, 1, ")
  for n = 1, max do
     sum = a + b
     a = b
     b = sum     
     tex.print(tostring(sum)..", ")
  end
end
\end{luacode}
\def\fibonacci#1{\directlua{fibo(#1)}}

\begin{document}
\fibonacci{46}	
\end{document}
```