책 이야기

서로 다른 소수인 p와 q로 만들어지는 정수 p^qq^p는 합성 정수(Hybrid Integer)라 부른다.

예를 들어, 800=2⁵5²은 합성 정수이다.

C(n)을 n이하의 합성 정수의 갯수라 정의하자.

C(800)=2이고 C(800⁸⁰⁰)=10790이다.

C(800800⁸⁰⁰⁸⁰⁰)을 구하시오.

--------------------------------------------------------------------------

처음에는 숫자가 너무 커서 다루기 겁이 나서 지나갔던 문제이다. 다른 사람의 접근을 보니 숫자가 너무 크기 때문에 log를 이용하면 해결 가능할 것으로 보였다. 문제에서 요구하는 것은 p^qq^p가 800800⁸⁰⁰⁸⁰⁰ 이하인 경우를 묻고 있으므로 다음과 같이 된다. 그리고 양변에 로그를 씌워 다시 정의하면 아래와 같다.

p^qq^p <= 800800⁸⁰⁰⁸⁰⁰

log(p^qq^p) <= log(800800⁸⁰⁰⁸⁰⁰)

log(p^q)+log(q^p) <= log(800800⁸⁰⁰⁸⁰⁰)

q*log(p)+p*log(q) <= 800800*log(800800)

소수는 2부터 시작하므로 800800*log(800800)을 최대값으로 보고 이보다 크게 되는 q*log2+2*log(q)의 q값을 구해 상한선으로 두고 이중 반복문을 운영하면 답을 구할 수 있다. 파이썬의 배열 한계를 넘어갈 것을 걱정했는데, 다행히 천만~2천만 사이의 어딘가에서 최대값을 넘는 것을 확인하고, 정확한 값을 구할 수 있었지만 안전하게 해서 답을 구하기로 했다.

15분쯤 소요되었으니 빠른 것은 아니지만 문제를 해결했다는 것에 만족하기로 했다.

30의 약수는 1, 2, 3, 5, 6, 10, 15, 30이다.

30의 모든 약수인 d와 d+30/d는 소수이다.

100000000이하의 정수 n의 약수 d가 있을 때, 모든 d+n/d가 소수인 n의 합계를 구하시오.

--------------------------------------------------------------------------

처음에는 정직하게 접근해서 1에서 1억 사이의 숫자를 대상으로 약수(d)를 구하고 d+n/d가 소수인 숫자를 찾게 했다. 시간이 많이 걸려서 생각해 보니 d+n/d가 소수이려면, d=n일 경우 n+1이 소수이고 2를 제외하고 모든 소수는 홀수이므로 n은 짝수여야 한다. 그리고 짝수의 경우 d=2일 때 n/2가 홀수여야 하므로 4의 배수가 되면 안된다. 그러므로, 2, 6, 10으로 커지는 4i+2의 경우만 검증하면 된다. 이렇게 해서 실행시간을 많이 줄였지만 1억까지 계산하려면 여전히 많은 시간을 필요로 했다.

그래서, 접근을 바꿔서 1000이하의 숫자(d)의 반복문과, d부터 시작해서 n/d를 구하는 이중 반복문을 만들고, 두 수의 합계가 소수가 아닌 경우에는 원 숫자에 표시하도록 처리해서, 남는 수의 합을 구하도록 해결책을 다르게 접근해서 9분 이내에 답을 구할 수 있었다. 

참고로, 챗gpt의 성능 테스트겸 357번 문제를 물어봤는데 문제에서 요구하는 그대로 가장 정직하게 프로그램을 제시했다. 성능 문제만 고려하지 않으면 즉시 적용 가능하도록 구현해 내는 것이 어찌보면 대단하다 싶었다.

169와 961은 모두 소수의 제곱이다. 169를 반대로 하면 961이 된다.

다음 조건을 만족하면 reversible prime square(가역 소수 제곱)이라 부른다:

1. 회문(palindrome)이 아니며,
2. 소수의 제곱이며,
3. 반대로 한 것도 소수의 제곱이다.

169와 961은 회문이 아니며, 소수의 제곱을 반대로 한 것이다.

처음 50개 reversible prime square의 합계를 구하시오.

--------------------------------------------------------------------------

프로그램은 어렵지 않게 구성 가능한데, reversible prime square를 만족하는 숫자를 50개 찾는 것이 쉽지 않았다.

50개가 나올때까지 매번 소수를 추가로 만드는 경우 시간이 많이 소요될 것으로 보여서, 일정한 갯수의 소수와 소수의 제곱수 리스트를 먼저 만들어 놓고, 회문이 아니고, 순서를 반대로 한 것도 소수의 제곱수 리스트에 있는 것들을 따로 모으도록 구현했다.

100자리 중 2개, 1000자리 중 2개 등 생각보다 위 조건을 만족하는 숫자가 많이 나오지 않아서, 처음 소수를 만드는 갯수를 계속 키워가며 구해야 했다. 천만의 제곱까지 구해도 50개가 되지 않는다.

