Voici la séquence dont je parle:

{1, 4, 5, 9, 10, 11, 16, 17, 18, 19, 25, 26, 27...}

À partir de 1, gardez 1, laissez tomber les 2 suivants, gardez les 2 suivants, laissez tomber 3, gardez 3 et ainsi de suite. Oui, c'est aussi sur OEIS (A064801) !

Le défi

Étant donné un entier n>0, trouver le nième terme de la séquence ci-dessus

Cas de test

Input -> Output       
1->1  
22->49  
333->683
4444->8908
12345->24747

C'est le golf de code, donc la réponse la plus courte en octets l'emporte! Bonne chance!

Java (OpenJDK 8) , 45 44 octets

n->{int i=0;for(;++i<n;n-=i);return~-n+i*i;}

Essayez-le en ligne!

-1 octet grâce à @Nevay

Après avoir regardé cela pendant un moment, j'ai remarqué un motif. Chaque fois que nous supprimons des nnombres, le nombre suivant de la séquence est un carré parfait. Voyant cela, j'ai scindé mentalement la séquence en morceaux pratiques: [[1],[4,5],[9,10,11],...]Fondamentalement, le ie morceau commence par i*iet itère vers le haut pour les iéléments.

Pour trouver le nnuméro e dans cette séquence, nous voulons d'abord trouver dans quel morceau le numéro est, puis dans quelle position dans le morceau qu'il occupe. Nous soustrayons notre numéro d'incrémentation ide njusqu'à ce que nsoit inférieur à i(ce qui nous donne notre bloc), puis ajoutons simplement n-1à i*ipour obtenir le bon positiondans le bloc.

Exemple:

n = 8
n > 1? Yes, n = n - 1 = 7
n > 2? Yes, n = n - 2 = 5
n > 3? Yes, n = n - 3 = 2
n > 4? No, result is 4 * 4 + 2 - 1 = 17

Haskell, 48 43 41 octets

