27
2
Today we'll look at a sequence a, related to the Collatz function f:
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.)
1
Obligatory OEIS
– FryAmTheEggman – 2016-08-12T20:26:35.7103Can input
n
be 0-based? – Luis Mendo – 2016-08-12T22:20:34.520a(n+1) = a(n) odd: 3*a(n)+1, or a(n) even: a(n)/2
– Karl Napf – 2016-08-12T23:08:28.293@LuisMendo Sorry, I somehow missed your message. No, reproduce the exact sequence as in the challenge. – orlp – 2016-08-13T09:14:14.380
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 – 2016-08-13T16:29:55.457@daniero Fixed. – orlp – 2016-08-13T19:47:18.737
May our code logic assume the conjecture is true? – xnor – 2016-08-13T23:09:33.067
@xnor If you can prove it :P (In all seriousness, go ahead and post it, just mention it assumes the conjecture.) – orlp – 2016-08-13T23:13:56.957