문제에서 요구한 조건을 만족하는 reversible prime square가 모두 홀수 자릿수의 숫자인 것은 의아했다. 확실한 이유가 생각되면 짝수 자릿수의 prime square는 검증과정을 생략하도록 해서 성능을 높을 수도 있을 것 같은데, 짝수 자릿수의 숫자가 없는 이유가 명확하게 떠오르지는 않아서 일단 모든 숫자를 대상으로 검증하게 했다.

일단 답은 구했지만 시간이 많이 걸렸다. 검색 끝에 찾은 몇가지 추가 조건은, △끝자리에 올 수 있는 수가 홀수이며 이 중 5의 배수인 5 제외, 1, 3, 7, 9의 제곱수는 1, 9이므로, 첫자리와 끝자리는 1, 9만 올 수 있으며, △첫자리에 1,9만 올 수 있으므로 제곱근은 1,3이 되고 이 경우 3자리 제곱은 5자리, 4자리 제곱은 7자리와 같이 홀수 자릿수로만 나오게 된다. 앞에서 얘기한 홀수 자릿수로만 reversible prime square가 나오는 이유를 알게 되었다.

그리고, 처음에는 소수의 제곱수 목록을 구해서(조건2) 그것을 대상으로 회문과 반대수를 구했는데(조건1,3), 제곱수를 구할 때 추가로 발견한 2가지 조건과 회문까지 판별해서 목록을 만들고(조건1,2), 반대수가 제곱수인 소수이면 정답 목록에 추가하는 방식으로 바꿔서 검증대상을 줄여봤다.

추가로 발견한 2가지 조건으로 검증대상이 500만개 이상에서 40만개 이하로 줄어 실행시간도 많이 개선되었지만, 검증대상 거의 마지막에 가서야 50개를 찾을 수 있어 실행시간은 여전히 필요했다.

적어도 2개의 소수를 약수로 가지고 있는 수를 합성수라 한다. 예를 들어, 15=3x5, 9=3x3, 12=2x2x3이다.

