EKG序列项

Question

Introduction

EKG序列从1和2开始，然后规则是，下一项是序列中尚未出现的最小正整数，其与最后一项的公共因子大于1(它们不是互质)。

第一个术语是：

1，2，4，6，3，9，12，8，10，5，15，

它被称为EKG，因为它的术语图与EKG非常相似。

我是OEIS中的序列A 064413。

挑战

您必须编写一个函数，该函数以整数n作为输入，并输出序列的n个首项中有多少大于n。

由于序列的规则从第三个项开始，输入整数必须大于或等于3。例如，给定输入10，输出为1，因为第七个项是12，而前十个项中没有一个超过10。

测试用例

3 -> 1 10 -> 1 100 -> 9 1000 -> 70

规则

• 对于小于3的整数，函数可能输出0或错误代码。
• 没有其他特别的规则，除了:这是代码高尔夫，越短越好！

Answer 1

外壳，16字节

#>¹↑¡§ḟȯ←⌋→`-Nḣ2

在网上试试！

解释

#>¹↑¡§ḟȯ←⌋→`-Nḣ2  Implicit input, say n=10
              ḣ2  Range to 2: [1,2]
    ¡             Construct an infinite list, adding new elements using this function:
                   Argument is list of numbers found so far, say L=[1,2,4]
             N     Natural numbers: [1,2,3,4,5,6,7...
           `-      Remove elements of L: K=[3,5,6,7...
      ḟ            Find first element of K that satisfies this:
                    Argument is a number in K, say 6
     §    →         Last element of L: 4
         ⌋          GCD: 2
       ȯ←           Decrement: 1
                    Implicitly: is it nonzero? Yes, so 6 is good.
                  Result is the EKG sequence: [1,2,4,6,3,9,12...
   ↑              Take the first n elements: [1,2,4,6,3,9,12,8,10,5]
#                 Count the number of those
 >¹               that are larger than n: 1

Answer 2

马蒂尔，29字节

qq:2:w"GE:yX-y0)yZdqg)1)h]G>z

在网上试试！

解释：

	#implicit input, n, say 10
qq:	#push 1:8
2:	#push [1 2]. Stack: {[1 .. 8], [1 2]}
w	#swap top two elements on stack
"	#begin for loop (do the following n-2 times):
 GE:	#push 1...20. Stack: {[1 2], [1..20]}
 y	#copy from below. Stack:{[1 2], [1..20], [1 2]}
 X-	#set difference. Stack: {[1 2], [3..20]}
 y0)	#copy last element from below. Stack:{[1 2], [3..20], 2}
 yZd	#copy from below and elementwise GCD. Stack:{[1 2], [3..20],[1,2,etc.]}
 qg)	#select those with gcd greater than 1. Stack:{[1 2], [4,6,etc.]}
 1)	#take first. Stack:{[1 2], 4}
 h	#horizontally concatenate. Stack:{[1 2 4]}
 ]	#end of for loop
G>z	#count those greater than input
	#implicit output of result

Answer 3

APL，字符121个，字节242个

∇r←a w;i;j;v
r←w⋄→0×⍳w≤2⋄i←2⋄r←⍳2⋄v←1,1,(2×w)⍴0
j←¯1+v⍳0
j+←1⋄→3×⍳1=j⊃v⋄→3×⍳∼1<j∨i⊃r⋄r←r,j⋄i+←1⋄v[j]←1⋄→2×⍳w>i
r←+/w<r
∇

在运行时，在这里测试不到一分钟：

  a¨3 10 100 1000 2000
1 1 9 70 128 

自然没有检查类型和范围..。