Urutan SUDSI ( su m, d ifference, s wap, i ncrement) adalah deretan integer yang aneh yang nampak menunjukkan perilaku yang agak kacau. Ini dapat dihasilkan sebagai berikut:

Biarkan S menjadi daftar tak terbatas dari alam nomor: 1 2 3 4 5 6 .... Biarkan S _i menunjukkan satu-diindeks i th elemen S . Jadi pada awalnya, S ₁ adalah 1, S ₂ adalah 2, dll. (Tidak ada S ₀ ).

Dimulai dengan S ₁ dan S ₂ ...

• Hitung jumlah mereka: sum = S1 + S2
• Hitung perbedaan absolut mereka (yang lebih besar dikurangi yang lebih kecil): diff = |S1 - S2|

• Tukar kedua nilai dalam S pada indeks jumlah dan perbedaan:swap(Ssum, Sdiff)

• Tambahkan indeks S yang sedang Anda kerjakan. Jadi lain kali Anda akan menghitung jumlah dan selisih S ₂ dan S ₃ , dan waktu setelah itu akan menjadi S ₃ dan S ₄ , dll.

• Ulangi proses ini tanpa batas.

Inilah beberapa tahap pertama S saat proses ini diterapkan. Tanda kurung []mengelilingi dua nilai yang akan dijumlahkan dan dibedakan.

S asli :

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

Setelah S ₃ ( 3 = 1 + 2) dan S ₁ ( 1 = |1 - 2|) ditukar:

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

Setelah S ₃ dan S ₁ ditukar:

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

Setelah S ₇ dan S ₁ ditukar:

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

Setelah S ₉ dan S ₁ ditukar:

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

Setelah S ₁₁ dan S ₁ ditukar:

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

Setelah S ₇ dan S ₅ ditukar:

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

dll.

Urutan SUDSI didefinisikan sebagai urutan elemen pertama dalam setiap daftar ini. Jadi beberapa syarat pertama dari urutan SUDSI adalah 1 3 1 7 9 11 11.

Berikut adalah 200 syarat pertama dari urutan SUDSI (20 per baris):

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

Tidak jelas (setidaknya bagi saya) bagaimana seseorang dapat memprediksi masa depan. Hanya merasa aman untuk mengatakan bahwa istilah tersebut selalu aneh, tidak menurun (setelah periode kedua), dan bahwa beberapa angka diulang berkali-kali.

Tantangan

Menulis sebuah program atau fungsi yang mengambil di bilangan bulat positif n dan mencetak atau mengembalikan n th jangka urutan SUDSI. Misalnya, jika n adalah 1, outputnya adalah 1, jika n adalah 2, outputnya adalah 3, jika n adalah 200, outputnya adalah 363.

Ambil input dengan cara biasa (stdin / command line / function arg).
Jawaban terpendek dalam byte menang.
(Situs itu mengkodekan hal-hal dalam UTF-8, tetapi Anda dapat menggunakan pengkodean apa pun yang Anda inginkan.)

Bonus Mathy: (berpotensi memenuhi syarat untuk hadiah)

• Ceritakan lebih banyak tentang urutan SUDSI. Apa pola yang mendasari angka apa yang merupakan bagian dari itu dan berapa banyak dari mereka (dan hal-hal seperti itu)? (Omong -omong, saya tidak dapat menemukan SUDSI di OEIS .)

Pyth, 45 41 40 38 byte

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

Saya perhatikan (seperti halnya Martin Büttner), bahwa jumlah maksimum yang terpengaruh dari langkah permutasi kadalah 2k + 1. Tetapi karena kita hanya memiliki n - 1, langkah-langkah, kita hanya perlu daftar nomor hingga 2n - 1.

Cobalah online: Peragaan

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 byte

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

Ini adalah program lengkap, membaca input dari prompt. Ini adalah implementasi definisi yang sangat langsung, di mana saya melacak urutan saat ini f(yang nilai f[n]defaultnya adalahn ).

Ini adalah versi yang sedikit lebih mudah dibaca:

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

Beberapa analisis

Saya telah merencanakan elemen 2000 pertama dari urutan (itu tidak benar-benar menjadi lebih menarik setelah itu):

