Introduction (peut être ignoré)

Mettre tous les entiers 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 entiers positifs. Il s'agit du sixième défi de cette série (liens vers les premier , deuxième , troisième , quatrième et cinquième défis).

Ce défi a un thème de Pâques doux (car c'est Pâques). Je me suis inspiré de cet œuf d'oie très décoré (et à mon avis plutôt moche).

Cela m'a rappelé la spirale Ulam , où tous les entiers positifs sont placés dans une spirale anti-horaire. Cette spirale a des caractéristiques intéressantes liées aux nombres premiers, mais ce n'est pas pertinent pour ce défi.

Nous arrivons à la permutation de ce nombre entier d'entiers positifs si nous prenons les nombres dans la spirale Ulam et suivons tous les entiers dans une spirale tournant dans le sens des aiguilles d' une montre , en commençant à 1. De cette façon, nous obtenons:

1, 6, 5, 4, 3, 2, 9, 8, 7, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 25, 24, 23, etc.

Si vous dessiniez les deux spirales, vous obtiendriez une sorte de maillage infini de spirales (coquille d'oeuf) ( notez la référence New Order ici ).

Cette séquence est présente dans l'OEIS sous le numéro A090861 . Puisqu'il s'agit d'un défi de "séquence pure", la tâche consiste à sortir $a(n)$ pour un $n$ donné en entrée, où est A090861 .$a(n)$

Tâche

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

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

Cas de test

Input | Output
---------------
1     |  1
5     |  3
20    |  10
50    |  72
78    |  76
123   |  155
1234  |  1324
3000  |  2996
9999  |  9903
29890 |  29796

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).
• 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 ,  16 14 11 10 9  8 octets

-1 grâce à Lynn (mod-2, NON logique, ajouter à l' auto: Ḃ¬+-> OU avec 1 bit: |1)

|1×r)ẎQi

Un lien monadique acceptant un nombre entier, nqui donne un nombre entier, a(n).

$\lceil\frac n2\rceil$

½‘|1×rƲ€ẎQi$\lceil\frac{\lfloor\sqrt n\rfloor+1}2\rceil$

Comment?

La permutation consiste à prendre les nombres naturels en tranches de longueurs inversées [1,5,3,11,5,17,7,23,9,29,11,35,13,...]- les entiers positifs impairs entrecoupés par les entiers positifs congruents à cinq modulo six, c'est-à-dire [1, 2*3-1, 3, 4*3-1, 5, 6*3-1, 7, 8*3-1, 9, ...].

C'est la même chose que la concaténation puis la déduplication des plages inversées [1..x]de où xsont les sommes cumulées de ces longueurs de tranche (c'est-à-dire le maximum de chaque tranche) - [1,6,9,20,25,42,49,72,81,110,121,156,169,...], qui est les entiers impairs au carré entrecoupés de nombres pairs multipliés par eux-mêmes incrémentés, c'est-à-dire [1*1, 2*3, 3*3, 4*5, 5*5, 6*7, 7*7,...].

Étant donné que les différences sont toutes supérieures à 1, nous pouvons enregistrer un octet (l'inversion) en créant [x..k]directement des plages , où kest l'indice indexé 1 de la tranche.

$P(n) = v \iff P(v) = n$n|1×r)ẎQị@n|1×r)ẎQi

|1×r)ẎQi - Link: integer, n       e.g. 10
    )    - for each k in [1..n]:  vs = [ 1, 2, 3, 4, 5, 6, 7, 8, 9,10]
|1       -   bitwise-OR (k) with 1     [ 1, 3, 3, 5, 5, 7, 7, 9, 9,11]
  ×      -   multiply (by k)           [ 1, 6, 9,20,25,42,49,72,81,110]
   r     -   inclusive range (to k)    [[1],[6..2],[9..3],[20..4],...,[110..10]]
     Ẏ   - tighten                     [1,6,5,4,3,2,9,8,7,6,5,4,3,20,...,4,......,110,...,10]
      Q  - de-duplicate                [1,6,5,4,3,2,9,8,7,20,...,10,......,110,...82]
       i - first index with value (n)  20

JavaScript (ES7),  46 45  41 octets

0 indexé.

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Essayez-le en ligne!

Comment?

Ceci est basé sur la formule indexée 1 utilisée dans les programmes d'exemple de A090861 .

$x_n$$0$

$$x_n=\left\lfloor\frac{\sqrt{n-1}+1}{2}\right\rfloor$$

Essayez-le en ligne!

