Introduction (peut être ignoré)

Mettre tous les nombres positifs dans son ordre régulier (1, 2, 3, ...) est un peu ennuyeux, n'est-ce pas? Voici donc une série de défis autour des permutations (remaniements) de tous les nombres positifs. Il s'agit du cinquième défi de cette série (liens vers les premier , deuxième , troisième et quatrième défis).

Dans ce défi, nous rencontrerons le tableau Wythoff, qui est une avalanche entrelacée de séquences de Fibonacci et de séquences Beatty!

Les nombres de Fibonacci sont probablement pour la plupart d'entre vous une séquence bien connue. Étant donné deux nombres de départ $F_0$ et $F_1$ , les $F_n$ sont donnés par: $F_n = F_{(n-1)} + F_{(n-2)}$ pour $n>2$ .

La séquence de Beatty , étant donné un paramètre $r$ est: $B^r_n = \lfloor rn \rfloor$ pour $n \ge 1$ . L'une des propriétés de la séquence Beatty est que pour chaque paramètre $r$ , il y a exactement un paramètre $s=r/(r-1)$ , de sorte que les séquences Beatty pour ces paramètres sont disjointes et jointes, elles s'étendent sur tous les nombres naturels à l'exclusion 0 (par exemple: $B^r \cup B^{r/(r-1)} = \Bbb{N} \setminus \{0\}$ ).

Voici maintenant la partie époustouflante: vous pouvez créer un tableau, où chaque ligne est une séquence Fibonacci et chaque colonne est une séquence Beatty. Ce tableau est le tableau Wythoff . La meilleure partie est: chaque nombre positif apparaît exactement une fois dans ce tableau! Le tableau ressemble à ceci:

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

Un élément à la ligne $m$ et à la colonne $n$ est défini comme:

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

où $\varphi$ est le nombre d'or: $\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

Étant donné une entrée entière $n$ , la sortie $a(n)$ au format entier, où $a(n)$ est A035513 .

Remarque: l'indexation basée sur 1 est supposée ici; vous pouvez utiliser une indexation basée sur 0, donc $a(0) = 1; a(1) = 2$ , etc. Veuillez le mentionner dans votre réponse si vous choisissez de l'utiliser.

Cas de test

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

Il peut être amusant de savoir que le plus grand $a(n)$ pour $1\le n\le32767$ est $a(32642) = 512653048485188394162163283930413917147479973138989971 = F(256) \lfloor 2 \varphi\rfloor + F(255).$

Règles

• L'entrée et la sortie sont des entiers
• Votre programme doit au moins prendre en charge les entrées comprises entre 1 et 32 ​​767). Notez que $a(n)$ va jusqu'à 30 numéros de chiffres dans cette gamme ...
• Une entrée non valide (0, flottants, chaînes, valeurs négatives, etc.) peut entraîner une sortie imprévue, des erreurs ou un comportement (non) défini.
• Les règles d'E / S par défaut s'appliquent.
• Les failles par défaut sont interdites.
• Il s'agit de code-golf , donc les réponses les plus courtes en octets l'emportent

Gelée , 27 24 octets

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

Essayez-le en ligne!

Lien monadique utilisant une indexation basée sur 1. Merci à @JonathanAllan pour une meilleure façon d'obtenir la ligne et les colonnes net d'économiser 3 octets. Dans sa forme la plus courte, il est trop lent pour un n plus grand sur TIO, donc ce qui suit Essayez-le en ligne! réduit la taille de la liste initiale de lignes et de colonnes au prix de trois octets.

Explication

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

Notez que cela est basé sur la description du code Python sur la page OEIS.

R , 143 130 124 123 octets

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

Essayez-le en ligne!

Utilise la formule $T(n,-1)=n-1; T(n,0)=\lfloor n\cdot\phi\rfloor;T(n,k)=T(n,k-1)+T(n,k-2)$pour construire le tableau (transposé), puis splitsle tableau le long des antidiagonales. kexiste simplement pour empêcher de forcer un drop=Fargument dans m[-1:-2,]l'affaire n=1.

Merci à Neil d' avoir signalé un golf de 1 octet.

R , 150 138 132 132 octets

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

Essayez-le en ligne!

Met en œuvre la formule $T(n,k)=Fib(k+1)\cdot\lfloor n\cdot\phi\rfloor+Fib(k)\cdot(n-1)$pour obtenir générer le tableau, puis le splitslong des antidiagonales et extrait l' nthélément.

Merci à Robin Ryder pour l' T[2]=1astuce pour générer la séquence de Fibonacci.

Les deux solutions sont très inefficaces, créant une nxnmatrice de (très probablement) doubles, car R promeut integer(signé 32 bits) doubleautomatiquement en cas de débordement, mais la seconde devrait être beaucoup plus rapide. Prendre ncomme un bignum devrait fonctionner automatiquement, en utilisant l'appel gmp::as.bigz(n), si la perte de précision sous doubles était inquiétante, et alors la langue le serait R + gmp.

Wolfram Language (Mathematica) , 90 octets

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

Essayez-le en ligne!

Gelée , 30 octets

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

Essayez-le en ligne!
C'est un peu lent, mais une énorme amélioration est apportée avec un préfixeḤ½Ċ(double, racine carrée, plafond) comme dans cette suite de tests .

Fusain , 54 octets

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

Essayez-le en ligne! Le lien est vers la version détaillée du code. 0 indexé. Utilise uniquement l'arithmétique entière et fonctionne donc pour les grandes valeurs arbitraires. Explication:

Ｎθ

Entrée q.

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

Calculez l'antidiagonale en soustrayant des nombres toujours croissants de q, ce qui aboutit au numéro de ligne cible m.

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

Calculez les premiers m+1termes de A019446 , bien que nous ne nous intéressions qu'au mth.

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

Calculez les premiers n+4termes de la série généralisée de Fibonacci qui commence par [a(m), m]. Les termes de cette séquence sont les mtermes de A019446 , A001477 , A000201 , A003622 , A035336 ; ces deux dernières sont les deux premières colonnes du tableau Wythoff, et donc cette séquence continue avec le reste de la me ligne du tableau.

Ｉ⊟υ

Sortez le terme souhaité.