Jadi urutannya pada dasarnya linier dengan kemiringan 2 dan selalu memiliki beberapa langkah tersebut. Tampaknya langkah-langkahnya tumbuh secara sublinear (jika tidak dibatasi), karena langkah tersebut menjadi hampir tidak terlihat ketika Anda meningkatkan jumlah poin yang Anda plot.

Kita dapat menjustifikasi pertumbuhan linier dengan cukup mudah (ini adalah sedikit handwavy, tapi saya pikir ini akan tahan terhadap bukti yang kuat melalui induksi): pada awalnya, jumlah maksimum yang terpengaruh dari langkah permutasi nadalah n + (n+1) = 2n + 1. Perhatikan juga bahwa angka-angka ini akan selalu dipindahkan ke 1, karena |n - (n+1)| = 1. Jadi tidak mengherankan bahwa kita mendapatkan angka yang kira-kira 2nberurutan. Namun, kami juga dapat mencatat bahwa untuk langkah hingga n , S _{n + 1} selalu dibatasi oleh n +1 , yang berarti bahwa tidak ada langkah swapping yang dapat menukar dua angka yang keduanya lebih besar dari n . Oleh karena itu, angka yang masih perlu diproses akan kurang dari atau sama dengan nilai awal mereka. Karenanya,2n + 1 juga terikat untuk urutan itu sendiri.

Saya pikir menemukan argumen untuk panjang langkah akan lebih sulit.

CJam, 45 40 39 byte

Hanya pendekatan yang naif. Dapat bermain golf lebih lanjut. Fungsi swap array hilang terlalu banyak.

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

Bagaimana itu bekerja:

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

Cobalah online di sini

Haskell, 95 byte

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

Contoh penggunaan: p 70->139

Saya tidak menyimpan urutan dalam daftar atau larik. Saya berulang kali memperbarui fungsi identitas ke fungsi dengan dua elemen dari langkah saat ini ditukar. Setelah nlangkah-langkah saya memanggil fungsi yang dihasilkan dengan parameter 1.

J, 63 byte

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

Penggunaan dan tes:

   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

Cobalah online di sini.

Pyth, 55 53 51

Mungkin bisa bermain golf lebih lanjut. Mungkin menjadi sangat lambat untuk besar nkarena saya malas untuk mencari tahu berapa lama array yang saya butuhkan dan hanya menggunakan n^nsatu.

Terima kasih kepada Volatility dan Martin Büttner karena telah menunjukkan bahwa saya dapat menggunakan maksimum 3n.

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

Penjelasan

                   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]

Menggunakan dict(peta) untuk menyimpan nilai untuk menggunakan indeks arbitrer.g(n)adalah fungsi mengembalikan nitem th. Kemudian hanya mengulangi input-1waktu dan menampilkan item pertama.

Ternyata lebih pendek menggunakan metode dari jawaban Pyth saya.

Terima kasih kepada xnor karena telah menghemat 5 byte.

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

Tidak disatukan, tidak ada yang rumit, sebagian besar dicuri dari @ 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

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

Penjelasan

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 byte

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

Gunakan echo $n $code | dc, di mana $nadalah n dan $codeadalah ... kode ( terkesiap ). Kutip secukupnya.

Sunting: Kecuali jika Anda mengganggu saya untuk penjelasan, saya tidak akan pernah sampai ke sana.

Perl 5, 131

Solusi naif (yaitu implementasi langsung dari definisi). Subrutin, dibutuhkan input sebagai daftar 1panjang yang diinginkan.

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

Visualisasikan hasilnya dengan mis print sub...->(1,1,1,1,1).

Penjelasan:

map$a[$_]=$_,1..3*@_membangun array @a, mengindeks setiap integer dengan sendirinya dari 1 hingga 3 kali ukuran @_(input).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_ulangi switcheroo berulang kali (satu kali lebih sedikit dari ukuran @_), beralih$a[$a[$_-1]+$a[$_]] dengan $a[abs($a[$_-1]-$a[$_])]sebagai $_berkisar dari 2 sampai ukuran @_.

Dan kemudian subrutin kembali $a[1].

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

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

Cobalah online!