Numbers of purity
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.
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.
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