(서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 30이하에 10개가 있다:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26

10⁸보다 작은 n에 대해, (서로 다를 필요가 없는) 2개의 소수로 구성된 합성수는 몇 개인가?

--------------------------------------------------------------------------

1억 이하의 숫자 중에 2개 이상의 소수의 곱으로 구성된 합성수가 몇 개인지 묻는 문제이다. 문제에서 (서로 다를 필요가 없는)으로 설명된 부분은 동일한 소수로 곱해도 된다는 뜻이므로, 예시와 같이 9=3x3을 허용하게 구현하면 된다.

빠른 계산을 위해서 1억 이하의 소수 목록을 구하고, 2중 반복문에서 소수끼리 서로 곱하게 해서 목록을 구하고, 파이썬의 집합을 이용해서 중복을 제거해서 구했다. 1억 이하의 소수가 5백만 개 이상 나오더니 목록을 구하면서 메모리 에러가 발생했다. 생각보다 리스트가 커져서 문제가 생긴 것 같았다.

그래서, 결과값 리스트를 만들지 않고, 생성되는 합성수의 갯수를 구하도록 바꿔서 답을 구할 수 있었다. 소수 2개의 곱을 구하는 것이어서 다른 약수가 있을 수 없기 때문에 중복을 제거하는 과정이 필요없었다.

1로만 구성된 숫자를 repunit이라 부른다. R(k)를 길이가 k인 repunit이라 정의하자. 예를 들어, R(6)=111111이다.

gcd(n,10)=1인 양의 정수 n에 대해 언제나 R(k)를 n으로 나눌 수 있는 k가 존재한다. 그러한 k 중 최소값을 A(k)라 하자. 예를 들어, A(7)=6이고, A(41)=5이다.

5보다 큰 모든 소수에 대해, p-1은 A(p)로 나눠진다. 예를 들어, p=41일 때, A(41)=5이며 40은 5로 나눠진다.

그러나, 합성수 중 이러한 특성을 가지는 것이 드물지만 있다. 처음 5개 숫자는 91, 259, 451, 481, 703이다.

gcd(n,10)=1이고 n-1을 A(n)으로 나눌 수 있는 처음 25개 숫자의 합계를 구하시오.

--------------------------------------------------------------------------

129번 문제를 해결했으면, 코드를 조금만 수정하면 해결 가능한 문제이다.

기존에는 검증 대상이 되는 숫자에서  2의 배수, 5의 배수를 제외했지만, 소수 목록을 만들어서 소수를 검증 대상에서 제외하는 과정을 추가하고, n-1을 A(n)으로 나눠지는 숫자를 찾으면 된다.

문제에서 요구한대로 코딩했는데도 처음에 오답이 나와 원인을 분석하는 데 시간이 조금 걸렸다. 원인을 찾아보니, 검증대상에서 제외할 소수목록을 1만 이하의 숫자를 대상으로 만들었는데 실제로는 1만 이상의 숫자까지 대상이 되면서, 제외되어야 하는 소수가 목록에 포함되었던 것이 문제였다.

n의 근인 rad(n)은 서로 다른 소수 n의 곱이다. 예를 들어, 504=2³*3²*7이고, rad(504)=2*3*7=42이다.

n이 1이상, 10이하일 때 rad(n)을 계산하고, rad(n)을 기준으로 정렬하고, 근 값이 같을 때 n 값에 따라 정렬하면 위의 표와 같다:

E(k)를 정렬된 n의 k번째 요소라고 하자. 예를 들어, E(4)=8이고, E(6)=9이다.

rad(n)이 1이상, 10만 이하의 값으로 정렬되었을 때, E(10000)을 구하시오.

--------------------------------------------------------------------------

미리 만들어 둔 약수 함수를 이용해서 결과 중 소수만 찾으면 rad(n) 값을 구할 수 있다.

10만개 결과 리스트에 대해 rad(n)값을 1순위, n값을 2순위로 해서 정렬하면 답을 구할 수 있다. 파이썬 리스트의 인덱스가 0부터 시작하는 것 때문에 1만번째 값을 다른 것을 구하는 덕분에 다시 한 번 더 실행해야 되어서 시간이 좀 걸렸다.

약수 함수를 아무리 개선해도 성능에 한계가 있어서 문제에서 10만개를 요구했으니 다행이지 다른 문제처럼 몇조 단위의 처리를 요구했으면 시간내에 해결하지 못했을 것 같다.

p_n을 n번째 소수(2, 3, 5, 7, 11, ..), r을 (p_n-1)ⁿ+(p_n+1)ⁿ을 p_n²으로 나눴을 때 나머지로 하자.

예를 들어, n이 3일 때, p₃=5이고, 4³+6³=280은 5 mod 25와 합동이다.

나머지가 처음으로 10⁹을 초과할 때 가장 작은 n의 값은 7037이다.

나머지가 처음으로 10¹⁰을 초과할 때 가장 작은 값을 구하시오.

--------------------------------------------------------------------------

이전 오일러 프로젝트 문제를 통해 소수와 나머지를 다루는 데 익숙해져 있으면 난이도 30%이지만 크게 어렵지 않게 해결 가능한 문제이다.

우선 충분한 크기의 소수 목록을 만들어 두고(천만 이하의 소수 목록을 만들어서 해결했는데, 결과론으로 보면 더 작은 목록을 만들어도 해결 가능했다), 각 소수에 대해 문제에서 제시한 공식을 대입해서 나머지 값을 구하면서 10¹⁰보다 큰 경우를 찾으면 된다.

앞에서 나온 나머지 문제를 해결할 때 중간값이 너무 커져서 에러가 발생한 경우를 봤기 때문에 부분계산을 할 때마다 나머지 연산을 적용해서 큰 수가 만들어지지 않게 하면서 답을 구했는데 생각보다 빠른 시간 내에 답을 구할 수 있었다.

다음 수식에서 x, y, n은 양의 정수이다.

1/x+1/y=1/n

n이 4일 때, 다음의 3개 답안만 있다:

1/5+1/20=1/4

1/6+1/12=1/4

1/8+1/8=1/4

서로 다른 해결책이 1,000개를 넘는 가장 작은 값 n은 얼마인가?

주의: 이 문제는 문제 110의 쉬운 버전이므로, 이 문제를 먼저 해결하기를 강력하게 권고함

--------------------------------------------------------------------------

다른 분이 이야기한 아이디어(양변에 nxy를 곱해서 분모 없애기)를 참고해서 해결할 수 있었다.

문제에 나오는 공식의 분모를 없애기 위해 간단히 수학을 적용해서 양변에 xyn을 곱하면 ny+nx=xy가 된다. 그리고, 예시를 보면 짐작 가능하겠지만 n이 x, y보다는 작기 때문에 x를 n+a, y를 n+b로 바꾸면 n(n+b)+n(n+a)=(n+a)(n+b)가 된다. 이를 풀면 n²+nb+n²+na=n²+na+nb+ab가 되고 양변을 정리하면 n²=ab가 된다.

이 특성을 이해하고, 예시를 다시 보면 x의 값이 n=4일 때, n보다 1, 2, 4만큼 큰 것을 알 수 있다. 이것이 4의 약수이기 때문에, 솔루션이 1000개를 넘는 것은 약수가 1000개를 넘는 경우와 같은 것으로 이해되었다. 그래서, 먼저 풀었던 243번 문제에서 적용한 소수의 곱을 대상으로 배수로 키워나가면서 약수가 1000개 이상인 경우를 찾는 방법을 적용했는데, 예상과는 달리 오답이었다.

n²=ab를 다시 생각해보니, n의 약수가 아니라 n²의 약수 중 n이하의 값인 것들을 찾으면 되는 것이었다. 예시로 나온 4가 너무 작은 수이면서 2의 배수여서 다양한 경우가 나오지 않아 잘못된 유추를 하게 되었던 것이다.

약수를 구하는 함수를 n제곱을 입력값으로 해서 n이하의 값만 구하도록 바꾸고 나니 빠른 시간 내에 답을 구할 수 있었다.

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form 2^6972593−1; it contains exactly 2,098,960 digits. Subsequently other Mersenne primes, of the form 2^p−1, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains 2,357,207 digits: 28433×2^7830457+1.

Find the last ten digits of this prime number.

1백만 자릿수가 넘는 소수 중 처음으로 알려진 소수가 1999년에 발견되었다. 이것은 2^6972593−1 형태인 메르센 소수(Mersenne prime)이다. 이 숫자는 2,098,960 자리로 구성된다. 마르센 소수 이후, 자릿수가 더 많은 2^p−1 형태의 메르센 소수가 발견되고 있다.

그러나, 2004년에 2,357,207 자릿수인 큰 규모의 비 메르센 소수 28433×2^7830457+1이 발견되었다.

이 소수의 마지막 열 자릿수를 구하시오.

--------------------------------------------------------------------------

메르센 소수(Mersenne prime)라는 새로운 형태의 소수를 소개하고 그것을 응용하는 문제이다. 프로그래밍을 효율적으로 또는 어렵게 하는 데 수학이 필요하다는 것은 인정하지만, 갈수록 프로그래밍 보다는 수학을 공부하고 있는 것 같다.

파이썬의 정수 최대값 허용폭이 넓은 것을 믿고 정직하게 한 줄로 작성했더니 최대값을 넘어 동작하지 않는다는 에러가 나왔다.

문제에서 마지막 10자리 숫자를 물어봤고, 이것은 모든 숫자를 계산할 필요없이 마지막 10자리 숫자만 계산하면 되는 것이었다. 그래서 % 연산자를 이용해 계속 10자리만 남게 하면서 2를 계속 곱해 2^7830457을 구하고, 거기에 28433곱하고 1을 더해서 나온 숫자의 마지막 10자리만 뽑아내면 되므로 문제를 해결하는 것은 그리 까다롭지 않았다.

The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime. For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes with this property.

Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.

소수 3, 7, 109, 673은 주목할 만하다. 두 소수를 선택해서 연결하면 소수가 된다. 예를 들면, 7, 109를 연결한 7109와 1097은 모두 소수이다. 네 소수의 합인 792는 이런 속성을 가진 네 소수의 합 중 가장 작은 값이다.

임의의 두 소수를 연결해도 소수가 되는 다섯 소수의 합계 중 가장 작은 값을 구하시오.

--------------------------------------------------------------------------

값을 찾을 소수의 최대값을 정해야 하는데, 예시를 보고 일단 1만 이하의 소수를 대상으로 찾아보기로 했다.

단순대입법보다 좋은 방법이 생각나지 않아서, 크기가 커지는 5개의 소수를 대상으로 반복문을 구성해서 이 중 2개씩 연결한 것 모두 소수인 것을 찾도록 구성했다. 5개 숫자를 a, b, c, d, e라고 할 때 2번째 반복문에서 ab, ba가 소수이고, 3번째 반복문에서 ac, ca, bc, cb가 소수이고, 4번째 반복문에서 ad, da, bd, db, cd, dc가 소수이며, 5번째 반복문에서 ae, ea, be, eb, ce, ec, de, ed의 20가지 모두 소수가 되는 경우를 찾게 했다.

소수 리스트가 1200개가 넘게 있으니 5중 반복문이면 최악의 경우 1200⁵를 계산해야 되는 구조여서 예상했던 것 보다 시간이 많이 필요했다. 제일 처음 나오는 값이 합계가 가장 작은 경우라는 보장이 없기 때문에 모든 경우를 계산해서 답을 찾아야 하지만, 가장 먼저 나온 경우를 입력했을 때 정답으로 처리되어 다행히 조금 더 빨리 답을 구할 수 있었다.

상황을 분석해보니 연결한 숫자의 소수여부를 판별하는 데 시간이 많이 걸리는 것을 발견하고, 초기에 소수 목록을 연결된 숫자까지 만들고 난 이후에 그 값으로 판별하게 하니 실행 시간이 몇시간에서 몇분으로 개선되었다. 그리고, 계속 오답을 찾아 이상했는데 리스트의 값과 인덱스를 잘 구분하지 못하고 사용한 문제 때문에 발생한 것이었다.

1만 이하 소수에서 답이 되는 경우가 하나 이상 있을 수 있어 5중 반복문을 전부 돌려 답을 찾게 했는데, 실제로는 답이 되는 경우가 하나 밖에 없었다.

It is possible to write ten as the sum of primes in exactly five different ways:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

What is the first value which can be written as the sum of primes in over five thousand different ways?

10을 소수의 합으로 나타내는 데에는 다음과 같이 5가지 방법이 있다:

7 + 3
5 + 5
5 + 3 + 2
3 + 3 + 2 + 2
2 + 2 + 2 + 2 + 2

소수의 합으로 5천가지 이상의 방법으로 표현 가능한 첫 숫자는 무엇인가?

--------------------------------------------------------------------------

31번 문제, 76번 문제를 조금 변형시켜 만들어진 문제이지만, 슬프게도 31번 문제, 76번 문제를 해결하는데 사용한 방법을 적용할 수 없었다. 31번 문제는 동전 숫자를 알아서 반복문을 중첩시켜 해결했고, 76번 문제는 정수론에 있는 분할수 공식을 이용해서 구했는데 이 두가지와는 성격이 달라 그대로 적용할 수 없었다.

영문 위키 Partition(Number Theory) 항목의 Restrcted partition을 잘 이해하면 적용 가능할 것 같은데 이제는 중학교 수준 이하의 실력을 가진 상황에 그 부분을 이해하고 프로그래밍 하는 것이 쉽지 않았다.

그래서, 31번, 76번 문제 모두에 적용가능했던 동적 프로그래밍 방법을 가져와 소수에 맞게 조금 응용해서 해결했다. 정답을 맞췄지만 내 것으로 소화한 것이 아니어서 찝찝함이 남는다.

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that there are 21 elements in this set.

How many elements would be contained in the set of reduced proper fractions for d ≤ 1,000,000?

n, d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고 HCF(n,d)=1인 것을 약분된 진분수라 부른다.

d가 8 이하인 약분된 진분수를 크기 순서로 정렬하면 다음과 같다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

이 집합에는 21개 원소가 있는 것을 알 수 있다.

d가 1,000,000 이하일 때, 약분된 진분수에는 몇 개의 원소가 있는가?

--------------------------------------------------------------------------

71번 문제에서 몇글자 다른데 전혀 다른 문제가 되어 있다. 71번과 마찬가지로 분자가 분모보다 작고, 분자와 분모의 최대공약수가 1이 되는 분수 집합을 전제로 하고, 이번 문제에서는 그런 약분된 진분수가 분모가 1,000,000 이하인 경우 몇 개 있는지 물어보고 있다.

71번 문제에서는 전체 분수 값이 정렬된 상태를 요구했지만, 이번 문제는 정렬하는 과정 없이 답을 구할 수 있으므로 조금 더 쉽게 접근이 가능할 것 같다. 특정 분모 숫자에 대한 공약수가 1인 분자의 갯수는 69번 문제, 70번 문제를 해결할 때 사용했던 Φ(n)을 구하는 것과 동일하다. 다만, 69, 70번은 특정 조건을 만족하는 소수를 대상으로 계산하면 되었지만, 이번 문제는 가능한 분모 전체를 대상으로 구해야 하기 때문에 시간을 더 많이 요구하고 있다.

기존 문제에 사용한 방법을 이용해서 계산해봤지만, 1만개 계산에 6분 이상 소요되면서 전체를 계산하려면 최소 10시간 이상이 필요할 것으로 전망되어 다시 난감함을 느끼게 되었다. 특정 숫자에 대한 파이값을 계산하는 공식을 구글링을 통해 찾아 적용했는데(예를 들어 3과 5가 약수인 Φ(75)=75*(1-1/3)*(1-1/5)), 그래도 생각보다 시간이 많이 소요되었다. 몇가지 최적화를 해서 2시간 이상 실행 끝에 오답을 구했다.

각 숫자를 소인수분해 해서 공식을 적용했는데 프로그램을 잘 못 구성했는지 오답이 나왔고, 발상의 전환을 해서 소수가 나오면 해당 수(i)의 모든 배수를 대상으로 미리 (i-1/i)를 곱하는 형태로 구현했더니 기존 시간에 비해 터무니없이 빠르게 정답을 구할 수 있었다.

51번 이후에는 문제들은 이해되고 해결방안을 구현 가능하지만 극심한 성능문제가 발생하는 경우가 많이 나오고 있다. 단순 알고리즘 구현보다는 정수론 같은 수학을 이해하고 그것을 기반으로 효율적인 알고리즘 구현이 필요한 상황이 나오고 있어서, 수학공부까지 하면서 파이썬 공부를 위해 오일러 프로젝트를 계속 할 것인지 고민하는 상황이 계속 나오고 있는 것 같다.

Euler's Totient function, φ(n) [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than nine and relatively prime to nine, φ(9)=6.
The number 1 is considered to be relatively prime to every positive number, so φ(1)=1.

Interestingly, φ(87109)=79180, and it can be seen that 87109 is a permutation of 79180.

Find the value of n, 1 < n < 10⁷, for which φ(n) is a permutation of n and the ratio n/φ(n) produces a minimum.

(파이 함수라고도 부르는) 오일러의 토션트 함수 φ(n)은 n에 대해 상대적으로 소수인 n보다 작거나 같은 양의 정수를 결정하는 함수이다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작으면서 9에 대해서는 소수이므로 φ(9)=6이다.

1은 모든 양의 정수에 대해 상대적으로 소수이므로, φ(1)=1이다.

흥미롭게도 φ(87109)=79180이며, 87109는 79180의 순열이다.

n이 1보다 크고 10⁷보다 작을때, φ(n)이 n의 순열이며, n/φ(n)이 최소인 n을 구하시오.

--------------------------------------------------------------------------

문제가 그렇게 까다롭게 보이지는 않았는데, 50번 이후 문제 대부분이 그렇듯이 1~1천만까지 있는 숫자 중에서 답을 구해야 되는 덕분에 실행시간이 많이 필요하므로, 통상적인 방법으로 시간을 들여 답을 구하거나, 숨어 있는 수학이론을 찾아 빠른 시간 내에 답을 구해야 한다는 것이 실제 문제였다.

69번 문제를 생각해보면, n/φ(n)가 최대인 경우는 n이 크면서, φ(n)이 작은 경우를 구하기 위해, 소수인 약수가 가장 많은 경우를 구해서 해결했다. 70번 문제는 정반대인 n/φ(n)이 최소인 경우를 묻고 있으므로, n이 작으면서 φ(n)이 큰 경우이며, 이 경우를 충족하려면 2개의 소수가 약수인 경우가 될 것이다 (자신이 소수인 경우는 1 작은 수가 순열이 되지 않아 제외). 2개의 소수가 편차가 작을수록 값이 작아질 것이기 때문에 √10000000(천만, 10⁷)인 3300 전후의 두 숫자가 조건을 만족할 것으로 추정되었는데, 자신이 없어서 천~만 사이의 두 소수를 곱해서 나오는 값(n)의 φ(n)이 n의 순열이 되면서 n/φ(n)이 최소인 값을 구하는 과정을 통해 답을 구할 수 있었다.

처음에는 φ(n)을 구하면 순열을 만들어서 n이 있는지 확인했는데, n과 φ(n)을 리스트로 만들어 정렬해서 두 값이 같은지 비교하는 것이 훨씬 빠르게 순열 여부를 확인할 수 있었다.

Euler's Totient function, Φ(n) [sometimes called the phi function], is defined as the number of positive integers not exceeding n which are relatively prime to n. For example, as 1, 2, 4, 5, 7, and 8, are all less than or equal to nine and relatively prime to nine, Φ(9)=6.

It can be seen that n=6 produces a maximum n/Φ(n) for n≤10.

Find the value of n≤1000000 for which n/Φ(n) is a maximum.

오일러의 파이 함수(Totient function)인 Φ(n)은 n보다 크지 않고, n에 대해 상대적으로 소수인 양의 정수로 정의된다. 예를 들어, 1, 2, 4, 5, 7, 8은 9보다 작고, 9에 대해 상대적으로 소수이므로 Φ(9)=6이다.

위 표에서 보듯이 n이 10이하일 때, n/Φ(n)이 최대값인 것은 n=6인 경우이다.

n이 1백만 이하일 때, n/Φ(n)이 최대가 되는 값을 구하시오.

--------------------------------------------------------------------------

상대적으로 소수(relative prime)라는 표현이 재밌었는데, n을 (1일 제외하고) 나눌 수 없는 수로 이해했다. 8의 경우를 보면 8을 나눌 수 있는 2와, 2의 배수인 4, 6을 제외하고, 10의 경우에는 2의 배수인 2, 4, 6, 8과 5를 제외한 수가 된다.

처음에는 소수의 경우에는 n에서 1을 뺀 값(자신을 제외한 모든 수가 나눌 수 없으므로), 소수가 아닌 경우에는1~n-1까지 숫자 중 n을 나눌 수 있으면, 그 수의 배수까지 카운트해서 n에서 카운트한 값을 빼는 형태로 Φ(n)을 구했는데, 8에서 앞의 표가 다르게 Φ(n)=3이 나왔다. 원인을 찾아보니 2의 배수로 3을 카운트했는데(2, 4, 6), 1씩 더하면서 확인할 때 4도 8을 나눌 수 있는 숫자이므로 2번 카운트 된 것으로 분석되었다.

중복 계산되는 경우를 막기 위해, 간단하게 카운트를 통해 계산하는 방법을 포기하고, 매번 1~n-1까지 리스트를 만들고, n을 나눌 수 있는 숫자와 그 수의 배수를 리스트에서 삭제해 나가는 느리지만 정확하게 계산할 수 있는 방법으로 구현했다. 이번에도 처리속도가 문제였다. 짝수면 홀수만으로 리스트를 만드는 식으로 성능개선을 했지만, 큰 수가 나오면 느리긴 마찬가지였다.

가만히 관찰해보니 (자신을 제외하고 나눌 수 있는 수가 없으므로)  소수의 경우 Φ(n)이 커지고, n/Φ(n)은 작아지게 되어 있고, 해당되는 수의 (소수인) 약수가 많아질수록 n/Φ(n)이 커지고 있었다. 실행시간이 너무 길어져서 중간에 포기했지만, 최고값을 경신하는 경우는 2, 6, 30, 210, 2310, 30030이었는데 이것을 다시 보면 2, 2x3, 6x5, 30x7, 210x11, 2310x13으로 소수를 차례로 곱해가는 경우였다.

그래서, 백만보다 크지 않은, 연속된 소수의 곱을 구하니 답이 되었다.

The smallest number expressible as the sum of a prime square, prime cube, and prime fourth power is 28. In fact, there are exactly four numbers below fifty that can be expressed in such a way:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

How many numbers below fifty million can be expressed as the sum of a prime square, prime cube, and prime fourth power?

소수의 제곱, 세제곱, 네제곱의 합계로 구할 수 있는 가장 작은 수는 28이다. 실제로, 소수의 제곱, 세제곱, 네제곱을 합하여 구할 수 있는 50이하의 수는 다음과 같이 4가지가 있다:

    28 = 2² + 2³ + 2⁴
    33 = 3² + 2³ + 2⁴
    49 = 5² + 2³ + 2⁴
    47 = 2² + 3³ + 2⁴

소수의 제곱, 세제곱, 네제곱의 합으로 구할 수 있는 5천만 이하의 숫자는 몇가지인가?

--------------------------------------------------------------------------

문제 난이도는 20%로 높게 책정되어 있지만, 그동안 많이 다뤄왔던 소수의 연장선에 있고 파이썬이 큰 숫자를 쉽게 다룰 수 있게 지원하기 때문에 그렇게 어렵지 않게 해결할 수 있었다. 문제 난이도를 생각하면 좀 더 빠르게 해결가능한 방법이 있을 것 같았지만, 문제에서 요구하는 정석대로 접근해서 해결했다.

5천만 이하의 소수의 제곱, 세제곱, 네제곱을 구하고, 이것을 반복문을 통해 서로 더해나가면 어렵지 않게 구할 수 있다.

처음에, 문제에 있는 prime을 간과한 덕분에 모든 자연수의 제곱, 세제곱, 네제곱을 구하고, 반복문을 통해 더한 것을 모두 나열하니 1.47억개의 리스트가 나왔고, 여기에서 중복을 제거하려 하니 몇시간이 걸려도 답이 나오지 않는 상황이 발생했다.

문제를 다시 읽어보니 소수를 대상으로 하는 것이어서 제곱, 세제곱, 네제곱이 훨씬 적게 되고, 마지막에 중복을 제거하지 않고 집합 자료형을 이용하여 중복을 제거하면서 합을 구했더니 훨씬 간단한 로직으로 구할 수 있었다.

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

2자리 숫자 *3의 첫번째 자릿수를 바꾸면 가능한 9개의 값 중 6개인 13, 23, 43, 53, 73, 83이 소수이다.

56**3의 3번째, 4번째 자릿수를 같은 숫자로 바꾸면, 가능한 10개의 값 중 5개(56003, 56113, 56333, 56443, 56663, 56773, 56993)가 소수가 되는 최초의 숫자이다. 따라서, 56003은 이러한 속성을 가지는 숫자 중 가장 작은 소수이다.

같은 자리의 숫자 일부를 바꿔(인접한 숫자일 필요 없음) 8개의 소수를 만드는 가장 작은 소수는 무엇인가?

--------------------------------------------------------------------------

문제를 보고 가장 난감했던 부분은 대상 숫자의 자릿수가 없고, 몇 개의 숫자를 바꿀 것인지 없으며, 어느 자리를 바꿀 것인지에 대한 힌트도 없는데 8개의 소수를 만들어내는 숫자를 찾으라는 것이었다. 짝수는 소수가 아니므로 8개를 만들기 위해서는 1의 자리 숫자를 바꾸지 않는 것은 확실한데 다른 숫자는 엄두가 나지 않았다.

몇 번의 반복문을 통해 해결했는데, 전체 자릿수를 두고, 바꾸면서 들어갈 숫자가 몇자리인지 정하고, 고정되게 들어갈 숫자를 반복하게 하고, 조합(combinations)을 이용해 바꾸면서 숫자가 들어갈 자리를 반복하고, 각 자리에 0~9를 대입하여 그 중 소수가 몇 개인지 찾도록 하였다.

반복되는 부분이 많고, 반복문이 독립적이지 않고 앞의 반복문에 연동되고(6자리 숫자인데 바꾸면서 들어갈 숫자가 2자리이면 고정되게 들어갈 숫자는 4자리), 파이썬의 특징을 살리지 못하는 전통적인 방식으로 코딩을 하다 보니 생각보다 코딩은 복잡했는데 답은 구할 수 있었다.

앞의 반복문에 연동되는 범위 계산을 잘못해서 오답을 구한 덕분에, 프로그램을 구성하는 시간만큼 수정하는 시간이 필요했다.

Starting with 1 and spiralling anticlockwise in the following way, a square spiral with side length 7 is formed.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

It is interesting to note that the odd squares lie along the bottom right diagonal, but what is more interesting is that 8 out of the 13 numbers lying along both diagonals are prime; that is, a ratio of 8/13 ≈ 62%.

If one complete new layer is wrapped around the spiral above, a square spiral with side length 9 will be formed. If this process is continued, what is the side length of the square spiral for which the ratio of primes along both diagonals first falls below 10%?

1에서 시작해서 반시계 방향으로 회전하는 정사각형을 구하면 한 변의 길이가 7인 것은 다음과 같다.

37 36 35 34 33 32 31
38 17 16 15 14 13 30
39 18  5  4  3 12 29
40 19  6  1  2 11 28
41 20  7  8  9 10 27
42 21 22 23 24 25 26
43 44 45 46 47 48 49

흥미롭게도 오른쪽 아래쪽 대각선에는 제곱수가 놓이고, 더욱 흥미있는 것은 두 대각선에 있는 13개 숫자 중 소수는 8개이며, 비율은 8/13≈ 62%이다.

회전하면서 둘러싸는 새로운 층을 만들면, 한 변의 길이가 9인 정사각형을 만든다. 이 과정이 계속될 때, 두 대각선에 있는 숫자 중 소수의 비율이 10% 이하가 되는 것은 언제인가?

--------------------------------------------------------------------------

1에서 오른쪽 아래에 대각선 방향에 있는 9, 25, 49, ... 는 제곱수이므로 소수가 아니다. 사각형이 커질 때마다 새롭게 검증 대상이 되는 숫자는 처음의 3, 5, 7, 두번째 13, 17, 21의 세 숫자씩이 된다.

대각선에 추가로 포함되는 3개 숫자 중 소수를 판별하고, 대각선 숫자 중 소수의 비율을 구하면 되므로 그렇게 까다롭지 않게 해결 가능하다.

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

소수인 41은 다음과 같이 여섯 개의 연속된 소수의 합으로 표현할 수 있다:

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서 가장 긴 연속된 소수의 합인 소수이다.

1000 이하에서 가장 긴 연속된 소수의 합인 소수는 21개 항목이 있는 953이다.

1백만 이하에서 가장 긴 연속된 소수의 합인 소수는 무엇인가?

--------------------------------------------------------------------------

이 문제에서 시행착오는 시작을 반드시 2로 해야한다고 생각했던 것이다. 프로젝트 오일러에서는 구했던 답이 틀렸다고 나와 이유를 찾는데 한참 걸렸다.

간단하게는 1백만 이하의 소수를 구하고, 그 리스트의 첫번째 요소로 시작해서 만들어지는 1백만 이하의 가장 큰 소수, 두번째 요소로 시작하는 1백만 이하의 가장 큰 소수를 차례로 만들면서 가장 긴 연속된 소수의 합을 구하면 된다.

파이썬 프로그램에 익숙해지기 위해 시작한 프로젝트 오일러 문제풀기였지만, 50번이 넘어가면서 파이썬 보다는 수학에 대한 이해의 비중이 점점 더 커지는 것 갈은데, 흥미가 완전히 없어질때까지 문제풀기를 계속해 보겠다. 이제는 문제들을 풀고 나서 포스팅 해야하기 때문에 포스팅 주기가 매우 길어질 것 갈다.

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

3330씩 커지는 등차수열 1487, 4817, 8147은 2가지 면에서 특이하다. (i) 세 숫자 모두 소수이고, (ii) 각 4자리 숫자는 서로의 순열이다.

1, 2, 3자리 소수에서는 이런 특성을 가지는 등차수열이 없으며, 4자리 숫자에서 하나의 등차수열이 더 있다.

이 수열의 3개 항목을 연결한 12자리 숫자는 무엇인가?

--------------------------------------------------------------------------

첫 시행착오는 3개의 숫자가 서로의 순열일 뿐이지, 한쪽 방향으로 각 자리수를 이동하는 것이 아니었는데 그런 방식으로 해결하려 했던 것이다. 방향을 잘못 잡았던 덕분에 문제를 처음부터 다시 해결해야 했다.

해결한 방법은 지금 생각하면 효율성은 낮지만, 4자리 소수를 구하고, 그 수로 만들 수 있는 순열 중 소수인 것을 구하고, 소수+순열이 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다.

이 방법의 성능을 개선할 방법으로는 4자리 소수 리스트를 만든 후에, 특정 숫자(소수)와 그 숫자로 만들 수 있는 순열 중 소수인 것을 소수 리스트에서 삭제하면서 구하고, 3개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다. 이렇게 하면 중복되는 소수여부 검사, 순열 작성 등의 부담이 줄어들 것이다.

The first two consecutive numbers to have two distinct prime factors are:

    14 = 2 × 7
    15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors each. What is the first of these numbers?

2개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 2개의 숫자는 다음과 같다:

    14 = 2 × 7
    15 = 3 × 5

3개의 서로 다른 소수 인수를 가지는, 처음으로 연속되는 3개의 숫자는 다음과 같다:

    644 = 2² × 7 × 23
    645 = 3 × 5 × 43
    646 = 2 × 17 × 19.

4개의 서로 다른 소수를 인자로 가지는, 처음으로 연속되는 3개의 숫자를 구하시오. 이 중 첫 숫자는 무엇인가?

--------------------------------------------------------------------------

5번 문제를 풀 때 소인수분해를 구현할 만큼 파이썬을 이해한 것이 아니어서 우회하는 방법으로 해결했는데, 이 문제에서는 소인수분해를 이용해서 해결했다.

해당하는 숫자보다 작은 값을 가지는 소수 리스트를 만들어 나가면서, 해당 숫자를 소수 리스트의 값으로 차례대로 계속 나눠 몇 개의 소수로 구성되는지를 판별하는 것이다. 예를 들어, 45는 2로 나눠지지 않고, 3으로는 2번 나눠지고(45/3=15, 15/3=5), 5는 5로 1번 나눠지므로 소인수는 3,5인 2개로 판별한다.

문제에서 요구하는 대로 소인수분해를 단순하게 구현한 덕분에 답을 구하는 데 시간이 많이 소요되었다. 아무래도 이 문제에서 요구하는 것은 문제에 충실하게 답을 구하는 것 보다는, 좀 더 효율적으로 답을 구하는 방법을 생각해 보는 것일 수도 있겠다.