La secuencia SUDSI ( su m, d ifference, s wap, i ncrement) es una secuencia entera curiosa que parece exhibir un comportamiento bastante caótico. Se puede generar de la siguiente manera:

Deje que S sea una lista infinita de los números naturales: 1 2 3 4 5 6 .... Let S _i denota el uno indexados i -ésimo elemento de S . Inicialmente, S ₁ es 1, S ₂ es 2, etc. (no hay S ₀ ).

Comenzando con S ₁ y S ₂ ...

• Calcule su suma: sum = S1 + S2
• Calcule su diferencia absoluta (la más grande menos la más pequeña): diff = |S1 - S2|

• Cambie los dos valores en S en los índices de la suma y la diferencia:swap(Ssum, Sdiff)

• Incremente los índices de S con los que está trabajando. Entonces, la próxima vez calculará la suma y la diferencia de S ₂ y S ₃ , y el tiempo posterior será S ₃ y S ₄ , etc.

• Repita este proceso indefinidamente.

Aquí están las primeras etapas de S a medida que se aplica este proceso. Los corchetes []rodean los dos valores que están a punto de sumarse y diferenciarse.

S original :

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

Después de intercambiar S ₃ ( 3 = 1 + 2) y S ₁ ( 1 = |1 - 2|):

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

Después de intercambiar S ₃ y S ₁ :

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

Después _de intercambiar S ₇ y S ₁ :

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

Después _de intercambiar S ₉ y S ₁ :

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

Después _de intercambiar S ₁₁ y S ₁ :

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

Después _de intercambiar S ₇ y S ₅ :

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

etc.

La secuencia SUDSI se define como la secuencia de los primeros elementos en cada una de estas listas. Entonces, los primeros términos de la secuencia SUDSI son 1 3 1 7 9 11 11.

Aquí están los primeros 200 términos de la secuencia SUDSI (20 por línea):

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

No está claro (al menos para mí) cómo uno podría predecir términos futuros. Solo se siente seguro decir que los términos son siempre impares, no decrecientes (después del segundo término), y que algunos números se repiten muchas veces.

Desafío

Escribir un programa o función que toma en un número entero positivo n y grabados o devuelve el n º término de la secuencia de SUDSI. Por ejemplo, si n es 1, la salida es 1, si n es 2, la salida es 3, si n es 200, la salida es 363.

Tome la entrada de la forma habitual (stdin / línea de comando / función arg).
La respuesta más corta en bytes gana.
(Ese sitio codifica cosas en UTF-8, pero puede usar cualquier codificación existente que desee).

Bono Mathy: (potencialmente elegible para recompensa)

• Cuéntame más sobre la secuencia SUDSI. ¿Cuál es el patrón subyacente de qué números son parte de él y cuántos hay (y cosas así)? (Por cierto, no pude encontrar SUDSI en OEIS ).

Pyth, 45 41 40 38 bytes

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

Noté (como lo hizo Martin Büttner), que el número máximo afectado de un paso de permutación kes 2k + 1. Pero como solo tenemos n - 1pasos, solo necesitamos una lista de los números hasta 2n - 1.

Pruébelo en línea: demostración

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 bytes

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

Este es un programa completo, que lee la entrada de un mensaje. Es una implementación muy directa de la definición, donde hago un seguimiento de la secuencia actual en f(cuyos valores f[n]predeterminados son n).

Aquí hay una versión un poco más legible:

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

Un poco de análisis

He trazado los primeros 2000 elementos de la secuencia (realmente no se vuelve más interesante después):

Entonces, la secuencia es esencialmente lineal con pendiente 2 y siempre tiene algunos de esos pasos. Parece que los pasos crecen sublinealmente (si ni siquiera están delimitados), ya que apenas se notan a medida que aumenta la cantidad de puntos que traza.

Podemos justificar el crecimiento lineal con bastante facilidad (esto es un poco ondulado, pero creo que resistiría una prueba rigurosa por inducción): inicialmente, el número máximo afectado de un paso de permutación nes n + (n+1) = 2n + 1. También tenga en cuenta que estos números siempre se moverán a 1, desde entonces |n - (n+1)| = 1. Por lo tanto, no es sorprendente que obtengamos números que están aproximadamente 2nen la secuencia. Sin embargo, también podemos observar que para los pasos hasta n , S _{n + 1} siempre está limitado por n + 1 , lo que significa que ningún paso de intercambio puede intercambiar dos números que sean mayores que n . Por lo tanto, los números que aún deben procesarse serán menores o iguales a su valor inicial. Por lo tanto,2n + 1 es también el límite de la secuencia misma.

Creo que encontrar un argumento para la longitud de los pasos será más complicado.

CJam, 45 40 39 bytes

Solo un enfoque ingenuo. Se puede jugar más al golf. Falta una función de intercambio de matriz demasiado.

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

Cómo funciona:

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";

Pruébalo en línea aquí

Haskell, 95 bytes

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

Ejemplo de uso: p 70->139

No almaceno la secuencia en una lista o matriz. Actualizo repetidamente la función de identidad a una función con los dos elementos del paso actual intercambiados. Después de los npasos, llamo a la función resultante con parámetro 1.

J, 63 bytes

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

Uso y pruebas:

   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

Pruébelo en línea aquí.

Pyth 55 53 51

Probablemente se pueda jugar más al golf. Podría ser muy lento para los grandes, nya que era flojo para averiguar cuánto tiempo necesitaría una matriz y simplemente utilicé una n^n.

Gracias a Volatility y Martin Büttner por señalar que puedo usar un máximo de 3n.

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

Explicación

                   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]

Utiliza un dict(mapa) para guardar los valores para usar índices arbitrarios. g(n)es una función que devuelve el nelemento th. Luego solo itera input-1veces y genera el primer elemento.

Resulta que es más corto usando los métodos de mi respuesta Pyth.

Gracias a xnor por guardar 5 bytes.

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

Sin golf, nada complicado, mayormente robado de @ 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];}

Explicación

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

corriente continua, 134 132 131 bytes

[_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

Uso echo $n $code | dc, donde $nes N y $codees el código ... ( suspiro ). Cita al gusto.

Editar: A menos que me molestes para obtener una explicación, nunca lo conseguiré.

Perl 5, 131

Una solución ingenua (es decir, una implementación directa de la definición). Una subrutina, toma la entrada como una lista de 1s de la longitud deseada.

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

Visualice su salida por ej print sub...->(1,1,1,1,1).

Explicación:

map$a[$_]=$_,1..3*@_construye la matriz @a, indexando cada entero por sí mismo de 1 a 3 veces el tamaño de @_(la entrada).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_repite el switcheroo repetidamente (uno menos veces que el tamaño de @_), la conmutación $a[$a[$_-1]+$a[$_]]con $a[abs($a[$_-1]-$a[$_])]como $_rangos de 2 al tamaño de @_.

Y luego vuelve la subrutina $a[1].

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

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

Pruébalo en línea!