n#l=[l..l+n]++(n+1)#(l+2*n+3)
((0:0#1)!!)

4 octets supplémentaires pour l'indexation basée sur 1 au lieu de basée sur 0. Une restriction inutile, à mon humble avis.

Essayez-le en ligne!

n#l             -- n is one less than the number of element to keep/drop and
                -- l the next number where the keep starts
   [l..l+n]     -- keep (n+1) numbers starting at l
   ++           -- and append a recursive call
   (n+1)#       -- where n is incremented by 1 and
      (l+2*n+3) -- l skips the elements to keep & drop

0#1             -- start with n=1 and l=0 and
 0:             -- prepend a dummy value to shift from 0 to 1-based index
    !!          -- pick the i-th element from the list 

Python 3 , 47 46 octets

1 octet merci à M. Xcoder.

def f(n):a=round((2*n)**.5);return~-n+a*-~a//2

Essayez-le en ligne!

TRÈS rapide pour des nombres plus élevés

Gelée , 8 octets

Ḷ+²µ€Ẏ⁸ị

Essayez-le en ligne!

Haskell , 33 octets

Une fonction anonyme. Utilisé comme((!!)$0:do n<-[1..];[n^2..n^2+n-1]) 1

(!!)$0:do n<-[1..];[n^2..n^2+n-1]

Essayez-le en ligne!

• Construit la séquence comme une liste infinie, puis l'indexe avec !!. Le 0:est un élément factice pour ajuster l'indexation de 0 à 1.
• La plage [n^2..n^2+n-1]construit une sous-séquence sans espaces, en commençant par le carré de net contenant les nnombres.
• La donotation concatène les plages construites pour tous n>=1.

Python 3 , 46 octets

f=lambda x,y=0,z=0:y<x and f(x,y+z,z+1)or~-y+x

Essayez-le en ligne!

Perl 6 , 43 octets

{(1..*).rotor({++$=>++$+1}...*).flat[$_-1]}

Essaye-le

Étendu:

{  # bare block lambda with implicit parameter ｢$_｣

  ( 1 .. * )                  # range starting from 1

  .rotor(                     # break it into chunks

    { ++$  =>  ++$ + 1} ... * # infinite Seq of increasing pairs
    #   1  =>    1 + 1    ==>   1 => 2 ( grab 1 skip 2 )
    #   2  =>    2 + 1    ==>   2 => 3
    #   3  =>    3 + 1    ==>   3 => 4
    # ...  =>  ... + 1

  ).flat\                     # reduce the sequence of lists to a flat sequence
  [ $_ - 1 ]                  # index into the sequence
                              # (adjusting to 0-based index)
}

(1..*).rotor({++$=>++$+1}...*) produit:

(
 (1,),
 (4, 5),
 (9, 10, 11),
 (16, 17, 18, 19),
 (25, 26, 27, 28, 29),
 ...
).Seq

TeX, 166 octets

\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

Usage

\documentclass[12pt,a4paper]{article}
\begin{document}
\newcommand{\f}[1]{\count0=0\count1=0\loop\advance\count0 by\the\count1\advance\count1 by1\ifnum\count0<#1\repeat\advance\count0 by#1\advance\count0 by-1
\the\count0}

\f{1}

\f{22}

\f{333}

\f{4444}

\f{12345}
\end{document}

Javascript, 43 38 octets

n=>eval("for(r=1;n>r;)n-=r++;r*r+n-1")

Essayez-le en ligne!

J'utilise le fait que pour chaque nombre triangulaire plus un, le résultat est un nombre carré.

Par exemple: les nombres triangulaires sont 0, 1, 3, 6, 10 ... donc pour 1, 2, 4, 7, 11 ... nous observons 1, 4, 9, 16, 25 ... dans notre séquence .

Si l'indice se situe quelque part entre ces nombres connus, les éléments de notre séquence n'avancent que de un. Par exemple, pour calculer le résultat pour 10, nous prenons 7 (comme un nombre triangulaire plus un), prenons le résultat (16) et ajoutons 10-7 = 3. Ainsi, 16 + 3 = 19.

05AB1E , 12 octets

LεÝÁćn+}˜¹<è

Essayez-le en ligne!

cQuents , 27 octets

#R(2B)^.5)|1:b~-B+A*-b~A//2

Essayez-le en ligne!

Actuellement, un portage de la réponse Python de Leaky , je pense qu'il y a un meilleur moyen.

Swift 3 , 72 octets

Port de ma solution Python .

func f(_ x:Int,_ y:Int=0,_ z:Int=0)->Int{return y<x ?f(x,y+z,z+1):y+x-1}

Suite de tests.

C # (mono) , 164 octets

using System.Linq;n=>{var a=new int[1]{1}.ToList();for(int i=1,m;a.Count<n;a.AddRange(new int[++i*2].Select((_,d)=>m+d+1).Skip(i).Take(i)))m=a.Max();return a[n-1];}

Essayez-le en ligne!

Mathematica, 37 octets

Flatten[Range@#+#^2-1&~Array~#][[#]]&

Explication

Range@#+#^2-1&

Functionqui prend un entier positif #et retourne la #suite de nombres consécutifs dans la séquence.

...~Array~#

Produit la liste de toutes ces exécutions jusqu'à l'entrée #

Flatten[...][[#]]

Flattensla liste résultante et renvoie le #e élément.

Perl 5 , 33 + 1 (-p) = 34 octets

$\+=$.--?1:2+($.=++$s)while$_--}{

Essayez-le en ligne!

Tampio , 310 308 octets

n:n uni on n unena 1:lle
a unena k:lle on a vuona k:lla vähennettynä a:sta ja k
a vuona nollalla ja k on a
a vuona k:lla vähennettynä nollasta ja k on a
a vuona b:n seuraajalla ja k on yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla ja k:n vähennettynä a:sta arvolla unena k:n seuraajalle seuraaja

Utilisation: 4:n uniévalue à9 .

Explication:

n:n uni on n unena 1:lle
uni(n)  =  n `uni` 1

a unena k:lle on  a vuona  k:lla vähennettynä a:sta ja k
a `uni` k     =  (a `vuo` (k     `vähennetty` a)    )  k

 a vuona nollalla ja k on a
(a `vuo` 0        )  k =  a

 a vuona  k:lla vähennettynä nollasta ja k on a
(a `vuo` (k     `vähennetty` 0)       )  k =  a

 a vuona  b:n seuraajalla ja k on
(a `vuo` (b   + 1)        )  k =

 yhteenlaskun kutsuttuna k:n kerrottuna 2:lla arvolla
(yhteenlasku            (k   *          2     )

 ja k:n vähennettynä a:sta arvolla unena  k:n seuraajalle seuraaja
((  k   `vähennetty` a     )       `uni` (k   + 1)   )  ) + 1

De la bibliothèque standard:

a `vähennetty` b = b - a
yhteenlasku a b  = a + b

JavaScript (ES6), 33 octets

Solution récursive inspirée des observations de Xanderhall .

f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)

Essayez-le

o.innerText=(
f=(n,x=1)=>n<x?n+x*x-1:f(n-x,++x)
)(i.value=12345);oninput=_=>o.innerText=f(+i.value)

<input id=i type=number><pre id=o>

Python 3 , 50 octets

def f(n):
 a=i=0
 while a<n:a+=i;i+=1
 return~-a+n

Essayez-le en ligne!

Mathematica, 82 octets

Complement[Range[3#],Array[#+⌊((r=Sqrt[1+8#])-1)/2⌋⌊(r+1)/2⌋/2&,3#]][[#]]&

Python , 40 octets

lambda n:(round((2*n)**.5)+.5)**2//2+n-1

Essayez-le en ligne!

Optimisation de l'expression de Leaky Nun .

Python , 41 octets

f=lambda n,k=1:n*(n<=k)or-~f(n-k,k+1)+2*k

Essayez-le en ligne!

Expression récursive.

Javascript (ES6) 100 98 octets

var k=n=>{var s=[],i=1,c=1,j;while(s.length<n){for(j=i;j<i+c;j++){s.push(j)}i+=c*2+1;c++}return s}

J'ai fait celui-ci rapidement, donc je parie qu'il y a beaucoup de place pour l'amélioration, juste des boucles et des compteurs de base.

Rétine , 27 octets

.+
$*
((^1|1\2)+)1
$1$2$&
1

Essayez-le en ligne! Port de la réponse Python de @ LeakyNun. La première et la dernière étape ne sont qu'une conversion décimale ary unaire ennuyeuse. La deuxième étape fonctionne comme ceci: ((^1|1\2)+)est un comparateur de nombres triangulaire; $1est le nombre triangulaire correspondant tandis que$2 son index. La fin 1signifie qu'elle correspond au plus grand nombre triangulaire strictement inférieur à l'entrée, ce qui entraîne exactement une itération de moins que la boucle Python, ce qui signifie $1qu'équivalent à a-iet $2à i-1et que leur somme est a-1ou ~-aselon les besoins. ( pour correspondre dans ce cas aussi.$& empêche simplement la correspondance d'être supprimée du résultat.) Notez que pour une entrée 1sans correspondance, la sortie est simplement la même que l'entrée. Si vous étiez pervers, vous pourriez utiliser^((^1|1\2)*)1

MATL , 12 octets

:"@U@:q+]vG)

Essayez-le en ligne!

Explication

:        % Push range [1 2 ... n], where n is implicit input
"        % For each k in that range
  @U     %   Push k^2
  @:     %   Push range [1 2 ... k]
  q      %   Subtract 1: gives [0 1 ... k-1]
  +      %   Add: gives [k^2 k^2+1 ... k^2+k-1]
]        % End
v        % Concatenate all numbers into a column vector
G)       % Get n-th entry. Implicitly display

C (gcc) , 38 octets

Utilisation de l'algorithme de @ Xanderhall ici

i;f(n){for(i=0;++i<n;n-=i);n=n-1+i*i;}

Essayez-le en ligne!

PHP, 48 42 37 + 1 octets

porté de la réponse de Leaky Nun

while($argn>$a+=$i++);echo$a+~-$argn;

Exécuter en tant que pipe avec -Fou l' essayer en ligne .

approche directe, 42 + 1 octets (porté depuis l' autre réponse de Leaky Nun )

<?=($a=(2*$argn)**.5+.5|0)*-~$a/2+~-$argn;

Exécuter en tant que tuyau avec -nRou décommenter dans TiO ci-dessus.

ancienne solution itérative, 48 + 1 octets

for(;$argn--;$n++)$c++>$z&&$n+=++$z+$c=1;echo$n;