정의
- 두 개의 정수가 이외의 양의 공통 제수를 공유하지 않으면 두 개의 정수가 coprime
1
입니다. a(1) = 1
a(2) = 2
a(n)
integer의 경우a(n-1)
, coprime에 해당 하며a(n-2)
아직 나타나지 않은 가장 작은 양의 정수입니다n >= 3
.
직무
- 양의 정수가 주어지면
n
output / printa(n)
입니다.
예
a(11) = 6
왜냐하면6
마지막 두 전임자 (즉,11
및13
) 와의 동시성 이므로 이전6
에는 나타나지 않았습니다.
노트
- 시퀀스가 오름차순이 아니므로 요소가 이전 요소보다 작을 수 있습니다.
명세서
- 당신은 해야한다 1 인덱스를 사용합니다.
테스트 케이스
n a(n)
1 1
2 2
3 3
4 5
5 4
6 7
7 9
8 8
9 11
10 13
11 6
12 17
13 19
14 10
15 21
16 23
17 16
18 15
19 29
20 14
100 139
1000 1355
10000 13387
100000 133361
채점
- coprime은 두 숫자가 하나의 제수 (
1
) 만 공유1
하고 작은 숫자를 의미하므로 바이트 수 측면에서 코드는 가능한 작아야합니다.
참고 문헌
- OEIS A084937
답변
파이썬 3.5 160 141 126 124 121 109 바이트
이것은 시퀀스 정의의 간단한 구현입니다. 골프 제안을 환영합니다.
편집 : Leaky Nun 덕분에 -17 바이트. Peter Taylor 덕분에 -9 바이트 Sp3000 덕분에 -6 바이트, Python 3.5로 전환
import math;f=lambda n,r=[2,1],c=3:n<2and r[1]or(c in r)+math.gcd(c,r[0]*r[1])<2and f(n-1,[c]+r)or f(n,r,c+1)
풀기 :
import math
def f(n, r=[2,1], c=3):
if n<2:
return r[1]
elif (c in r) + math.gcd(c,r[0]*r[1]) < 2:
return f(n-1, [c]+r)
else:
return f(n, r, c+1)
답변
MATL , 28 27 바이트
2:i:"`@ym1MTF_)Zdqa+}@h]]G)
코드는 느리지 만 올바른 결과를 제공합니다.
온라인으로 사용해보십시오! 또는 처음 10 건을 확인하십시오 .
코드를 약간만 수정하면 시퀀스 플롯이 생성됩니다.
2:i:"`@ym1MTF_)Zdqa+}@h]]G:)XG
ASCII art 또는 오프라인 컴파일러에서 그래픽 출력 으로 참조하십시오 .
설명
2: % Push [1 2] to initiallize the sequence
i: % Input n. Push [1 2 ... n]
" % For loop: repeat n times
` % Do while loop
@ % Push iteration index, starting at 1. This is the candidate number
% to extend the sequence
y % Duplicate vector containing the sequence so far
m % Is member? Gives true if the candidate is in the sequence
1M % Push candidate and vector again
TF_) % Get last two elements of the vector
Zd % GCD between the candidate and those two elements. Produces a
% two-element vector
qa % True if any of the two results exceeds 1, meaning
% the candidate is not coprime with the latest two sequence values
+ % Add. This corresponds to logical "or" of the two conditions, namely
% whether the candidate is member of the sequence so far, and
% whether it is not coprime with the latest two. In either case
% the do...while must continue with a next iteration, to try a new
% candidate. Else the loop is exited, and the current candidate
% is the new value of the sequence
} % Finally (execute when the loop is exited)
@h % Push current candidate and concatenate to the sequence vector
] % End do...while
] % End for
G) % Get n-th value of the sequence. Implicitly display
답변
C, 185 바이트
G(a,b){return a%b?G(b,a%b):b;}
i,j,k;f(n){int a[n+2];for(i=0;i++<n;){a[i]=i<3?i:0;for(j=2;!a[i];++j){for(k=i;--k;){if(a[k]==j)++j,k=i;}a[G(a[i-1],j)*G(a[i-2],j)<2?i:0]=j;}}return a[n];}
답변
실제로 , 38 37 35 33 31 30 바이트
이것은 함수 정의의 간단한 구현입니다. 골프 제안을 환영합니다. 온라인으로 사용해보십시오!
편집 : Leaky Nun 덕분에 -3 바이트.
2R#╗,;`1";2±╜tπg@╜í+Y"£╓╖`nD╜E
풀기 :
2R#╗ Push [1,2] and store it in register 0
,; Take input and duplicate
`1 Start function, push 1
" Start string
; Duplicate i
2±╜t Push (list in register 0)[-2:]
πg gcd(i, product of list[-2:])
@╜í Rotate the gcd and bring up i, check for i in list (0-based, -1 if not found)
+Y Add the gcd and the index, negate (1 if coprime and not found in list, else 0)
"£ End string, turn into a function
╓ Push first (1) values where f(x) is truthy, starting with f(0)
╖` Append result to the list in register 0, end function
n Run function (input) times
D╜E Return (final list)[n-1]
답변
하스켈, 81 73 바이트
c l@(m:n:_)=m:c([x|x<-[1..],gcd(m*n)x<2,all(/=x)l]!!0:l)
((0:1:c[2,1])!!)
사용 예 : ((0:1:c[2,1])!!) 12
-> 17
.
모두의 목록을 작성 a(n)
을 시작으로 0
1부터 시작하는 인덱스를 수정하고 1
및 다음 c[2,1]
. c
인수 목록의 머리 부분에 l
이어 재귀 호출을 한 다음 앞에 추가 된 (공동 프라임, 이전에 보지 않은) 숫자를 사용합니다 l
. n
이 목록 의 th 요소를 선택하십시오 .
답변
R, 141 바이트
f=Vectorize(function(n)ifelse(n>3,{c=3;a=f(n-1);b=f(n-2);d=f(4:n-3);while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)c=c+1;c},n))
언 골프
f=Vectorize( function(n) #build a recursive function. Vectorize allows
if(n>3) { #the function to be called on vectors.
c=3 #Tests size. Builds some frequent variables.
a=f(n-1)
b=f(n-2)
d=f(4:n-3) #Should really golf this out, but its horribly slow.
while(!c%%which(!a%%1:a)[-1]||!c%%which(!b%%1:b)[-1]||c%in%d)
c=c+1 #If we are coprime and not already seen. add.
c
} else n) #First three are 1,2,3.
답변
Mathematica, 97 90 바이트
a@1=1;a@2=2;a@n_:=SelectFirst[Range[2n],GCD[a[n-1]a[n-2],#]<2&&!MemberQ[a/@Range[n-1],#]&]
를 기반으로 내 추측이 a(n) < 2n
모든 n
.
, 빠른 실행 얻을 추가하려면 a@n=
원래 후 :=
너무 기능이 이전 값을 다시 계산 할 필요가 없습니다 .
저장 7 Sherlock9 덕분에 바이트 (만약 gcd(a,b)=1
다음 gcd(ab,m) = gcd(a,m)*gcd(b,m)
)