$k_n$$6$$-2$

$$k_n=\begin{cases} -2&\text{if }n\le 4{x_n}^2+2x_n\\ 6&\text{otherwise} \end{cases}$$

Essayez-le en ligne!

$a_n$

$$a_n=8{x_n}^2+k_nx_n+2-n$$

Essayez-le en ligne!

Qui peut se traduire en:

n=>8*(x=(n-1)**.5+1>>1)*x+(n<=4*x*x+2*x?-2:6)*x+2-n

Le rendre indexé 0 enregistre immédiatement 5 octets:

n=>8*(x=n**.5+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n

La formule peut être encore simplifiée en utilisant:

$${x'}_n=2\times\left\lfloor\frac{\sqrt{n}+1}{2}\right\rfloor$$

qui peut être exprimé comme:

x=n**.5+1&~1

menant à:

n=>2*(x=n**.5+1&~1)*x+(n<x*x+x?-1:3)*x+1-n

et enfin:

n=>((x=n**.5+1&~1)*2-(n<x*x+x)*4+3)*x+1-n

Wolfram Language (Mathematica) , 60 octets

8(s=⌊(⌊Sqrt[#-1]⌋+1)/2⌋)^2-#+2+If[#<=4s^2+2s,-2,6]s&

Essayez-le en ligne!

MATL , 12 11 octets

Eq1YL!tPG=)

Essayez-le en ligne!

Très peu efficace en mémoire. Le pré-paiement le X^krend plus efficace .

C # (Visual C # Interactive Compiler) , 67 octets

n=>8*(x=(int)Math.Sqrt(--n)+1>>1)*x+(n<4*x*x+2*x?-2:6)*x+1-n;int x;

Essayez-le en ligne!

Python 3.8, 104 74 65 60 57 octets

lambda n:(-2,6)[n>4*(x:=(n**.5+1)//2)*x+2*x]*x+2+~n+8*x*x

Edit: Merci à Johnathan Allan de l'avoir fait passer de 74 à 57 octets!

Cette solution utilise une indexation basée sur 0.

Python 3.8 (version préliminaire) , 53 octets

Un port direct de la réponse JavaScript d' Arnauld , votez pour cela, et / ou la réponse Mathematica de J42161217 et / ou la réponse Python de Kapocsi :)

lambda n:((x:=int(n**.5+1)&-2)*2-(n<x*x+x)*4+3)*x+1-n

0 indexé.

Essayez-le en ligne!

Befunge, 67 57 octets

Cette solution suppose une indexation basée sur 0 pour les valeurs d'entrée.

p&v-*8p00:+1g00:<
0:<@.-\+1*g00+*<|`
0g6*\`!8*2+00g4^>$:0

Essayez-le en ligne!

Explication

On commence par calculer le "rayon" auquel l'entrée n se trouve avec une boucle:

radius = 0
while n > 0
  radius += 1
  n -= radius*8

À la fin de la boucle, la valeur précédente de n est le décalage dans la spirale à ce rayon:

offset = n + radius*8

Nous pouvons alors déterminer si nous sommes sur la section supérieure ou inférieure de la spirale comme suit:

bottom = offset >= radius*6

Et une fois que nous avons tous ces détails, la valeur en spirale est calculée avec:

value = ((bottom?10:2) + 4*radius)*radius + 1 - offset

Le rayon est la seule valeur que nous devons stocker en tant que "variable", le limitant à une valeur maximale de 127 dans Befunge-93, donc cet algorithme peut gérer des entrées jusqu'à 65024.

Japt , 15 octets

Solution Jelly du port de Jonathan. 1 indexé.

gUòȲ+X*v)õÃcÔâ

Essayez-le

gUòȲ+X*v)õÃcÔâ     :Implicit input of integer U
g                   :Index into
 Uò                 :  Range [0,U]
   È                :  Map each X
    ²               :    Square X
     +X*            :    Add X multiplied by
        v           :    1 if X is divisible by 2, 0 otherwise
         )          :    Group result
          õ         :    Range [1,result]
           Ã        :  End map
            c       :  Flatten
             Ô      :    After reversing each
              â     :  Deduplicate

C ++ (gcc) , 88 octets

#import<cmath>
int a(int n){int x=(sqrt(n-1)+1)/2;return x*(8*(x+(n>4*x*x+2*x))-2)+2-n;}

1 indexé; utilise la formule de la page OEIS, mais manipulée pour économiser quelques octets.

Essayez-le en ligne!