15
\$\begingroup\$

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 Si denote the one-indexed ith element of S. So initially, S1 is 1, S2 is 2, etc. (there is no S0).

Starting with S1 and S2 ...

  • 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 S2 and S3, and the time after that it will be S3 and S4, 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 S3 (3 = 1 + 2) and S1 (1 = |1 - 2|) are swapped:

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

After S3 and S1 are swapped:

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

After S7 and S1 are swapped:

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

After S9 and S1 are swapped:

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

After S11 and S1 are swapped:

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

After S7 and S5 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.)
\$\endgroup\$
8
  • \$\begingroup\$ As again . Better not link than creating confusion about encoding. \$\endgroup\$
    – Optimizer
    Mar 25, 2015 at 8:54
  • \$\begingroup\$ @Optimizer I've been linking to that byte counter with the same phrasing for ages. Why would it suddenly cause more confusion than it ever did? \$\endgroup\$ Mar 25, 2015 at 8:59
  • 1
    \$\begingroup\$ @orlp I guess that would be a nice additional feature, but I personally rely on being able to copy-paste since I rarely have source files for my submissions. \$\endgroup\$ Mar 25, 2015 at 11:21
  • 1
    \$\begingroup\$ @orlp But who will need that anyway? They can see the size directly if they had the file. And it is not that easy to remove the newline in the end in some operating systems. \$\endgroup\$
    – jimmy23013
    Mar 25, 2015 at 12:50
  • 2
    \$\begingroup\$ @MartinBüttner I was bored: meta.codegolf.stackexchange.com/questions/4944/… \$\endgroup\$
    – orlp
    Mar 25, 2015 at 13:51

12 Answers 12

18
\$\begingroup\$

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):

enter image description here

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, Sn+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.

\$\endgroup\$
1
  • 3
    \$\begingroup\$ +1 for a good solution but mostly for the very interesting and informative analysis! \$\endgroup\$
    – Alex A.
    Mar 25, 2015 at 14:33
5
\$\begingroup\$

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]
\$\endgroup\$
2
  • \$\begingroup\$ Is there a fine for using Pyth outside of a library? \$\endgroup\$
    – Alex A.
    Mar 25, 2015 at 14:34
  • 1
    \$\begingroup\$ @Alex A. Haha, no. But there's one for not returning books. \$\endgroup\$
    – Jakube
    Mar 25, 2015 at 14:42
4
\$\begingroup\$

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

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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]
\$\endgroup\$
4
  • \$\begingroup\$ I ran some tests, and it seems that the required list length converges to 2*n for large n, with a maximum of 3*n for n=1. \$\endgroup\$
    – Volatility
    Mar 25, 2015 at 10:14
  • \$\begingroup\$ @Volatility Essentially, the maximum is 2n+1, which as you say has it's maximum at 3 for n=1 and (in a way) converges to 2n. This isn't too surprising since that's the maximum for the unpermuted sequence, and no step in the process can increase a number that's still ahead. I might add this to my answer. \$\endgroup\$ Mar 25, 2015 at 10:27
  • \$\begingroup\$ I see you're already putting my .a extension to good work! There's a lot more goodies on the way, but isaac is sleeping right now: github.com/isaacg1/pyth/pull/32 \$\endgroup\$
    – orlp
    Mar 25, 2015 at 11:16
  • \$\begingroup\$ @orlp, I actually happened to read the docs while writing the code (I usually use the doc.txt on GitHub for a manual) and saw the update. Fortunately, as I could've just skipped it and written a custom implementation... \$\endgroup\$ Mar 25, 2015 at 11:23
1
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ You can use list unpacking: b,c=a[i:i+2]. Also, b+c is short enough that saving it to a variable s loses chars over just writing it twice. \$\endgroup\$
    – xnor
    Mar 25, 2015 at 11:09
1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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];
}
\$\endgroup\$
1
  • \$\begingroup\$ You can save two bytes by moving the second loop body into the increment clause of the for statement. (Separate the statements with commata rather than semicola.) \$\endgroup\$ Mar 29, 2015 at 15:31
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Do I need to add three bytes for the ` -e`? \$\endgroup\$
    – juh
    Jun 17, 2016 at 2:14
  • \$\begingroup\$ @Sir, it turns out you do not! [codegolf.stackexchange.com/questions/25670/… \$\endgroup\$
    – juh
    Jul 2, 2016 at 19:19
  • \$\begingroup\$ Was that a conversation with yourself? \$\endgroup\$ Jul 3, 2016 at 19:46
  • \$\begingroup\$ @NoOneIsHere: Yep, sure was. It was a question open to anyone, but I found the answer. \$\endgroup\$
    – juh
    Jul 3, 2016 at 21:39
0
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.