Introdução (pode ser ignorado)

Colocar todos os números positivos em sua ordem regular (1, 2, 3, ...) é um pouco chato, não é? Então, aqui está uma série de desafios em torno de permutações (reorganizações) de todos os números positivos. Este é o quinto desafio desta série (links para o primeiro , segundo , terceiro e quarto desafio).

Neste desafio, conheceremos o conjunto Wythoff, que é uma avalanche entrelaçada de sequências de Fibonacci e de Beatty!

Os números de Fibonacci são provavelmente para a maioria de vocês uma sequência bem conhecida. Dados dois números iniciais $F_0$ e $F_1$ , os seguintes $F_n$ são dados por: $F_n = F_{(n-1)} + F_{(n-2)}$ para $n>2$ .

A sequência de Beatty , dado um parâmetro $r$ é: $B^r_n = \lfloor rn \rfloor$ para $n \ge 1$ . Uma das propriedades da sequência de Beatty é que, para cada parâmetro $r$ , existe exatamente um parâmetro $s=r/(r-1)$ , de modo que as seqüências de Beatty para esses parâmetros são disjuntas e unidas, elas abrangem todos os números naturais, excluindo 0 (por exemplo: $B^r \cup B^{r/(r-1)} = \Bbb{N} \setminus \{0\}$).

Agora, aqui vem a parte surpreendente: você pode criar uma matriz, em que cada linha é uma sequência de Fibonacci e cada coluna é uma sequência de Beatty. Essa matriz é a matriz Wythoff . A melhor parte é: todo número positivo aparece exatamente uma vez nessa matriz! A matriz fica assim:

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

Um elemento em fileira $m$ e coluna $n$ é definido como:

$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}$

onde $\varphi$ é a proporção áurea: $\varphi=\frac{1+\sqrt{5}}{2}$ .

Se seguirmos as antiagonais dessa matriz, obteremos A035513 , que é a sequência de destino para esse desafio (observe que essa sequência é adicionada ao OEIS pelo próprio Neil Sloane !). Como esse é um desafio de "sequência pura", a tarefa é gerar $a(n)$ para um dado $n$ como entrada, onde $a(n)$ é A035513 .

Existem diferentes estratégias que você pode seguir para chegar a $a(n)$ , o que torna esse desafio (na minha opinião) realmente interessante.

Tarefa

Dada uma entrada inteira $n$ , imprima $a(n)$ no formato inteiro, onde $a(n)$ é A035513 .

Nota: a indexação baseada em 1 é assumida aqui; você pode usar a indexação baseada em 0; portanto, $a(0) = 1; a(1) = 2$ , etc. Por favor mencione isso na sua resposta se você optar por usá-lo.

Casos de teste

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

Pode ser divertido saber que o maior $a(n)$ para $1\le n\le32767$ é$a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) \lfloor 2 \varphi\rfloor + F(255).$

Regras

• Entrada e saída são números inteiros
• Seu programa deve, no mínimo, suportar entrada no intervalo de 1 a 32767). Observe que $a(n)$ atinge até 30 dígitos neste intervalo ...
• Entrada inválida (0, valores flutuantes, seqüências de caracteres, valores negativos etc.) pode levar a resultados imprevisíveis, erros ou comportamento (não) definido.
• Regras de E / S padrão se aplicam.
• As brechas padrão são proibidas.
• Isso é código-golfe , então as respostas mais curtas em bytes ganham

Geléia , 27 24 bytes

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

Experimente online!

Link monádico usando indexação baseada em 1. Obrigado a JonathanAllan por uma maneira melhor de obter a linha e as colunas ne salvar 3 bytes. Em sua forma mais curta, é muito lento para n maior no TIO, portanto, faça o seguinte Experimente online! reduz o tamanho da lista inicial de linhas e colunas ao custo de três bytes.

Explicação

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

Observe que isso se baseia na descrição do código Python na página OEIS.

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]}

Experimente online!

$T(n,-1)=n-1; T(n,0)=\lfloor n\cdot\phi\rfloor;T(n,k)=T(n,k-1)+T(n,k-2)$ para construir a matriz (transposta), depois splitsa matriz ao longo das antidiagonais.ksimplesmente existe para evitar forçar um drop=Fargumento m[-1:-2,]para o caso n=1.

Agradecimentos a Neil por apontar um golfe de 1 byte.

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]}

Experimente online!

$T(n,k)=Fib(k+1)\cdot\lfloor n\cdot\phi\rfloor+Fib(k)\cdot(n-1)$splits ao longo das antidiagonals e extrai o nthelemento.

Obrigado a Robin Ryder pelo T[2]=1truque para gerar a sequência de Fibonacci.

Ambas as soluções são altamente ineficientes, criando uma nxnmatriz de (provavelmente) doubles, como R promove integer(assinado de 32 bits) para doubleautomaticamente ao transbordar, mas a segunda deve ser muito mais rápida. Tomando ncomo um bignum deve funcionar automaticamente, usando a chamada gmp::as.bigz(n), se a perda de precisão em doubles for preocupante e, em seguida, o idioma for R + gmp.

Wolfram Language (Mathematica) , 90 bytes

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

Experimente online!

Gelatina , 30 bytes

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

Experimente online!
Isso é um pouco lento, mas uma grande melhoria é feita com um prefixo deḤ½Ċ(dobro, raiz quadrada, teto), como nesta suíte de testes .

Carvão , 54 bytes

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

Experimente online! Link é a versão detalhada do código. Indexado a 0. Utiliza apenas aritmética inteira, portanto, funciona com valores grandes arbitrários. Explicação:

Ｎθ

Entrada q.

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

Calcule o antidiagonal subtraindo números cada vez maiores de q, que terminam com o número da linha de destino m.

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

Calcule os primeiros m+1termos de A019446 , embora estejamos interessados ​​apenas no mth.

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

Calcule os primeiros n+4termos da série generalizada de Fibonacci que começa com [a(m), m]. Os termos desta sequência são os mth th termos de A019446 , A001477 , A000201 , A003622 , A035336 ; essas duas últimas são as duas primeiras colunas da matriz Wythoff e, portanto, essa sequência continua com o restante da mquinta linha da matriz.

Ｉ⊟υ

Saída o termo desejado.