La séquence SUDSI ( su m, d ifference, s wap, i ncrement) est une suite d'entiers curieux qui semble présenter un comportement chaotique. Il peut être généré comme suit:

Que S soit une liste infinie des nombres naturels: 1 2 3 4 5 6 .... Soit S _i désignent celui-indexé i ème élément de S . Donc au départ, S ₁ est 1, S ₂ est 2, etc. (il n'y a pas S ₀ ).

À partir de S ₁ et S ₂ ...

• Calculez leur somme: sum = S1 + S2
• Calculez leur différence absolue (la plus grande moins la plus petite): diff = |S1 - S2|

• Échangez les deux valeurs de S aux indices de la somme et de la différence:swap(Ssum, Sdiff)

• Augmentez les indices de S avec lesquels vous travaillez. Donc, la prochaine fois, vous calculerez la somme et la différence de S ₂ et S ₃ , et le temps après ce sera S ₃ et S ₄ , etc.

• Répétez ce processus indéfiniment.

Voici les premières étapes de S lorsque ce processus est appliqué. Les crochets []entourent les deux valeurs qui sont sur le point d'être additionnées et différenciées.

S d' origine :

[1 2] 3 4 5 6 7 8 9 10 11 12 ...

Après l' échange de S ₃ ( 3 = 1 + 2) et S ₁ ( 1 = |1 - 2|):

3 [2 1] 4 5 6 7 8 9 10 11 12 ...

Après l' échange de S ₃ et S ₁ :

1 2 [3 4] 5 6 7 8 9 10 11 12 ...

Après l' échange de S ₇ et S ₁ :

7 2 3 [4 5] 6 1 8 9 10 11 12 ...

Après l' échange de S ₉ et S ₁ :

9 2 3 4 [5 6] 1 8 7 10 11 12 ...

Après l' échange de S ₁₁ et S ₁ :

11 2 3 4 5 [6 1] 8 7 10 9 12 ...

Après l' échange de S ₇ et S ₅ :

11 2 3 4 1 6 [5 8] 7 10 9 12 ...

etc.

La séquence SUDSI est définie comme la séquence des premiers éléments de chacune de ces listes. Les premiers termes de la séquence SUDSI sont donc 1 3 1 7 9 11 11.

Voici les 200 premiers termes de la séquence SUDSI (20 par ligne):

1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19 
19 19 19 19 19 19 19 19 57 59 59 59 59 59 59 59 59 59 77 79 
81 83 85 87 89 91 91 91 91 91 91 91 91 91 91 91 91 91 115 115 
121 123 125 127 127 127 127 127 137 139 141 143 145 147 147 147 147 147 147 147 
147 147 147 147 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 167 
167 167 167 167 209 211 211 211 211 211 221 223 223 223 223 223 223 223 223 223 
223 223 243 243 243 243 243 243 257 259 261 263 263 263 263 263 263 263 263 263 
263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 263 
263 263 325 327 329 331 331 331 331 331 331 331 331 331 349 351 351 351 351 351 
361 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363 363

On ne sait pas (du moins pour moi) comment on pourrait prédire les termes futurs. Il semble juste de dire que les termes sont toujours impairs, non décroissants (après le deuxième terme), et que certains nombres sont répétés beaucoup de fois.

Défi

Écrire un programme ou une fonction qui prend en un nombre entier positif n et imprime ou retourne le n ième terme de la suite SUDSI. Par exemple, si n est 1, la sortie est 1, si n est 2, la sortie est 3, si n est 200, la sortie est 363.

Prenez l'entrée de n'importe quelle manière habituelle (stdin / ligne de commande / fonction arg).
La réponse la plus courte en octets l' emporte.
(Ce site code les choses en UTF-8, mais vous pouvez utiliser n'importe quel encodage existant que vous souhaitez.)

Bonus Mathy: (potentiellement éligible à la prime)

• Parlez-moi de la séquence SUDSI. Quel est le modèle sous-jacent à quels nombres en font partie et combien il y en a (et des trucs comme ça)? (Au fait, je n'ai pas trouvé SUDSI sur OEIS .)

Pyth, 45 41 40 38 octets

MXGH_HhugGm@Gtd,s<>GH2.a-@GH@GhHtQr1yQ

J'ai remarqué (comme Martin Büttner), que le nombre maximal affecté d'une étape de permutation à kest 2k + 1. Mais comme nous n'avons que des n - 1étapes, nous n'avons besoin que d'une liste des nombres jusqu'à 2n - 1.

Essayez-le en ligne: Démonstration

M                       define a function g(G, H): return
                        (G is the list of numbers, H is a tuple)
 XGH_H                     a translation of G
                           (replaces the elements in H with the elements in reversed H)
                           in this application it swaps two values in the list G


                        implicit: Q = input()
 u     tQr1yQ           reduce, G = [1, 2, ..., 2*Q-1]
                        for each H in [0, 1, ..., Q - 2]:
                           G = 
  gG...                        g(G, ...)
h                       print the first element of the resulting list

And the second argument ... of the function call g is:

     ,                  create the tuple (
      s<>GH2               sum(G[H:][:2]), 
            .a-@GH@GhH     abs(G[H],G[H+1])
                        )
m@Gtd                   and map each value d to G[d - 1]

Mathematica, 88 octets

Last[f@n_:=n;(r=f@1;{f@a,f@b}={f[b=+##],f[a=Abs[#-#2]]};r)&@@f/@{#,#+1}&/@Range@Input[]]

Il s'agit d'un programme complet, lisant l'entrée à partir d'une invite. C'est une implémentation très directe de la définition, où je garde la trace de la séquence actuelle f(dont les valeurs f[n]par défaut sont n).

Voici une version légèrement plus lisible:

Last[
  f@n_ := n;
  (
    r = f@1;
    {f@a,f@b} = {f[b=+##],f[a=Abs[#-#2]]};
    r
  ) & @@ f /@ {#,#+1} & /@ Range @ Input[]
]

Quelques analyses

J'ai tracé les 2000 premiers éléments de la séquence (ça ne devient pas vraiment plus intéressant par la suite):

La séquence est donc essentiellement linéaire avec la pente 2 et comporte toujours quelques-unes de ces étapes. Il semble que les étapes se développent de façon sublinéaire (si elles ne sont même pas limitées), car elles deviennent à peine perceptibles lorsque vous augmentez le nombre de points que vous tracez.

Nous pouvons justifier la croissance linéaire assez facilement (c'est un peu ondulé, mais je pense que cela résisterait à une preuve rigoureuse par induction): au départ, le nombre maximum affecté d'une étape de permutation à nest n + (n+1) = 2n + 1. Notez également que ces numéros seront toujours déplacés vers 1, depuis |n - (n+1)| = 1. Il n'est donc pas surprenant que nous obtenions des nombres qui sont approximativement 2ndans la séquence. Cependant, nous pouvons également noter que pour les étapes jusqu'à n , S _{n + 1} est toujours limité par n + 1 , ce qui signifie qu'aucune étape de permutation ne peut échanger deux nombres qui sont tous les deux supérieurs à n . Par conséquent, les nombres qui doivent encore être traités seront inférieurs ou égaux à leur valeur initiale. Par conséquent,2n + 1 est également la limite de la séquence elle-même.

Je pense que trouver un argument pour la longueur des étapes sera plus difficile.

CJam, 45 40 39 octets

Juste une approche naïve. Peut être joué plus loin. Manque trop une fonction d'échange de tableau.

ri_K*,\{\:L>2<L1$:+:S@:-z:DL=tDSL=t}/1=

Comment ça fonctionne:

ri_                             "Read the input, convert to integer and copy it";
   K*,                          "Multiply the copy by 20 and get 0 to 20*input-1 array";
      \{ ... }/1=               "Swap and put input on stack and run the loop that many";
                                "times. After the loop, take the second element as";
                                "we have a 0 based array while series is 1 based";
{\:L>2<L1$:+:S@:-z:DL=tDSL=t}
 \:L                            "Swap to put iteration index behind the array";
                                "and store array in L";
    >2<                         "In each loop, the iteration index will be on stack";
                                "Get the two elements from the array starting at that";
       L1$                      "Put the array on stack and copy the tuple";
          :+:S                  "Get the sum and store it in S";
              @:-z:D            "Get the absolute difference of the tuple and store in D";
                    L=t         "Put the element at S diff at sum index";
                       DSL=t    "Put the element at S sum at diff index";

Essayez-le en ligne ici

Haskell, 95 octets

f#n=let b=f$n+1;l=f n+b;r=abs$f n-b;y x|x==l=f r|x==r=f l|1<2=f x in y
p n=foldl(#)id[1..n-1]$1

Exemple d'utilisation: p 70->139

Je ne stocke pas la séquence dans une liste ou un tableau. Je mets à jour à plusieurs reprises la fonction d'identité en fonction avec les deux éléments de l'étape actuelle échangés. Après les nétapes, j'appelle la fonction résultante avec paramètre 1.

J, 63 octets

3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

Utilisation et tests:

   f=.3 :'{.>((1-~{(+,|@-)]{~1+[)|.@:{`[`]}])&.>/(<"*i.1-y),<>:i.3*y'

   f 5
9
   f every 1+i.20
1 3 1 7 9 11 11 11 15 15 19 19 19 19 19 19 19 19 19 19

Essayez-le en ligne ici.

Pyth, 55 53 51

Peut probablement être joué plus loin. nCela pourrait devenir très lent pour les grands, car j'étais paresseux pour savoir combien de temps j'avais besoin d'un tableau et j'en ai juste utilisé un n^n.

Merci à Volatility et Martin Büttner d' avoir souligné que je peux utiliser un maximum de 3n.

KU*3QFNr1QJ@KN=G@tKNAJG,+JG.a-JG=Y@KJ XXKJ@KGGY)@K1

Explication

                   Q = input (implicit)
KU*3Q              K = range(3 * Q)
FNr1Q              for N in range(1, Q):
 J@KN               J = K[N]
 =G@tKN             G = K[1:][N]
 AJG,+JG.a-JG       J, G = J + G, abs(J - G)
 =Y@KJ              Y = K[J]
 XXKJ@KGGY          K[J], K[G] = K[G], Y
)
@K1                print K[1]

Python 2, 117 106 101

j=input();a=range(3*j)
for i in range(1,j):b,c=a[i:i+2];d=abs(b-c);a[b+c],a[d]=a[d],a[b+c]
print a[1]

Utilise un dict(carte) pour enregistrer les valeurs afin d'utiliser des indices arbitraires. g(n)est une fonction renvoyant le ne élément. Il suffit ensuite d'itérer les input-1heures et de sortir le premier élément.

Il s'avère qu'il est plus court en utilisant les méthodes de ma réponse Pyth.

Merci à xnor pour avoir économisé 5 octets.

Aller 150

func f(j int){a:=make([]int,j*2);for i:=range a{a[i]=i};for i:=1;i<j;i++{b,c:=a[i],a[i+1];v:=b-c;if v<0{v*=-1};a[b+c],a[v]=a[v],a[b+c]};println(a[1])}

Non golfé, rien de délicat, principalement volé à @ Pietu1998

func f(j int) {
    a := make([]int, j*2) // Build the array we will be working on
    for i := range a {
        a[i] = i
    }
    for i := 1; i < j; i++ {
        b, c := a[i], a[i+1]
        v := b - c
        if v < 0 {
            v *= -1
        }
        a[b+c], a[v] = a[v], a[b+c]
    }
    println(a[1])
}

http://play.golang.org/p/IWkT0c4Ev5

Java, 162

int f(int n){int a[]=new int[2*n],s,d,x,t;for(x=0;x<2*n;)a[x]=++x;for(x=0;++x<n;){s=a[x]+a[x-1]-1;d=Math.abs(a[x]-a[x-1])-1;t=a[s];a[s]=a[d];a[d]=t;}return a[0];}

Explication

int f(int n) {
    int a[] = new int[2 * n], sum, diff, x, temp;
    for (x = 0; x < 2 * n;) {
        a[x] = ++x;  // set initial array
    }
    for (x = 0; ++x < n;) {
        sum = a[x] + a[x - 1] - 1;
        diff = Math.abs(a[x] - a[x - 1]) - 1;
        temp = a[sum];
        a[sum] = a[diff];
        a[diff] = temp;
    }
    return a[0];
}

dc, 134 132 131 octets

[_1*]sOdsn2*ddslsSsa[ladd:S1-dsa0<P]dsPx1d0rsN:N[la1+dsad;SdS@r1+;SdS@rL@L@r+Ss-d0>Od;SrLsdSsrLs;Sr:S:S1;SladsN:Nlaln>G]dsGxln1-;Nf

Utilisez echo $n $code | dc, où $nest n et $codeest ... le code ( halètement ). Devis au goût.

Edit: À moins que vous ne me harceliez pour une explication, je n'y arriverai jamais.

Perl 5, 131

Une solution naïve (c'est-à-dire une mise en œuvre directe de la définition). Un sous-programme, il prend l'entrée comme une liste de1 s de la longueur souhaitée.

{map$a[$_]=$_,1..3*@_;($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_;$a[1]}

Visualisez sa sortie par exemple print sub...->(1,1,1,1,1).

Explication:

map$a[$_]=$_,1..3*@_ construit le tableau @a , indexant chaque entier de 1 à 3 fois la taille de @_(l'entrée).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_répète la switcheroo plusieurs fois (une fois moins que la taille de @_), la commutation $a[$a[$_-1]+$a[$_]]avec $a[abs($a[$_-1]-$a[$_])]comme$_ va de 2 à la taille @_.

Et puis le sous-programme revient $a[1].

Perl 5 , 90 + 1 (-p) = 91 octets

@a=0..3*$_;$_=(map{@a[$d,$s]=@a[$s=$a[$_]+$a[$_-1],$d=abs$a[$_]-$a[$_-1]];$a[1]}1..$_)[-1]

Essayez-le en ligne!