27
\$\begingroup\$

Today we'll look at a sequence a, related to the Collatz function f:

enter image description here

We call a sequence of the form z, f(z), f(f(z)), … a Collatz sequence.

The first number in our sequence, a(1), is 0. Under repeated application of f, it falls into a cycle 0 → 0 → …

The smallest number we haven't seen yet is 1, making a(2) = 1. Under repeated application of f, it falls into a cycle 1 → 4 → 2 → 1 → …

Now we have seen the number 2 in the cycle above, so the next smallest number is a(3) = 3, falling into the cycle 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1 → 4 → 2 → 1 → …

In all above cycles we've seen 4 and 5 already, so the next number is a(4) = 6.

By now you should get the idea. a(n) is the smallest number that was not part of any Collatz sequences for all a(1), …, a(n − 1).

Write a program or function that, given an positive integer n, returns a(n). Shortest code in bytes wins.


Testcases:

1  -> 0
2  -> 1
3  -> 3
4  -> 6
5  -> 7
6  -> 9
7  -> 12
8  -> 15
9  -> 18
10 -> 19
50 -> 114

(This is OEIS sequence A061641.)

\$\endgroup\$
  • 1
    \$\begingroup\$ Obligatory OEIS \$\endgroup\$ – FryAmTheEggman Aug 12 '16 at 20:26
  • 3
    \$\begingroup\$ Can input n be 0-based? \$\endgroup\$ – Luis Mendo Aug 12 '16 at 22:20
  • \$\begingroup\$ a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2 \$\endgroup\$ – Karl Napf Aug 12 '16 at 23:08
  • \$\begingroup\$ @LuisMendo Sorry, I somehow missed your message. No, reproduce the exact sequence as in the challenge. \$\endgroup\$ – orlp Aug 13 '16 at 9:14
  • \$\begingroup\$ If a isn't 0-based I don't understand why you seem to be "talking 0-based" here: a(n) is the smallest number that was not part of any Collatz sequences for all a(0), …, a(n − 1). \$\endgroup\$ – daniero Aug 13 '16 at 16:29

11 Answers 11

5
\$\begingroup\$

Jelly, 20 19 bytes

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ
Ç¡Ṫ

Try it online! or verify all test cases.

How it works

Ç¡Ṫ              Main link. No explicit arguments. Default argument: 0
 ¡               Read an integer n from STDIN and do the following n times.
Ç                  Call the helper link.
  Ṫ              Tail; extract the last element of the resulting array.


ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ  Helper link. Argument: A (array)

  J              Yield all 1-based indices of A, i.e., [1, ..., len(A)]. Since 0
                 belongs to A, there is at least one index that does belong to A.
ḟ@               Filter-false swapped; remove all indices that belong to A.
   Ḣ             Head; extract the first index (i) that hasn't been removed.
           ÐĿ    Call the quicklink to the left on i, then until the results are no
                 longer unique. Collect all unique results in an array.
         Ḃ?      If the last bit of the return value (r) is 1:
       $           Apply the monadic 3-link chain to the left to r.
    ×3‘              Yield 3r + 1.
        H        Else, halve r.
              Ṛ  Yield A, reversed.
             ;   Concatenate the results array with reversed A.

After n iterations, the value of a(n + 1) will be at the beginning of the array. Since we concatenate the new array with a reversed copy of the old one, this means that a(n) will be at the end.

\$\endgroup\$
9
\$\begingroup\$

Haskell, 93 92 bytes

