分形烟雾序列

Question

Introduction

A229037有一个非常有趣的情节(至少在最初的几个术语中是这样)：

有一个猜想，即它可能确实具有某种分形性质。

这个序列是如何构造的？

定义a(1) = 1, a(2) = 1，然后为每个n>2找到一个最小正整数a(n)，这样对于每一个指数的算术3项序列n,n+k,n+2k，序列a(n),a(n+k),a(n+2k)的对应值都不是算术序列。

挑战

给定一个正整数n作为输入，输出该序列的第一个n项a(1), ... , a(n)。(具有任何合理的格式。可能的前导/训练字符/字符串是不相关的。)

有一些片段可用于生成此序列，但我认为其他方法可能更适合某些语言。

请告诉我们你的程序是如何工作的。如果你来了一个交叉算法--一个特别有效的算法--你可能也要提到这一点，因为它允许在更短的时间内绘制更多的序列术语。

前几个测试用例：

1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 1, 1, 2, 1, 1, 2, 2, 4, 4, 1, 1, 2, 1, 1, 2, 2, 4, 4, 2, 4, 4, 5, 5, 8, 5, 5, 9, 9, 4, 4, 5, 5, 10, 5, 5, 10, 2, 10, 13, 11, 10, 8, 11, 13, 10, 12, 10, 10, 12, 10, 11, 14, 20, 13

更多测试案例：

  a(100)  =   4
  a(500)  =   5
 a(1000)  =  55
 a(5000)  =  15
a(10000)  = 585

到n=100000的所有条款都可以在这里获得：https://oeis.org/A229037/b229037.txt

谢谢你的帮助和鼓励。

Answer 1

Python2，95字节

l=[];n=input()
exec"a=min(set(range(n))-{2*b-c for b,c in zip(l,l[1::2])});print-~a;l=[a]+l;"*n

主要的诀窍是生成新值必须避免的数字。到目前为止，在l中保持相反的顺序，让我们来看看哪些元素可以与我们将要添加的值形成一个三项算术级数。

? 4 2 2 1 1 2 1 1   a b c
^ ^ ^               ? 4 2
^   ^   ^           ? 2 1
^     ^     ^       ? 2 2
^       ^       ^   ? 1 1

其他数字是l的配对成员和l的每二个元素，因此是zip(l,l[1::2])。如果这对是(b,c)，那么a=2*b-c就会出现算术级数(a,b,c)。在生成a's的集合以避免后，代码取补语的最小值，打印它，并将其添加到列表中。(实际上，计算的数字减少了1，打印得更高，这样range(n)就可以作为候选的宇宙。)

Answer 2

Mathematica，95字节

For[n_~s~k_=0;n=0,n<#,For[i=n,--i>0,s[2n-i,2f@n-f@i]=1];For[++n;i=1,n~s~i>0,++i];Print[f@n=i]]&

当然不是最高明的方法，但与我从OEIS页面尝试的算法相比，这实际上是相当有效的。

与检查每个s(n)的所有禁止值相反，当我们到达那里时，我使用的是基于筛网的方法。当我们找到一个新的值s( n )时，我们会立即检查m>n中禁止这个值的值，然后通过寻找不被禁止的第一个值来求解s(n+1)。

通过将条件--i>0更改为2n-#<=--i>0，可以提高效率。在这种情况下，我们避免检查大于输入的n的禁止值。

为了获得一个更具可读性的版本，我从下面的代码开始，它将结果存储到max中的函数f中，然后将其添加到上面的一行纯函数：

 max = 1000;
 ClearAll[sieve, f];
 sieve[n_, k_] = False;
 For[n = 0, n < max,
  temp = f[n];
  For[i = n - 1, i > 0 && 2 n - i <= max, --i,
   sieve[2 n - i, 2 temp - f[i]] = True;
   ];
  ++n;
  i = 1;
  While[sieve[n, i], ++i];
  f@n = i;
  ]

Answer 3

ES6,114个字节

n=>[...r=Array(n)].map((x,i,s)=>{for(y=1;x&&x[y];y++);r[i]=y;for(j=i;++j<n;s[j][y+y-r[i+i-j]]=1)s[j]=s[j]||[]}&&r

返回序列的前n个元素的数组，因此索引在下面的非黄金版本中为1。我用了筛子法。这个版本在关于n=2000之后会慢下来；以前的版本避免读取数组的开头，这意味着它直到关于n=2500才会慢下来。一个较早的版本使用筛子数组作为禁止值的列表，而不是禁止其值的布尔数组；这可以在不费力的情况下达到n=5000的目的。我的原始版本试图使用位掩码，但结果却没有用(而且也太长了，只有198个字节)。

不太慢的版本没有打高尔夫球：

function smoke(n) {
    result = [];
    sieve = [];
    for (i = 1; i <= n; i++) {
        value = 1;
        if (sieve[i]) {
            while (sieve[i][value]) {
                value++;
            }
        }
        result[i] = value;
        for (j = 1; j < i && i + j <= n; j++) {
            if (!sieve[i + j]) sieve[i + j] = [];
            sieve[i + j][value + value - result[i - j]] = true;
        }
    }
    return result;
}