# The half-step of Fibonacci

## Challenge

Implement the 1-indexed sequence A054049, which starts like this:

1, 2, 3, 6, 13, 5, 9, 377, 21, 11,
89, 14, 8, 233, 16, 987, 18, 2584, 20, 6765,
55, 23, 28657, 25, 75025, 27, 196418, 29, 514229, 31,
1346269, 33, 3524578, ...


This sequence is the lexicographically smallest sequence of positive integers, so that indexing into the sequence twice yields the regular Fibonacci sequence:

$$a(a(1)) = a(1) = 1 \\ a(a(2)) = a(2) = 2 \\ a(a(3)) = a(3) = 3 \\ a(a(4)) = a(6) = 5 \\ a(a(5)) = a(13) = 8 \\ a(a(6)) = a(5) = 13 \\ a(a(7)) = a(9) = 21 \\ \vdots$$

The value of $$\a(34)\$$, the first term that does not fit into the OEIS page, is equal to $$\F(377+1)\$$, or

4444705723234237498833973519982908519933430818636409166351397897095281987215864


## I/O and scoring

The following I/O methods are allowed:

• Take no input, and output the sequence indefinitely.
• Take the value of $$\n\$$ (1-indexed), and output the value of $$\a(n)\$$.
• This should follow the definition of $$\a(1) = 1\$$, $$\a(2) = 2\$$, and so on. The sequence is broken otherwise.
• Take the value of $$\n\$$, and output first $$\n\$$ values of the sequence.

Due to the indexing nature of this sequence, the indexing is fixed to 1-indexing. The sequence can be considered 0-indexed by including $$\a(0) = 1\$$ in front of the sequence; you may use this alternative definition for any of the I/O methods.

Standard rules apply. The shortest code in bytes wins.

• Out of curiosity, would hyper-neutrino's algorithm work for finding the half-step of any function, just by replacing f with the desired target function? Apr 19, 2021 at 13:40
• @Jonah You'd need to change the initial state a bit based on the exact sequence but it seems to be somewhat portable; it worked for n^2 and n^3. Also, this only works for sequences; you'd need a completely different algorithm (possibly none can be generalized) for general functions R->R, but for N->N sequences this might work Apr 19, 2021 at 15:43
• @hyper-neutrino Thanks, and yeah I was assuming sequences only. Apr 19, 2021 at 15:44
• @Jonah an example for n->n^2+n in case you were interested Apr 19, 2021 at 15:46
• @hyper-neutrino Thanks, I am :) Apr 19, 2021 at 15:51

# Python 2, 226 bytes

g=input()+2
f=lambda n,x=1,y=1:n and f(n-1,y,x+y)or x
k={1:1,2:2,3:3}
s=set(k)
x=4
y=6
while g/x:
while g/x|g/y:k[y]=f(x);k[x]=y;s|={x};x,y=y,f(x)
x,y=sorted(set(range(1,max(s)+3))-s)[:2];s|={y}
print map(k.get,range(1,g-1))


Try it online!

-33 bytes thanks to ovs

• The fibonacci function f can be shortened to f=lambda n,x=1,y=1:n and f(n-1,y,x+y)or x and the two while loops for updating x and y can be replaced by x,y=sorted(set(range(1,max(s)+3))-s)[:2];s|={y}. 224 bytes with some other minor golfs.
– ovs
Apr 19, 2021 at 10:14
• I found a bug while porting it to JS. If you pass 7, it will output [1, 2, 3, 6, 13, 5, 8] instead of [1, 2, 3, 6, 13, 5, 9]. Apr 19, 2021 at 10:23
• I think it can be fixed with min(x,y)<g+2, but I'm not 100% sure that's it's going to work for all possible inputs. Apr 19, 2021 at 10:28
• @Arnauld I don't know if it's the same thing, but I have something like min(x,y)<g+2 in my solution and I think it should work. Apr 19, 2021 at 11:05
• I believe the algorithm with g+2 fix works here (mainly because a(4)=6 was hardcoded), and in general for any parent sequence which is strictly increasing with sufficient gaps between terms. Apr 19, 2021 at 22:59

1:2:3:4#(0:1:z)
n#(0:x:y:t)|x<1=n#((n+1):f!!n:y:t)|m<-n+2=n#(m:x:f!!n:t)
n#(x:t)|(a,_:b)<-splitAt(f!!n-n-1)t=x:(n+1)#(a++f!!x:b)
f=1:scanl(+)1f
z=0:z


Try it online!

The infinite (1-indexed) sequence (it breaks after the 33rd element because of integer overflow, but the algorithm should in principle work for arbitrarily large numbers). Here you can find a version that uses the same algorithm with arbitrary precision Integers (and, incidentally, is also much more efficient).

## How?

To understand the algorithm I've implemented, imagine an infinite array a indexed by the positive integers, and a pointer ^ that moves along this array.

Step 0. Initially, the array looks like this:

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  . 13  .  .  .  .  .  .  .  .
^


We hardcode into the array the values at positions 1, 2, 3 and 5, and all the other cells of the array are empty. The pointer starts at position 4, and will only move forwards.

Step 1. Assume the pointer is pointing at an empty cell (otherwise, go to step 2), say at position n. In the initial configuration, n=4.

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  . 13  .  .  .  .  .  .  .  .
^


