纯度数

Question

今天，我们将看一个序列a，它与Collatz函数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}

我们将形式z, f(z), f(f(z)), …的一个序列称为Collatz序列。

我们序列中的第一个数字，a(1)，是0。在反复应用f的情况下，它属于循环0\to0\to0\to\:\cdots。

我们还没见过的最小的数字是1，这是a(2)=1。在反复应用f的情况下，它属于循环1\to4\to2\to1\to\cdots。

现在我们已经在上面的循环中看到了2数，所以下一个最小的数是a(3) = 3，它进入了循环3\to10\to5\to16\to8\to4\to2\to1\to4\to\cdots。

在上述所有周期中，我们已经看到了4和5，因此下一个数字是a(4) = 6。

现在你应该知道这个主意了。a(n)是所有a(1), ..., a(n-1)中不属于任何Collatz序列的最小数。

编写一个程序或函数，给定一个正整数n，返回a(n)。以字节为单位的最短代码获胜。

测试案例：

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

(这是OEIS序列A 061641。)

Answer 1

皮斯，32字节

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

测试套件。

Answer 2

Java，148个字节

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;}

把它放进去！ (警告:由于零优化导致的指数复杂度)。

将其从do...while循环转换为for循环将是golfier，但我在这样做时遇到了困难。

如往常一样欢迎打高尔夫球的建议。

Answer 3

Mathematica，134个字节

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