Gere a sequência SUDSI

15

A sequência SUDSI ( su m, d ifference, s WAP, i ncrement) é uma sequência de número inteiro curioso que parece exibir comportamento caótico. Pode ser gerado da seguinte maneira:

Deixe- S ser uma lista infinita dos números naturais: 1 2 3 4 5 6 .... Deixe S i denotar a uma indexados i -ésimo elemento de S . Então, inicialmente, S 1 é 1, S 2 é 2, etc. (não há S 0 ).

Começando com S 1 e S 2 ...

  • Calcule a soma deles: sum = S1 + S2
  • Calcule a diferença absoluta (quanto maior menos o menor): diff = |S1 - S2|
  • Troque os dois valores em S nos índices da soma e da diferença:swap(Ssum, Sdiff)

  • Incremente os índices de S com os quais você está trabalhando. Então, da próxima vez, você calculará a soma e a diferença de S 2 e S 3 , e o tempo depois disso será S 3 e S 4 , etc.

  • Repita esse processo indefinidamente.

Aqui estão os primeiros estágios de S à medida que esse processo é aplicado. Os colchetes []envolvem os dois valores que estão prestes a ser somados e diferenciados.

S original :

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

Depois que S 3 ( 3 = 1 + 2) e S 1 ( 1 = |1 - 2|) são trocados:

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

Depois que S 3 e S 1 são trocados:

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

Depois que S 7 e S 1 são trocados:

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

Depois que S 9 e S 1 são trocados:

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

Depois que S 11 e S 1 são trocados:

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

Depois que S 7 e S 5 são trocados:

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

etc.

A sequência SUDSI é definida como a sequência dos primeiros elementos em cada uma dessas listas. Portanto, os primeiros termos da sequência SUDSI são 1 3 1 7 9 11 11.

Aqui estão os primeiros 200 termos da sequência SUDSI (20 por linha):

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

Não está claro (pelo menos para mim) como se pode prever termos futuros. Parece seguro dizer que os termos são sempre ímpares, não diminuem (após o segundo mandato) e que alguns números são repetidos várias vezes.

Desafio

Escrever um programa ou função que leva em um número inteiro positivo n e gravuras ou retorna o n ésimo termo da sequência SUDSI. Por exemplo, se n for 1, a saída será 1, se n for 2, a saída será 3, se n for 200, a saída será 363.

Tome entrada da maneira usual (stdin / linha de comando / função arg).
A resposta mais curta em bytes vence.
(Esse site codifica as coisas em UTF-8, mas você pode usar qualquer codificação existente que desejar.)

Bônus de Mathy: (potencialmente elegível para recompensa)

  • Conte-me mais sobre a sequência SUDSI. Qual é o padrão subjacente a quais números fazem parte dele e quantos deles existem (e coisas assim)? (A propósito, não consegui encontrar o SUDSI no OEIS .)
Passatempos de Calvin
fonte
Como de novo. Melhor não vincular do que criar confusão sobre codificação.
Optimizer
@ Optimizer Estive vinculando a esse contador de bytes com o mesmo fraseado há muito tempo . Por que de repente causaria mais confusão do que nunca?
Hobbies de Calvin
1
@orlp Acho que esse seria um bom recurso adicional , mas pessoalmente confio em poder copiar e colar, pois raramente tenho arquivos de origem para meus envios.
Martin Ender
1
@orlp Mas quem vai precisar disso? Eles podem ver o tamanho diretamente se tiverem o arquivo. E não é tão fácil remover a nova linha no final de alguns sistemas operacionais.
jimmy23013
2
@ MartinBüttner Eu estava entediado: meta.codegolf.stackexchange.com/questions/4944/…
orlp:

Respostas:

5

Pitão, 45 41 40 38 bytes

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

Notei (como Martin Büttner), que o número máximo afetado de uma etapa de permutação em ké 2k + 1. Mas como temos apenas n - 1etapas, precisamos apenas de uma lista dos números até 2n - 1.

Experimente online: Demonstração

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]
Jakube
fonte
Existe uma multa para usar Pyth fora de uma biblioteca?
Alex A.
1
@Alex A. Haha, não. Mas há um para não devolver livros.
Jakube 25/03
18

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 é um programa completo, lendo a entrada de um prompt. É uma implementação muito direta da definição, onde eu acompanho a sequência atual emf (cujos valores f[n]padrão são n).

Aqui está uma versão um pouco mais legível:

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

Alguma análise

Plotamos os primeiros 2000 elementos da sequência (na verdade não fica mais interessante depois):

insira a descrição da imagem aqui

Portanto, a sequência é essencialmente linear com a inclinação 2 e sempre possui algumas dessas etapas. Parece que os passos crescem de forma sublinear (se eles nem são limitados), pois se tornam quase imperceptíveis à medida que você aumenta o número de pontos traçados.

