New Order #5: where Fibonacci and Beatty meet at Wythoff

Question

Introduction (may be ignored)

Putting all positive numbers in its regular order (1, 2, 3, ...) is a bit boring, isn't it? So here is a series of challenges around permutations (reshuffelings) of all positive numbers. This is the fifth challenge in this series (links to the first, second, third and fourth challenge).

In this challenge, we will meet the Wythoff array, which is a intertwined avalanche of Fibonacci sequences and Beatty sequences!

The Fibonacci numbers are probably for most of you a well known sequence. Given two starting numbers \$F_0\$ and \$F_1\$, the following \$F_n\$ are given by: \$F_n = F_{(n-1)} + F_{(n-2)}\$ for \$n>2\$.

The Beatty sequence, given a parameter \$r\$ is: \$B^r_n = \lfloor rn \rfloor\$ for \$n \ge 1\$. One of the properties of the Beatty sequence is that for every parameter \$r\$, there is exactly one parameter \$s=r/(r-1)\$, such that the Beatty sequences for those parameters are disjunct and joined together, they span all natural numbers excluding 0 (e.g.: \$B^r \cup B^{r/(r-1)} = \Bbb{N} \setminus \{0\}\$).

Now here comes the mindblowing part: you can create an array, where each row is a Fibonacci sequence and each column is a Beatty sequence. This array is the Wythoff array. The best part is: every positive number appears exactly once in this array! The array looks like this:

   1    2    3    5    8   13   21   34   55   89  144 ...
   4    7   11   18   29   47   76  123  199  322  521 ...
   6   10   16   26   42   68  110  178  288  466  754 ...
   9   15   24   39   63  102  165  267  432  699 1131 ...
  12   20   32   52   84  136  220  356  576  932 1508 ...
  14   23   37   60   97  157  254  411  665 1076 1741 ...
  17   28   45   73  118  191  309  500  809 1309 2118 ...
  19   31   50   81  131  212  343  555  898 1453 2351 ...
  22   36   58   94  152  246  398  644 1042 1686 2728 ...
  25   41   66  107  173  280  453  733 1186 1919 3105 ...
  27   44   71  115  186  301  487  788 1275 2063 3338 ...
  ...

An element at row \$m\$ and column \$n\$ is defined as:

\$A_{m,n} = \begin{cases} \left\lfloor \lfloor m\varphi \rfloor \varphi \right\rfloor & \text{ if } n=1\\ \left\lfloor \lfloor m\varphi \rfloor \varphi^2 \right\rfloor & \text{ if } n=2\\ A_{m,n-2}+A_{m,n-1} & \text{ if }n > 2 \end{cases}\$

where \$\varphi\$ is the golden ratio: \$\varphi=\frac{1+\sqrt{5}}{2}\$.

If we follow the anti-diagonals of this array, we get A035513, which is the target sequence for this challenge (note that this sequence is added to the OEIS by Neil Sloane himself!). Since this is a "pure sequence" challenge, the task is to output \$a(n)\$ for a given \$n\$ as input, where \$a(n)\$ is A035513.

There are different strategies you can follow to get to \$a(n)\$, which makes this challenge (in my opinion) really interesting.

Task

Given an integer input \$n\$, output \$a(n)\$ in integer format, where \$a(n)\$ is A035513.

Note: 1-based indexing is assumed here; you may use 0-based indexing, so \$a(0) = 1; a(1) = 2\$, etc. Please mention this in your answer if you choose to use this.

Test cases

Input | Output
---------------
1     |  1
5     |  7
20    |  20
50    |  136
78    |  30
123   |  3194
1234  |  8212236486
3000  |  814
9999  |  108240
29890 |  637

It might be fun to know that the largest \$a(n)\$ for \$1\le n\le32767\$ is \$a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) \lfloor 2 \varphi\rfloor + F(255).\$

Rules

• Input and output are integers
• Your program should at least support input in the range of 1 up to 32767). Note that \$a(n)\$ goes up to 30 digit numbers in this range...
• Invalid input (0, floats, strings, negative values, etc.) may lead to unpredicted output, errors or (un)defined behaviour.
• Default I/O rules apply.
• Default loopholes are forbidden.
• This is code-golf, so the shortest answers in bytes wins

Answer 1

R, 143 130 124 123 bytes

function(n){k=0:n+1
`~`=rbind
m=k-1~(k*(1+5^.5)/2)%/%1
for(i in k)m=m~m[i,]+m[i+1,]
m=m[-1:-2,]
m[order(row(m)+col(m))][n]}