c x|x<2=[[0,2]!!x]|odd x=x:c(3*x+1)|1<2=x:c(div x 2)
([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!)

Usage example: ([y|y<-[-1..],all(/=y)$c=<<[0..y-1]]!!) 10 -> 19.

c x is the Collatz cycle for x with a little bit of cheating for x == 1. The main functions loops through all integers and keeps those that are not in c x for x in [0..y-1]. Pretty much a direct implementation of the definition. As Haskell index operator !! is 0-based, I start at -1 to prepend a (otherwise useless) number to get the index fixed.

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

MATL, 46 40 bytes

Oiq:"tX>Q:yX-X<`t0)to?3*Q}2/]h5M1>]Pv]0)

Try it online!

Explanation

The code has an outer for loop that generates n Collatz sequences, one in each iteration. Each sequence is generated by an inner do...while loop that computes new values and stores them in a sequence vector until a 1 or 0 is obtained. When we are done with the sequence, the vector is reversed and concatenated to a global vector that contains the values from all previous sequences. This vector may contain repeated values. The reversing of the sequence vector ensures that at the end of the outer loop the desired result (the starting value of the last sequence) will be at the end of the global vector.

Pseudo-code:

1  Initiallization
2  Generate n sequences (for loop):
3    Compute initial value for the k-th sequence
4    Generate the k-th sequence (do...while loop)
5      Starting from latest value so far, apply the Collatz algorithm to get next value
6      Update sequence with new value 
7      Check if we are done. If so, exit loop. We have the k-th sequence
8    Update vector of seen values
9  We now have the n sequences. Get final result

Commented code:

O           % Push 0                                                          1
iq:         % Input n. Generate [1 2 ... n-1]                                 ·
"           % For loop: repeat n-1 times. Let k denote each iteration         2
  t         %   Duplicate vector of all seen values                           · 3
  X>Q       %   Take maximum, add 1                                           · ·
  :         %   Range from 1 to that: these are potential initial values      · ·
  y         %   Duplicate vector of all seen values                           · ·
  X-X<      %   Set difference, minimum: first value not seen                 · ·
  `         %   Do...while: this generates the k-th Collatz sequence          · 4
    t0)     %     Duplicate, push last value of the sequence so far           · · 5
    to      %     Duplicate, parity: 1 if odd, 0 if even                      · · ·
    ?       %     If odd                                                      · · ·
      3*Q   %       Times 3, plus 1                                           · · ·
    }       %     Else                                                        · · ·
      2/    %       Half                                                      · · ·
    ]       %     End if                                                      · · ·
    h       %     Concatenate new value of the sequence                       · · 6
    5M      %     Push the new value again                                    · · 7
    1>      %     Does it exceed 1? This is the loop condition                · · ·
  ]         %   End do...while. The loops ends when we have reached 0 or 1    · ·
  P         %   Reverse the k-th Collatz sequence                             · 8
  v         %   Concatenate with vector of previously seen values             · ·
]           % End for                                                         ·
0)          % Take last value. Implicitly display.                            9
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 70 67 65 63 62 bytes

,[]:?:1ih.
,0<=X=,?'eXg{t{:2/.*?|:3*+.}gB,(?.sB;?:Bc:2&.)}:?c.

Try it online!

\$\endgroup\$
3
\$\begingroup\$

Python 2, 97 96 bytes

r,=s={-1}
exec'n=r=min({r+1,r+2,r+3}-s)\nwhile{n}-s:s|={n};n=(n/2,3*n+1)[n%2]\n'*input()
print r

Takes advantage of the fact that all multiples of 3 are pure. Test it on Ideone.

How it works

On the first line, r,=s={-1} sets s = {-1} (set) and r = -1.

Next we read an integer from STDIN, repeat a certain string that many times, then execute it. This is equivalent to the following Python code.

for _ in range(input())
    n=r=min({r+1,r+2,r+3}-s)
    while{n}-s:
        s|={n}
        n=(n/2,3*n+1)[n%2]

In each iteration, we start by finding the smallest member of {r+1, r+2, r+3} that does not belong to s. In the first iteration, this initializes r as 0.

In all subsequent runs, s may (and will) contain some of r+1, r+2 and r+3, but never all of them, since all multiples of 3 are pure. To verify this statement, observe that no multiple m of 3 is of the form 3k + 1. That leaves 2m as the only possible pre-image, which is also a multiple of 3. Thus, m cannot appear in the Collatz sequence of any number that is less than m, and is therefore pure.

After identifying r and initializing n, we apply the Collatz function with n=(n/2,3*n+1)[n%2], adding each intermediate value of n to the set s with s|={n}. Once we encounter a number n that is already in s, {n}-s will yield an empty set, and the iteration stops.

The last value of r is the desired element of the sequence.

\$\endgroup\$
  • 1
    \$\begingroup\$ To add to this, a proof that all multiples of 3 are pure. Look at any Collatz sequence modulo 3. After any application of the 3x+1 rule, the modulo is 1. After the application of the x/2 rule, mod 1 becomes 2, and mod 2 becomes 1. Neither rule can generate a multiple of 3, unless the starting value already was a bigger multiple of 3 that got halved. But those are bigger values not generated yet, so n=0 (mod 3) => n is pure. \$\endgroup\$ – orlp Aug 13 '16 at 7:42
1
\$\begingroup\$

Pyth, 32 bytes

VtQ=+Y.u?%N2h*3N/N2Z)=Zf!}TYhZ)Z

Test suite.

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

Java, 148 bytes

int a(int n){if(n<2)return 0;int f=a(n-1),b,i,c;do{f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}while(b<1);return f;}

Ideone it! (Warning: exponential complexity due to zero optimization.)

Converting it from a do...while loop to a for loop would be golfier, but I am having trouble doing so.

Golfing advice is welcome as usual.

\$\endgroup\$
  • \$\begingroup\$ Not much, but you can golf 1 byte off by changing for(b=1,i=1;i<n;i++) to for(b=1,i=0;++i<n;). Btw, I understand why your ideone is missing the test case for 50, but why does it also miss the 10? It can handle it without a problem. \$\endgroup\$ – Kevin Cruijssen Aug 25 '16 at 11:06
  • \$\begingroup\$ @KevinCruijssen Because the formatting would be bad. \$\endgroup\$ – Leaky Nun Aug 25 '16 at 11:16
  • \$\begingroup\$ Not the best improvement but I didn't spent too much time... (147 bytes) int a(int n){if(n<2)return 0;int f=a(n-1),b=0,i,c;for(;b<1;){f++;for(b=1,i=1;i<n;i++)for(c=i==2?4:a(i);c>1;c=c%2>0?c*3+1:c/2)b=c==f?0:b;}return f;} \$\endgroup\$ – Poke Aug 25 '16 at 13:50
1
\$\begingroup\$

Perl6, 96

my @s;my $a=0;map {while ($a=@s[$a]=$a%2??3*$a+1!!$a/2)>1 {};while @s[++$a] {}},2..slurp;$a.say;

Based on the Perl 5 answer. A bit longer since Perl6 syntax is less forgiving than Perl5 syntax, but I'll settle with this for now.

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

PHP, 233 124 bytes

<?$n=$argv[1];for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}echo$v;

+4 for function:

function a($n){for($c=[];$n--;){for($v=0;in_array($v,$c);)$v++;for(;$n&&!in_array($v,$c);$v=$v&1?3*$v+1:$v/2)$c[]=$v;}return$v;}
\$\endgroup\$
0
\$\begingroup\$

Perl 5 - 74 bytes

map{0 while 1<($a=$c[$a]=$a%2?$a*3+1:$a/2);0 while$c[++$a]}2..<>;print$a+0

This is a pretty straightforward solution. It repeatedly applies the Collatz function to the variable $a and stores in the array @c that the value has been seen, then after reaching 0 or 1 it increments $a until it's a number that hasn't been seen yet. This is repeated a number of times equal to the input minus 2, and finally the value of $a is outputted.

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

Mathematica, 134 bytes

f=If[EvenQ@#,#/2,3#+1]&;a@n_:=(b={i=c=0};While[i++<n-1,c=First[Range@Max[#+1]~Complement~#&@b];b=b~Union~NestWhileList[f,c,f@#>c&]];c)

Easier-to-read format:

f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
  b = {i = c = 0};                                   initializations
                                                       b is the growing sequence
                                                       of cycles already completed
  While[i++ < n - 1,                                 computes a(n) recursively
    c = First[Range@Max[# + 1]~Complement~# & @b];   smallest number not in b
    b = b~Union~NestWhileList[f, c, f@# > c &]       apply f to c repeatedly
                                                       until the answer is smaller
                                                       than c, then add this new
                                                       cycle to b
    ]
  ; c)                                                 output final value of c
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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