Podemos justificar o crescimento linear com bastante facilidade (isso é um pouco handwavy, mas eu acho que iria realizar-se a uma prova rigorosa por indução): inicialmente, o número máximo afetada de uma etapa de permutação em né n + (n+1) = 2n + 1. Observe também que esses números sempre serão movidos para 1, desde |n - (n+1)| = 1. Portanto, não surpreende que tenhamos números aproximadamente 2nna sequência. No entanto, também podemos observar que para as etapas até n , S n + 1 é sempre limitado por n + 1 , o que significa que nenhuma etapa de troca pode trocar dois números que são maiores que n . Portanto, os números que ainda precisam ser processados ​​serão menores ou iguais ao seu valor inicial. Conseqüentemente,2n + 1 também é o limite para a própria sequência.

Acho que encontrar um argumento para a extensão das etapas será mais complicado.

Martin Ender
fonte
3
+1 para uma boa solução, mas principalmente para a análise muito interessante e informativa!
Alex A.
4

CJam, 45 40 39 bytes

Apenas uma abordagem ingênua. Pode ser jogado ainda mais. Falta muito na função de troca de matriz.

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

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

Experimente online aqui

Optimizer
fonte
4

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

Exemplo de uso: p 70->139

Não guardo a sequência em uma lista ou matriz. Atualizo repetidamente a função de identidade para uma função com os dois elementos da etapa atual trocados. Depois de npassos que eu chamar a função resultante com parâmetro 1.

nimi
fonte
2

J, 63 bytes

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

Uso e testes:

   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

Experimente online aqui.

randomra
fonte
1

Pyth, 55 53 51

Provavelmente pode ser jogado ainda mais. Pode ficar muito lento, npois eu estava com preguiça de descobrir quanto tempo precisava de uma matriz e apenas a usei n^n.

Agradeço a Volatility e Martin Büttner por apontar que posso usar no máximo 3n.

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

Explicação

                   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]
PurkkaKoodari
fonte
Fiz alguns testes e parece que o comprimento da lista necessária converge 2*npara grande n, com um máximo de 3*npara n=1.
Volatilidade
Volatilidade @ Essencialmente, o máximo é o 2n+1que, como você diz, é o máximo em 3para n=1e (de certa forma) converge para 2n. Isso não é muito surpreendente, já que é o máximo para a sequência não-permutada e nenhuma etapa do processo pode aumentar um número que ainda está à frente. Eu posso adicionar isso à minha resposta.
Martin Ender
Vejo que você já está colocando minha .aextensão em um bom trabalho! Há muito mais guloseimas a caminho, mas isaac está dormindo no momento: github.com/isaacg1/pyth/pull/32
orlp
@orlp, na verdade eu li os documentos enquanto escrevia o código (eu geralmente uso o doc.txtGitHub no manual) e vi a atualização. Felizmente, como eu poderia simplesmente ignorá-lo e escrever uma implementação personalizada ...
PurkkaKoodari
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]

Usa um dict(mapa) para salvar os valores para usar índices arbitrários. g(n)é uma função retornando o nitem th. Em seguida, apenas itera os input-1tempos e gera o primeiro item.

Acontece que é mais curto usando os métodos da minha resposta Pyth.

Obrigado ao xnor por salvar 5 bytes.

PurkkaKoodari
fonte
Você pode usar a lista de desembalar: b,c=a[i:i+2]. Além disso, b+cé curto o suficiente para salvá-lo em uma variável e sperde caracteres ao escrever apenas duas vezes.
xnor 25/03
1

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

Ungolfed, nada complicado, principalmente roubado 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

Kristoffer Sall-Storgaard
fonte
1

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

Explicação

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];
}
Ypnypn
fonte
Você pode salvar dois bytes movendo o segundo corpo do loop para a cláusula de incremento da instrução for. (Separe as declarações com commata em vez de semicola.)
AJMansfield
1

dc, 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

Use echo $n $code | dc, onde $nestá n e $codeé ... o código ( suspiro ). Cite a gosto.

Edit: A menos que você me incomode por uma explicação, eu nunca vou dar a volta a isso.

Joe
fonte
Preciso adicionar três bytes para o `-e`?
Joe
@ Sir, acontece que você não! [ codegolf.stackexchange.com/questions/25670/…
Joe
Isso foi uma conversa com você?
NoOneIsHere
@NoOneIsHere: Sim, com certeza foi. Era uma pergunta aberta a qualquer pessoa, mas encontrei a resposta.
31416 Joe
0

Perl 5, 131

Uma solução ingênua (isto é, uma implementação direta da definição). Uma sub-rotina, recebe a entrada como uma lista de 1s do comprimento desejado.

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

Visualize sua saída por exemplo print sub...->(1,1,1,1,1).

Explicação:

map$a[$_]=$_,1..3*@_constrói a matriz @a, indexando cada número inteiro de 1 a 3 vezes o tamanho de @_(a entrada).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_repete o switcheroo repetidamente (um menor número de vezes do que o tamanho de @_), alternando $a[$a[$_-1]+$a[$_]]com $a[abs($a[$_-1]-$a[$_])]a $_intervalos de 2 ao tamanho de @_.

E então a sub-rotina retorna $a[1].

msh210
fonte
0

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]

Experimente online!

Xcali
fonte