Try it online!

Uses the formula \$T(n,-1)=n-1; T(n,0)=\lfloor n\cdot\phi\rfloor;T(n,k)=T(n,k-1)+T(n,k-2)\$ to construct the array (transposed), then splits the array along antidiagonals. k merely exists to prevent forcing a drop=F argument in m[-1:-2,] for the case n=1.

Thanks to Neil for pointing out a 1 byte golf.

R, 150 138 132 bytes

function(n){T[2]=1
for(j in 2:n-1)T=c(T,T[j]+T[j+1])
m=T[-1]%o%((1:n*(.5+5^.5/2))%/%1)+T[-1-n]%o%(1:n-1)
m[order(row(m)+col(m))][n]}

Try it online!

Implements the formula \$T(n,k)=Fib(k+1)\cdot\lfloor n\cdot\phi\rfloor+Fib(k)\cdot(n-1)\$ to get generate the array, then splits along the antidiagonals and extracts the nth element.

Thanks to Robin Ryder for the T[2]=1 trick for generating the Fibonacci sequence.

---

Both solutions are highly inefficient, creating an nxn matrix of (most likely) doubles, as R promotes integer (32-bit signed) to double automatically when overflowing, but the second one should be quite a lot faster. Taking n as a bignum should work automatically, using the call gmp::as.bigz(n), should loss of precision under doubles be worrisome, and then the language would be R + gmp.

Answer 2

Jelly, 27 24 bytes

p`SÞ⁸ịð’;×ØpḞ¥×⁹r‘ÆḞ¤Sð/

Try it online!

Monadic link using 1-based indexing. Thanks to @JonathanAllan for a better way of getting the row and columns from n and saving 3 bytes. In its shortest form it’s too slow for larger n on TIO, so the following Try it online! reduces the size of the initial list of rows and columns at the cost of three bytes.

Explanation

p`                       | Cartesian product of the range from 1..input with itself   
  SÞ                     | Sort by sum
    ⁸ị                   | Find the tuple at the position indicated by the input - this is the row and column
      ð               ð/ | Start a new dyadic chain using the row as the left and column as the right argument
       ’                 | Increase the row by 1
        ;    ¥           | Concatenate to:
         ×Øp             |   row × φ
            Ḟ            |   rounded down
              ×     ¤    | Multiply this pair by
                  ÆḞ     |   the Fibonacci numbers at positions
               ⁹         |   column index and
                r‘       |   column index plus one
                     S   | sum

Note this is based on the description of the Python code on the OEIS page.

Answer 3

Wolfram Language (Mathematica), 90 bytes

Flatten[Table[(F=Fibonacci)[a+1]⌊(b-a+1)GoldenRatio⌋+(b-a)F@a,{b,#},{a,b,1,-1}]][[#]]&

Try it online!

Answer 4

Jelly, 30 bytes

p`SÞ⁸ịð;Øp,²;\¤×Ḟ¥/;+ƝQƊ⁹¡ị@ð/

Try it online!
This is a little slow, but a huge improvement is made with a prefix of Ḥ½Ċ (double, square-root, ceiling) like in this test-suite.

Answer 5

Charcoal, 54 bytes

Ｎθ≔⁰ηＷ‹ηθ«≦⊕η≧⁻ηθ»⊞υ¹Ｆθ⊞υ⁻⁺³ι§υ⊖§υι⊞υθＦ⁺²⁻θη⊞υΣ…⮌υ²Ｉ⊟υ

Try it online! Link is to verbose version of code. 0-indexed. Uses only integer arithmetic so works for arbitrary large values. Explanation:

Ｎθ

Input q.

≔⁰ηＷ‹ηθ«≦⊕η≧⁻ηθ»

Calculate the antidiagonal by subtracting ever increasing numbers from q, which ends up with the target row number m.

⊞υ¹Ｆθ⊞υ⁻⁺³ι§υ⊖§υι

Calculate the first m+1 terms of A019446, although we're only interested in the mth.

⊞υθＦ⁺²⁻θη⊞υΣ…⮌υ²

Calculate the first n+4 terms of the generalised Fibonacci series that starts with [a(m), m]. The terms of this sequence are the mth terms of A019446, A001477, A000201, A003622, A035336; these last two are the first two columns of the Wythoff array, and so this sequence continues with the rest of the mth row of the array.

Ｉ⊟υ

Output the desired term.