Generate The SUDSI Sequence

Question

The SUDSI sequence (sum, difference, swap, increment) is a curious integer sequence that appears to exhibit rather chaotic behavior. It can be generated as follows:

Let S be an infinite list of the natural numbers: 1 2 3 4 5 6 .... Let S_i denote the one-indexed ith element of S. So initially, S₁ is 1, S₂ is 2, etc. (there is no S₀).

Starting with S₁ and S₂ ...

• Compute their sum: sum = S1 + S2
• Compute their absolute difference (the larger one minus the smaller one): diff = |S1 - S2|

• Swap the two values in S at the indices of the sum and difference: swap(Ssum, Sdiff)

• Increment the indices of S you are working with. So next time you will compute the sum and difference of S₂ and S₃, and the time after that it will be S₃ and S₄, etc.

• Repeat this process indefinitely.

Here are the first few stages of S as this process is applied. The brackets [] surround the two values that are about to be summed and differenced.

Original S:

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

After S₃ (3 = 1 + 2) and S₁ (1 = |1 - 2|) are swapped:

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

After S₃ and S₁ are swapped:

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

After S₇ and S₁ are swapped:

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

After S₉ and S₁ are swapped:

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

After S₁₁ and S₁ are swapped:

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

After S₇ and S₅ are swapped:

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

etc.

The SUDSI sequence is defined as the sequence of the first elements in each of these lists. So the first few terms of the SUDSI sequence are 1 3 1 7 9 11 11.

Here are the first 200 terms of the SUDSI sequence (20 per line):

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

It is unclear (to me at least) how one might predict future terms. It only feels safe to say that that the terms are always odd, non-decreasing (after the second term), and that some numbers are repeated lots of times.

Challenge

Write a program or function that takes in a positive integer n and prints or returns the nth term of the SUDSI sequence. For example, if n is 1, the output is 1, if n is 2, the output is 3, if n is 200, the output is 363.

Take input in any usual way (stdin/command line/function arg).
The shortest answer in bytes wins.
(That site encodes things in UTF-8, but you may use any darn existing encoding you want.)

Mathy bonus: (potentially eligible for bounty)

• Tell me more about the SUDSI sequence. What's the underlying pattern to what numbers are part of it and how many of them there are (and stuff like that)? (I couldn't find SUDSI on OEIS by the way.)

Answer 1

Pyth, 45 41 40 38 bytes

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

I noticed (as did Martin Büttner), that the maximum affected number of a permutation step at k is 2k + 1. But since we only have n - 1, steps, we only need a list of the numbers up to 2n - 1.

Try it online: Demonstration

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]

Answer 2

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

This is a full program, reading the input from a prompt. It's a very direct implementation of the definition, where I'm keeping track of the current sequence in f (whose values f[n] default to n).

Here is a slightly more readable version:

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

Some analysis

I've plotted the first 2000 elements of the sequence (it doesn't really get more interesting afterwards):

So the sequence is essentially linear with slope 2 and always has a few of those steps. It seems that the steps grow sublinearly (if they aren't even bounded), since they become barely noticeable as you increase the number of points you plot.

We can justify the linear growth quite easily (this is a bit handwavy, but I think it would hold up to a rigorous proof by induction): initially, the maximum affected number of a permutation step at n is n + (n+1) = 2n + 1. Also note that these numbers will always be moved to 1, since |n - (n+1)| = 1. So it's not surprising that we get numbers which are approximately 2n in the sequence. However, we can also note that for steps up to n, S_n+1 is always bounded by n+1, which means that no swapping step can swap two numbers which are both greater than n. Hence, numbers that still need to be processed will be less than or equal to their initial value. Hence, 2n + 1 is also the bound for the sequence itself.

I think finding an argument for the length of the steps will be trickier.

Answer 3

CJam, 45 40 39 bytes

Just a naive approach. Can be golfed further. Missing a array swap function too much.

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

How it works:

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

Try it online here

Answer 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

Usage example: p 70 -> 139

I do not store the sequence in a list or array. I repeatedly update the identity function to a function with the two elements of the current step swapped. After n steps I call the resulting function with parameter 1.

Answer 5

J, 63 bytes

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

Usage and 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

Try it online here.

Answer 6

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]

Uses a dict (map) to save the values to use arbitrary indices. g(n) is a function returning the nth item. Then just iterates input-1 times and outputs the first item.

It turns out it's shorter using the methods from my Pyth answer.

Thanks to xnor for saving 5 bytes.

Answer 7

Pyth, 55 53 51

Can probably be golfed further. Might get really slow for large n as I was lazy to figure out how long of an array I'd need and just used a n^n one.

Thanks to Volatility and Martin Büttner for pointing out that I can use a maximum of 3n.

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

Explanation

                   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]

Answer 8

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, nothing tricky, mostly stolen from @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

Answer 9

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

Explanation

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

Answer 10

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, where $n is n and $code is...the code (gasp). Quote to taste.

Edit: Unless you pester me for an explanation, I will never get around to it.

Answer 11

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]

Try it online!

Answer 12

Perl 5, 131

A naive solution (i.e. a direct implementation of the definition). A subroutine, it takes input as a list of 1s of the desired length.

{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 its output by e.g. print sub...->(1,1,1,1,1).

Explanation:

map$a[$_]=$_,1..3*@_ builds the array @a, indexing each integer by itself from 1 to 3 times the size of @_ (the input).

($a[$a[$_-1]+$a[$_]],$a[abs($a[$_-1]-$a[$_])])=($a[abs($a[$_-1]-$a[$_])],$a[$a[$_-1]+$a[$_]])for 2..@_ repeats the switcheroo repeatedly (one fewer times than the size of @_), switching $a[$a[$_-1]+$a[$_]] with $a[abs($a[$_-1]-$a[$_])] as $_ ranges from 2 to the size of @_.

And then the subroutine returns $a[1].