# Numbers of purity

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

$$f = \begin{cases} n/2 & \text{if } n \equiv 0 \text{ (mod }2) \\ 3n+1 & \text{if } n \equiv 1 \text{ (mod }2) \\ \end{cases}$$

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\to0\to0\to\:\cdots\$$

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\to4\to2\to1\to\cdots\$$

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\to10\to5\to16\to8\to4\to2\to1\to4\to\cdots\$$

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

• Obligatory OEIS – FryAmTheEggman Aug 12 '16 at 20:26
• Can input n be 0-based? – Luis Mendo Aug 12 '16 at 22:20
• a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2 – Karl Napf Aug 12 '16 at 23:08
• @LuisMendo Sorry, I somehow missed your message. No, reproduce the exact sequence as in the challenge. – orlp Aug 13 '16 at 9:14
• 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). – daniero Aug 13 '16 at 16:29

# Jelly, 20 19 bytes

ḟ@JḢ×3‘$HḂ?ÐĿ;Ṛ Ç¡Ṫ ### 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:

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

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

f = If[EvenQ@#, #/2, 3#+1] &;                        Collatz function
a@n_ := (                                            defines a(n)
b = {i = c = 0};                                   initializations
b is the growing sequence