Let m be the index of the first empty cell after n. Conveniently, either m=n+1 or m=n+2, since at most one of n+1 and n+2 is a Fibonacci number, and all non-Fibonacci-indexed cells after n are empty. Then we write m at position n and f(n) at position m, where f(n) is the n-th Fibonacci number. In the example, m=6 since cell 5 is not empty; we set a(4)=6 and a(6)=f(4)=5:

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  6 13  5  .  .  .  .  .  .  .
^


After that, we go to step 2 without moving the pointer.

Step 2. Let n be the position of the pointer. If we got to this point, there is a number (say x) at position n.

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  6 13  5  .  .  .  .  .  .  .
^


In this example, x=6. It's not hard to see that cell f(n) will always be empty (except for this example, where a(5) was hardcoded). Then we write the number f(x) at position f(n).

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  6 13  5  .  .  .  .  .  .  .
^


After that, we advance the pointer by 1 and we go back to step 1.

n    |  1  2  3  4  5  6  7  8  9 10 11 12 13
a(n) |  1  2  3  6 13  5  .  .  .  .  .  .  .
^


Here are the next few steps of the algorithm.

n    |  1   2   3   4   5   6   7   8   9  10  11  12  13
a(n) |  1   2   3   6  13   5   . 337   .   .   .   .   .
^


Step 2. Write f(13)=337 at position f(5)=8; advance the pointer.

n    |  1   2   3   4   5   6   7   8   9  10  11  12  13
a(n) |  1   2   3   6  13   5   . 337   .   .   .   .   8
^


Step 2. Write f(5)=8 at position f(6)=13; advance the pointer.

n    |  1   2   3   4   5   6   7   8   9  10  11  12  13
a(n) |  1   2   3   6  13   5   9 337  21   .   .   .   8
^


Step 1. Write m=9 at position 7; write f(7)=21 at position m=9.

# JavaScript (ES6),  181  171 bytes

This is really just a port of @hyper-neutrino's answer.

Returns the $$\n\$$th term of the sequence.

n=>(s=new Set(k=[A=n=>s.has(++n)?A(n):s.add(n)|n,1,2,3]),h=(x,y)=>x>n?k[n]:(g=(x,y)=>x>n+1&y>n+1?h(A,A):g(y,k[k[s.add(x)|x]=y]=(F=p=>x--?F(q,q+=p):p)(q=1)))(x,y))(4,6)


Try it online!

### Commented

Helper function A

A = n =>                       // expects n zero'ish on the initial call
s.has(++n) ?                 // increment n; if n belongs to the set:
A(n)                       //   do a recursive call
:                            // else:
s.add(n) | n               //   add n to the set and return n


Main function

n => (                         // n = input
s = new Set(                 // create a set s containing:
k = [, 1, 2, 3]            //   the values of the array k = [undefined, 1, 2, 3]
),                           //   (undefined will be quietly ignored thereafter)
h = (x, y) =>                // outer recursive function h taking (x, y):
x > n ?                    //   if x is greater than n:
k[n]                     //     we're done: return k[n]
:                          //   else:
( g = (x, y) =>          //     inner recursive function g taking (x, y):
x > n + 1 &            //       if min(x, y) is greater than n + 1:
y > n + 1 ?            //
h(A, A)          //         do a recursive call to h with the next two
//         values that are not yet in the set
:                      //       else:
g(                   //         do a recursive call to g:
y,                 //           pass x = y
k[                 //           update k[y]:
k[s.add(x) | x]  //             add x to the set and do k[x] = y
= y              //
] = (              //             set k[y] to the x-th Fibonacci number
F = p =>         //             using yet another recursive function F
x-- ?          //             to compute it
F(q, q += p) //
:              //
p            //
)(q = 1)           //             initial call to F
)                    //         end of recursive call
)(x, y)                  //     initial call to g
)(4, 6)                        // initial call to h


# Python 3, 191 143 bytes*

from itertools import*
s=lambda n:[l for l in product(*[range(1,9**9**n)]*9**9**n)if all(l[l[i]]+l[l[i+1]]==l[l[i+2]]for i in range(n))][0][:n]


The function s takes an integer n and returns a tuple of length n which starts with (1, 1, 2, 3, 6, ...).

This is simple brute force, and is practically infeasible for even n=2. To make sure this works you can switch the 9**9**n for an 8 and it should work for all $$\n\le4\$$

*NOTE: this assumes that $$\\forall\left\{n\ge1\right\}:a\left(n\right)<9^{9^n}\$$. I think it's fine as the regular Fibonacci sequence grows as less than $$\2^n\$$, but if that's false then we might switch this out for triple/quadruple exponentials for an extra cost of 6 bytes per extra exponential for both (just add 9** before the first 9 on both occurrences in the code)

-30 bytes thanks to Bubbler (import* and reducing indentation)

-18 bytes thanks to Roee Sinai (converting s to a one-liner)

• Your assumption is unfortunately incorrect because $a(34)$ is almost a 80-digit number. Looks like it works if you apply the 9**9**n fix. Welcome to CGCC, and nice first answer. Apr 21, 2021 at 0:12
• Golfing tips: You can reduce the indentation to 1 space per level. Since you use itertools.product only once, starting with from itertools import* and using product is the shortest way. Check out tips for golfing in Python. Apr 21, 2021 at 0:16