RSS Feed

기막힌 소수 생성 자동화 장치

Problem 308

출제 일시 : 2021-01-07 00:02:01

프로그래밍 언어 프랙트란(Fractran)으로 작성된 프로그램은 분수의 목록입니다.

프랙트란 가상 머신의 내부 상태는 양의 정수입니다. 처음에 어떤 초기 정수 값이 하나 설정됩니다. 프랙트란 프로그램의 각 단계마다 상태 정수 값에 곱하여 결과가 정수가 되는 분수 목록의 첫 번째 분수를 곱합니다.

예를 들어, 존 호턴 콘웨이(John Horton Conway)가 소수를 생성하도록 작성한 프랙트란 프로그램은 다음 14개의 분수 목록입니다:

17
91
,
78
85
,
19
51
,
23
38
,
29
33
,
77
29
,
95
23
,
77
19
,
1
17
,
11
13
,
13
11
,
15
2
,
1
7
,
55
1
.

초기 정수 값 2에서 시작해서, 연속적인 프로그램의 단계마다 다음 수열을 생성합니다:
15, 825, 725, 1925, 2275, 425, ..., 68, 4, 30, ..., 136, 8, 60, ..., 544, 32, 240, ...

이 수열에 나타나는 2의 제곱수는 22, 23, 25, ... 입니다.
이 수열에 나타나는 모든 2의 제곱수는 소수 지수를 갖고, 모든 소수는 순서대로 2의 제곱수의 지수에 나타납니다!

만일 누군가가 위의 프랙트란 프로그램을 이용하여 프로젝트 오일러 7번 (10001번째 소수를 찾는) 문제를 푼다면, 210001번째 소수를 생성할 때까지 몇 번의 단계가 필요합니까?


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.