[Question]
  [
## Challenge
Implement the 1-indexed sequence [A054049](https://oeis.org/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 [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") rules apply. The shortest code in bytes wins.
  
[Answer]
# [Python 2](https://docs.python.org/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!](https://tio.run/##PY3BioMwFEXXzVdkmYdxSuIwhcj7EnGRwZiKNYrJ0Bdav93WgZnduVzOvUtO1znoffc4hOUnCSg06/Fmp@/O8iAJlcyoTOA2dLwXoXxnSUWGeeXERnwoo6Q2Wlam2ljE6JIYgRF@soxf7H4dbo77Mxl2@uenP2czNrnFXhDUY0Mt5jo@8UFbTe@/LI@CnQ6O85pcJ47d1QbvhJKTJRGhqADKCI3R7a@bN7asQ0h8sosYP7xL8k/wpQLY98sL "Python 2 – Try It Online")
-33 bytes thanks to ovs
[Answer]
# [Haskell](https://www.haskell.org/), ~~181~~ 149 bytes
```
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!](https://tio.run/##JYxBDsIgEEX3PUWbuoAgSWldTcrCA3gDk2ZsijYCIcICG88uQt3Nf//9eaB/LlonlNckoIcBTi3pQMBGK1uuCG8I9BNHIXMmlgkKqmnsH5uRW9aXxmRz52EfxtISPE5woyP3Tq/hHEgRuOWCBhlh/9USZCzjmL1KSQF@RqsJo0JVm@xgSwZXKw26y1S712rDIeBzqYehxvSdlca7T3x27gc "Haskell – 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](https://tio.run/##LY2xTsQwEER7f0Wio7BljOzjqlVcINEgQUWLdFqCfVhnL1biwkSIT8ckB93szNuZd5zPLsYWUv6YSnePBW8ew1wY74U9OXJTGB/ozVWG9qUZ2MMtHHZcg4FFMNpUhU8o4qsOxq43J2kE@J7@3DQokvstSCu42eXyVreQ4/U3P8KrEIP633rOMZS7wldSkTKi2AqXyh1HKX1fV5p5a2AekSKXwni2WA1LSxjIJsxPxy5PgcpVwbPrjNa6w/Yz@oinuakx518 "Haskell – Try It Online") 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`.
[Answer]
# JavaScript (ES6), ~~181~~ 171 bytes
This is really just a port of [@hyper-neutrino's answer](https://codegolf.stackexchange.com/a/223810/58563).
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!](https://tio.run/##TY7BboQwDETv@xU5rCpbCah0qx7YGsRlf6BHhES0BGhBDmxQC2L5dpq2lx48Hj3Zo/nQn9pdb@/DFLCtzF7TzpSAIzZf4s1M0FGekUcubLUDKRnTDBhjF@qq8ubOKlJP6lSgaglmtSAlc8Jpl3MRQ/MPyehh@dG0hawslR@MG1hUl3f5X9qM97mgpSC40OB/giC9wKhGSQPGA8JIESL@JiI8qxfca3uD3kyCBYno7NcridOjN1KiWA9CXC0725uwtw2UGo4rb@hvj2vtu28lng/b/g0 "JavaScript (Node.js) – 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
```
[Answer]
# [Python 3](https://docs.python.org/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)
]