800. Hybrid Integers

 

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

예를 들어, 800=2552은 합성 정수이다.

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

C(800)=2이고 C(800800)=10790이다.

C(800800800800)을 구하시오.

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

 

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

 

pqqp <= 800800800800

log(pqqp) <= log(800800800800)

log(pq)+log(qp) <= log(800800800800)

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

 

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

 

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

757. Stealthy Numbers

양의 정수 a,b,c,d가 ab=cd=N이고 a+b=c+d+1인 경우, 양의 정수 N은 은밀하다고(stealthy) 한다.

예를 들어, 36=4x9=6x6은 은밀하다.

106 이하에는 2851개의 은밀한 숫자(Stealthy Numbers)가 있다.

1014 이하에는 몇 개의 은밀한 숫자가 있는가?

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

 

문제는 그리 까다롭지 않아, 문제에서 요구한 것만 구현하면 코드가 그리 길지 않다. 숫자의 약수를 구해서, 약수가 n개인 경우 n/2개까지 두 숫자를 각각 a, c로 두고, b, d를 연산을 통해 구하고, a+b=c+d+1인 경우를 찾도록 만들었다.

 

하지만, 예시로 나온 1백만 이하에 몇 개가 있는지 검증하는데 벌써 속도 문제를 만나게 되었다. 문제에서 요구한대로 했을때 구해지는 답을 보고 4의 배수만 나오기 때문에 그것으로 성능을 조금 개선했다. 그래도, 약수를 구하는 부분에서 시간이 많이 소요되어서, 대상 숫자를 보니 전체 약수의 가운데 부근에 있었다. 예를 들어 설명하면 약수가 10개인 경우 4,5번째 숫자 또는 3,4번째 숫자가 a,c가 되는 것이었다. 그렇게 해서 속도를 개선하니 1백만 개 이하의 은밀한 숫자 갯수를 맞게 구할 수 있어서 문제에서 요구한 대로 구현했음을 알 수 있었다.

 

하지만, 1백만 개에 9초의 시간이 필요했으면, 문제에서 요구한 1경 개를 대상으로 구하려면 적어도 900000000초(250000시간)의 시간이 필요한 상황임을 알 수 있었다. 그 말은 문제를 있는 대로 구현하는 것이 아니고 새로운 알고리즘을 찾는 것을 요구하는 정수론 문제라는 것이었다.

 

인터넷을 검색해 보니, 깃헙에 누군가가 구현한 내용에서 bipronics라는 명칭으로 x*(x+1)*y*(y+1)을 구하는 정수 배열을 활용해서 구했다고 설명했는데, 그 정수 배열이 문제에서 요구하는 답과 동일한 것이었다. 왜 약수 중에 a+b=c+d+1인 약수와 x*(x+1)*y*(y+1)이 동일한지 이해는 안되었지만 그렇다고 한다. 처음 접근한 방법으로 안되었을 때, 숫자 리스트를 만들고 a+b=c+d+1을 만족하는 경우에 flag을 바꾸는 형태로 해결할 수 있을지 고민하다가, 변수가 너무 많아 포기했는데 조금은 비슷한 접근인 것 같기도 했다.

 

이 개념으로 구현하니 1백만 개는 0.04초만에 구할 수 있었는데, 그래도 1경 개를 구하는 데에는 시간이 꽤나 걸렸다. 조건에 맞는 리스트를 구하는 것보다 중복을 제거하는 데 시간이 더 많이 걸린 것이 함정이었다. 파이썬의 list(set())의 조합으로 중복을 제거했는데, 7천만 개 이상 리스트에서 중복 제거하는 데 많은 시간을 필요로 했다. 대충 1분 이내에 조건에 맞는 리스트를 구했는데 거기에서 중복을 제거하는 데 10분 이상 소요되었다.

 

357. Prime Generating Integers

 

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번 문제를 물어봤는데 문제에서 요구하는 그대로 가장 정직하게 프로그램을 제시했다. 성능 문제만 고려하지 않으면 즉시 적용 가능하도록 구현해 내는 것이 어찌보면 대단하다 싶었다.

700. Eulercoin

 

레온하르트 오일러는 1707년 4월 15일에 태어났다.

배열 1504170715041707n mod 4503599627370517을 생각해 보라.

이 배열의 요소는 이전에 찾은 모든 오일러코인보다 작은 오일러코인으로 정의된다.

 예를 들어, 첫 요소인 1504170715041707은 첫 오일러코인이다. 두번째 요소인 3008341430083414는 1504170715041707보다 크기 때문에 오일러코인이 아니다. 세번째 요소인 8912517754604는 새로운 오일러코인이 된다.

처음 두 오일러코인의 합계는 1513083232796311이다.

모든 오일러코인의 합계를 구하시오.

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

 

프로젝트 오일러의 문제가 그렇듯 문제 자체는 간단하고 프로그램으로 구현하기도 쉽다. 다만, 정수론에 대한 이해 없이 문제를 정직하게 구현하면 시간의 함정에 빠지게 된다. 문제를 보면 오일러코인이 1이 되면 끝나는데, 최악의 경우 4,500조 횟수를 반복해야 구할 수 있기 때문이다.

 

문제대로 정직하게 구현하면 처음 16번 오일러코인까지는 그런대로 빨리 구할 수 있지만 그 이후로는 시간이 많이 소요되며, 처음 20번 오일러코인까지 나온 특성(이전 코인과의 차이가 같거나 크게 나옴)을 이용해서 구현하면 54번째까지는 빨리 구하지만 그 뒤로는 마찬가지로 시간이 너무 많이 소요된다.

 

그래서 정수론의 도움을 받으려면, 나머지 함수의 나누기 특성에 대한 이해가 필요하다. 문제를 공식으로 만들어  설명하려면 우선 상수 1504170715041701=euler, 4503599627370517=divider로 정의하자.

(euler*n)%divider=x 형태가 된다.

n=(x/euler)%divider

n=(x*euler-1)%divider가 되는데, 여기서 나머지 함수의 나누기 특성을 위해 페르마의 소 정리를 보면,

ap-1 ≡ 1(%p), 단 p는 소수이고 a는 p의 배수가 아닌 경우

ap-1=a*ap-2≡ 1(%p)가 된다.

이를 위 공식에 적용하면 n=(x*euler(divider-2))%divider가 된다.

그리고 (euler(divider-2))%divider는 상수 형태이므로 프로그램으로 구현하면 어렵지 않게 구할 수 있다(3451657199285664). 페르마의 소 정리를 이용해서 계산했는데, 좀 더 빠른 성능을 위해서는 확장 유클리드 개념을 활용하면 된다고 한다.

 

이 내용을 구현하면 오일러코인 값이 1부터 시작할 때 몇번째 배열 값이 되는지 쉽게 구할 수 있고, 배열 값이 이전 값보다 큰 경우를 제외하게 되면 실제 오일러코인 합계에 포함되는 값들을 구할 수 있다.

 

나머지 함수의 나누기 특성만으로 구한 것으로 설명은 되어 있었지만, 정수론에 대한 이해가 부족해서인지 빠른 형태로 구현하지 못해서, 두 프로그램의 결과를 조합해서 문제에서 요구하는 오일러코인의 합계를 구할 수 있었다.

836. A Bold Proposition

 

A를 잔여 특성 p를 갖는 근을 적분하는(radically integral) 적분된 로컬 필드를 가로지르는 아핀 평면(affine plane)이라 하자.

정규화 된 하르 척도(Haar measure)를 사용하여 A의 개방형 선 부분을 U라 (고려)한다.

U를 A에 직교 커널로 임베딩하는 자코비안(Jacobian)의 최대 가능한 판별식으로 f(m,p)를 정의한다.

f(20230401,57)을 구하시오. 굵은 글씨로 표현된 단어의 첫 글자를 연결하여 답하시오.

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

 

수학 배경이 없으면 알지도 못하는 단어들이 많이 나오는 문제여서 보류했다가 나중에 풀어보는데, 앞에서 나온 어려운 문제는 이해할 필요가 없고(문제를 한글로 바꾸는 것도 매끄럽게 못할 지경이다) 마지막 줄만 읽어보면 되는 것이었다.

 

즉, 영어로 된 문제에서 굵은 글씨로 표현된 단어의 첫 글자를 연결해서 답을 하면 된다. 답이 3단어여서 띄어쓰기, 기호 추가 등을 통해 제대로 된 단어를 만들었는데 그럴 필요 없이 그냥 글자를 쭉 연결해서 1개 단어 형태로 답하면 된다.

 

제목은 대단한 제안이지만 쉬어가기 문제였다.

493. Under The Rainbow

 

항아리에 일곱 가지 무지개 색의 공이 각각 10개씩, 총 70개의 공이 항아리에 있다.

랜덤하게 20개의 공을 선택할 경우 몇 가지의 색이 있겠는가?

소숫점 9자리까지 답을 구하시오(a.bcdefghij형태).

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

 

처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 70C20의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.

 

그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(60C20/70C20), 특정 색이 있을 확률은 정반대가(1-60C20/70C20) 되며, 7개 공 각각에 대해 구하면(7*(1-60C20/70C20)) 된다.

 

이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.

 

 

 

 

 

816. Shortest Distance Among Points

 

이차원 평면에 다음 랜덤 숫자 생성기를 이용하여 좌표의 배열인 Pn을 생성하자:
S0=290797
Sn+1=Sn2 mod 50515093

Pn=(S2n,S2n+1)

 

P0,⋯,Pk-1 중 임의의 (서로 다른) 두 좌표의 최단 거리를 d(k)라고 하면, d(14)=546446.466846479이다.

소숫점 9자리까지 나오도록 반올림하여  d(2000000)을 구하시오.

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

 

번호가 높은 문제여서 해결한 사람이 많지 않지만, 5% 난이도 문제여서 그렇게까지 까다롭지는 않다.

 

초기값과 값을 구하는 공식, 해당 값을 이용한 좌표를 구하는 공식이 있으므로 요구하는 대로 값을 계산하면 된다.

 

다만, 예시를 보고 정확하게 프로그램을 작성하지 않아 한가지 실수가 있었는데, mod함수를 사용해서 연속된 두 좌표의 거리 중 가장 짧은 것을 계산한 것이었다. n개 좌표가 있으면 n-1번 계산했는데, 하필이면 예시가 12번째, 13번째 사이가 최단거리인 경우여서 잘못된 프로그램으로도 예시의 답이 나와서 잘못된 부분을 찾는데 애먹었다.

 

하지만, 곰곰히 생각해 보면, 문제에서는 임의의 두 좌표에 대한 거리를 묻고 있으므로 생성가능한 모든 조합에 대해 거리를 계산해야 되어서 시간이 매우 많이 필요하다. 복잡도가 O(n)에서 O(n2)이 되면서 시간이 기하급수로 늘어나는 문제가 있었다.

 

몇시간이 걸려도 해결되지 않아 코드를 일부 개선해봤지만 시간이 더 걸리는 등 알고리즘에 대한 근본적인 해결책이 필요했다. 관련 내용을 검색해보다 복잡도를 낮출 아이디어를 구했다. 2백만개의 좌표가 mod 함수에 의해 구해져서 들쑥날쑥이어서 모든 좌표 간의 거리를 계산했는데, 원점을 기준으로 정렬하면 앞뒤 좌표간의 거리만 계산해도 해결 가능하게 되어 복잡도가 줄어든다.

 

전체 실행시간을 보면, Pn 좌표를 생성하는데 3.6초, 원점 기준으로 정렬하는데 6초, 좌표 간 거리를 계산하는데 10초가 걸려 20초 만에 답을 구할 수 있었다.

808. Reversible Prime Squares

 

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개를 찾을 수 있어 실행시간은 여전히 필요했다.

751. Concatenation Coincidence

작아지지 않는 정수의 수열인 an은 다음 과정을 통해 양의 실수 θ에서 만들어 낼 수 있다.

    b1

    bn=└bn-1┘(bn-1-└bn-1┘+1) , n>=2일 때

    an=└bn

└ ┘은 버림을 나타낸다.

예를 들어, θ=2.956938891377988...는 피보나치 수열(2, 3, 5, 8, 13, 21, 34, 55, 89, ...)를 생성한다.

양의 정수의 수열인 an을 연결하면, τ로 표기하는 a1에서 시작해서 소숫점 아래의 연속된 요소를 결합한 a1.a2a3a4...모양의 실수가 된다.

예를 들어, θ=2.956938891377988...에서 나오는 피보나치 순열을 연결하면 τ=2.3581321345589...가 되며, θ 값에 대해 θ와 τ는 다르다.

a1=2에서 시작해서 수열을 결합했을 때 τ=θ가 되는 유일한 값 θ를 찾으시오. 답안은 반올림하여 소숫점 24자리까지 구하시오.

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

 

처음에는 고민을 많이 하고 접근했는데, 생각보다 어렵지 않게 해결 가능했다.

 

처음에는 θ=2로 시작해서, 공식을 소숫점 25자리까지 반복 적용해서 나온 숫자(τ)를 다시 θ로 설정하는 작업을 τ=θ가 나올때까지 반복하면 되는데 몇 번 반복하지 않고 답을 구할 수 있었다.

205. Dice Game

 

피터는 (피라미드 모양) 4면 주사위 9개를 가지고 있고, 각 주사위 면에는 1,2,3,4가 적혀 있다.

콜린은 (정육면체 모양) 6면 주사위 6개를 가지고 있고, 각 주사위 면에는 1,2,3,4,5,6이 적혀 있다.

피터와 콜린이 주사위를 굴려 합계를 비교해서 합계가 큰 사람이 이긴다. 둘의 합계가 같으면 무승부이다.

4면 주사위를 가진 피터가 콜린을 이길 확률은 얼마인가? 정답을 소숫점 7자리까지 반올림으로 나타내어 0.abcdefg 형태로 제시하시오.

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

 

처음에 랜덤 함수를 이용하여 둘의 주사위를 생성하고, 합계를 비교하는 몬테카를로 시뮬레이션 방법을 활용하여 천만번 게임을 운영한 승패를 구했는데 답이 맞지 않았다.

 

그래서 어쩔수 없이 단순하게 전체 경우를 구하는 형태로 접근을 바꿨다. 파이썬 라이브러리의 중복순열(from itertools import production)을 이용하여 피터와 콜린의 경우의 수를 각각 구하고, 그것을 합계로 바꿔 반복문을 통해 두 사람의 모든 경우를 비교하는 형태로 구현했다. 이렇게 설명하면 간단하지만 두 사람의 경우를 곱하면 122억이 넘기 때문에 보기보다 많은 시간이 걸리는 문제였다(몬테카를로 시뮬레이션을 활용하더라도 100억 번은 넘어야 결과에 가까운 답이 나올 수 있다는 뜻으로 이해되었다).

 

다시 생각해보니, 피터는 9~36, 콜린은 6~36의 합계가 나올 수 있지만 경우의 수는 각각 262,144, 46,656이므로 많은 경우 중복되어 나온다. 앞의 방식처름 122억 회 이상 비교하는 것 보다는 각 값에 대한 발생횟수를 가중치 형태로 만들어서 계산하니 2초 내외에 답을 구할 수 있었다.

 

문제를 잘못 이해해서 답을 abcdefg 형태로 구했는데 계속 틀리게 나와 알고리즘을 다시 검토하는 등 시간을 많이 소모했는데, 답은 이미 맞게 구했고 '0.abcdefg' 형태로 답을 쓰면 되는 것이었다.

203. Squarefree Binomial Coefficients

 

이항계수 (n k)는 위 그림과 같이 파스칼 삼각형이라 불리는 삼각형 형태로 나타낼 수 있다.

파스칼 삼각형의 첫 8줄은 12개의 서로 다른 수로 구성된다: 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21, 35.

n이 제곱수로 나눠지지 않으면 양의 정수 n을 squarefree라 부른다. 파스칼 삼각형 첫 8줄의 서로 다른 12개 숫자 중에서 4와 20을 제외하고는 squarefree이다. 첫 8줄에서 sqarefree인 숫자의 합계는 105이다.

파스칼 삼각형 첫 51줄의 서로 다른 squarefree 숫자의 합을 구하시오.

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

 

생각가능한 몇 개의 단계로 나눠 답을 구했는데 그래도 25초 내외 시간 안에 답을 구할 수 있었다.

 

처음에는 파스칼 삼각형 모양의 리스트를 만들어가면서 서로 다른 숫자의 리스트를 구했다. 파스칼 삼각형 자체를 만들려고 했는데, 그것이 뒤에 다시 쓰이지 않기 때문에 파스칼 삼각형의 현재 행을 구하면서 서로 다른 숫자는 별도 리스트에 추가하는 형태로 했다.

 

서로 다른 숫자 리스트를 정렬하고, 그 최대값 이하의 제곱수 리스트를 만들었다. 서로 다른 숫자 리스트의 각 숫자에 대해 제곱수 리스트 숫자로 모듈러 연산(%)을 수행하고, 나머지가 0인 경우는 sqaurefree가 아니므로 해당하는 숫자의 리스트를 만들었다.

 

마지막으로, 서로 다른 숫자 리스트에서 squarefree가 아닌 숫자를 제외한 숫자를 모두 더해서 합계를 구했다.

 

그렇게까지 까다로운 문제는 아니었는데 2가지 오류때문에 해결하는데 시간이 좀 걸렸다. 하나는 51줄을 55줄로 잘못 설정해서 발생한 것이었는데 문제를 다시 읽고 해결할 수 있었다. 다른 하나는 2번째 단계에서 처음에는 나머지가 0인 경우에 서로 다른 숫자 리스트에서 해당하는 숫자를 삭제하는 형태로 해서 바로 결과를 구하도록 구성했는데, for문 대상 리스트에서 숫자가 삭제되면서 인덱스 값이 모두 바뀌어서 엉뚱한 연산을 하는 상황이 생겼다. 상황을 보고도 어떤 문제 때문에 생기는 것인지 빨리 인지하지 못해서 오류를 해결하는 데 많은 시간이 걸렸다.

 

187. Semiprimes

 

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

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

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

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

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

 

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

 

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

 

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

686. Powers Of Two

 

27=128은 "12"로 시작하는 첫번째 2의 거듭제곱수이며, "12"로 시작하는 다음 2의 거듭제곱수는 280 이다.

p(L,n)을 L로 시작하는 십진수 중 2j가 n번째 가장 작은 j를 나타낸다고 정의하면, p(12,1)=7이고 p(12,2)=80이다.

또한 p(123,45)=70이다.

p(123,678910)을 구하시오.
--------------------------------------------------------------------------

 

문제에서 요구하는 대로 구성하면 프로그램의 구조는 간단하다. 2를 계속 곱해가면서 L로 시작되는 n번째 숫자를 찾아 거듭제곱수를 알려주면 된다.

 

이렇게 구현하면 예시로 나와있는 p(12,1), p(12,2), p(123,45)는 어렵지 않게 구할 수 있다. 하지만, 2의 거듭제곱수 중에서 123으로 시작하는 678910번째 숫자가 2의 몇 거듭제곱인지 찾는 것은 데이터 허용범위가 넓은 파이썬으로도 어려운 일이었다. (이번에는 4300자릿수 이상을 넘을 수 없다는 에러메시지를 봤던 것 같다)

 

프로젝트 오일러의 높은 번호 문제는 난이도가 낮아도, 간단히 해결 가능한 것이 아니라 (주로 상상도 못한 크기의 숫자로) 한계가 숨어 있고, 이것을 어떻게 해결해내는 것인지가 추가로 포함되어 있는 것 같다.

 

이번 문제에서는 앞의 3자리만 동일하면 되기 때문에, 일정크기 이상으로 커지면 앞의 3자리에 영향을 미치지 않을 아랫쪽 수를 10000으로 나눠 없애는 형태로 계산했는데, 정확한 숫자를 구하는 것이 아니어서 살짝 걱정되었지만 맞출 수 있었다.

166. Criss Cross

 

0~9 사이의 숫자 d로 채워지는 4x4 크기의 격자가 있다.

그 격자는 위와 같이 나타낼 수 있으며, 예시에서 각 열과 행의 합은 12이고, 대각선의 합 또한 12이다.

0~9 사이의 숫자 d로 구성되는 4x4  격자에서 각 행, 열, 두 대각선의 합계가 동일한 경우는 몇가지가 있는가?

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

 

처음에는 기계적으로 중복순열을 만들어서 해결하려 했으나, 1016크기의 중복순열을 만들면서 메모리 에러가 발생했다.

 

그래서 격자의 (0,0)에서 (4,4)까지 a부터 p까지 자리기호를 매기고, (16차) 반복문으로 생성되는 숫자를 기준으로 첫 행의 가로 합계(sum=a+b+c+d)가 나머지 가로 합계(e+f+g+h, i+j+k+l, m+n+o+p), 세로 합계(a+e+i+m, b+f+j+n, c+g+k+o, d+h+l+p), 대각선(a+f+k+p, d+g+j+m)과 동일한 지 확인하도록 구성을 했는데, 1016 크기만큼 반복을 하면서 시간이 대책없이 오래 걸리는 문제가 발생했다.

 

그래서, 고민을 하다 다른 사람이 해결한 방법을 검색해 봤는데, 변수 갯수를 줄이는 형태로 접근해서 실행시간을 개선하는 방법을 제시한 것이 있어 그 방법을 적용해 봤다. 앞 문단에서 설명한 것과 마찬가지 상황에서 sum=a+b+c+d로 했을 때,  가로 세로 합계 공식을 바꿔, h=sum-e-f-g, l=sum-i-j-k, p=sum-m-n-o, m=sum-a-e-i, n=sum-b-f-j, o=sum-c-g-k를 구할 수 있고, 대각선 공식을 이용하면 j=sum-d-g-m이 된다.

 

a, b, c, d, e, f, g, i, k에 대해 반복문을 구성하여, h, o는 반복문의 값으로 구하고, m을 먼저 구해서 j를 구하고, 그 값을 이용해서 l, p, n를 구할 수 있다. 대각선의 합계가 맞는지 확인하고(sum=a+f+k+p), 연산에 의해 구해진 값(h,j,l,m,n,o,p)이 0~9 사이의 값인 경우에 문제의 조건을 만족하는 경우가 된다.

 

이것을 반복문을 활용해서 계속 구해나가면 복잡도가 1016에서 109로 1/107이 줄어들어, 이전보다는 훨씬 빠르지만 그래도 답을 구하는 데는 시간이 좀 필요했다. 다만, 스스로 생각해서 끌까지 해결하지 못하고 다른 사람의 아이디어를 봐야 해결가능하다는 것이 씁쓸했다.

243. Resilience

 

분자가 분모보다 작은 양의 분수를 진분수(proper fraction)라 한다.

어떤 분모 d에 대해 d-1개의 진분수가 있다. 예를 들어, d=12일때 진분수는 다음과 같다.
1/12,2/12,3/12,4/12,5/12,6/12,7/12,8/12,9/12,10/12,11/12.

약분되지 않는 분수를 탄력분수(resilient fraction)이라 부르자.

특정 분모 d에 대해 약분되지 않는 분자의 비율을 R(d)라 정의한다. 예를 들어, R(12)=4/11이다.

실제로, d=12는 R(d)<4/10인 가장 작은 분모이다.

R(d)<15499<94744인 가장 작은 분모 d를 구하시오.

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

 

약분되지 않는 분수를 학교에서는 기약분수(inreducible fraction)로 배웠는데, 여기에서는 무슨 차이가 있는지 모르겠지만 탄력분수로 정의하고 있다.

 

처음에는 모든 숫자를 대입해서 계산을 시도했는데, 시간이 너무 많이 걸렸다. 기약분수가 적은 경우를 찾는 형태여서 생각해보니 69번 문제를 변형한 문제처럼 보였다.

 

일단 많이 나눠주는 수의 곱으로 분모가 되어야 작아질 것이기 때문에 처음에는 짝수를 대상으로 시도했는데, 결과값 패턴을 보니 2와 3의 공배수인 6의 배수가 값이 작은 것이 보였다. 가만히 생각해보니 작은 소수의 곱으로 구성되는 숫자일수록 나눠지는 숫자가 많아 정답에 근접하게 나오게 되는 패턴을 찾았다.

 

그래서, 일단은 2에서 시작해서 나오는 소수의 곱을 대상으로, 배수를 5번씩 계산해서 정답보다 낮은 경우를 찾도록 했다.(예를 들어, 2의 경우 2,4,6,8,10, 2와3의 곱인 6의 경우 6,12,18,24,30, 2와3과5의 곱인 30의 경우 30,60,90,120,150 등을 계산하도록 했다)

 

소수의 곱은 생각보다 기하급수로 커졌고, 그 덕분에 정답 또한 생각했던 것 보다는 엄청 큰 값이었고, 답에 근접한 값만 계산하게 했어도 상당한 시간이 필요했다.

206. Concealed Square

 

"_"가 숫자 한 자리이며, 제곱값이 1_2_3_4_5_6_7_8_9_0인 양의 정수를 구하시오.

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

 

난이도 5%인 문제여서 그런지 그나마 단순한 방법으로 해결가능했다.

 

일단 19자리 숫자이면서 1의 자리에 0, 백 자리에 9, 만 자리에 8, 백만 자리에 7, 억 자리에 6, 백억 자리에5, 조 자리에 4, 백조 자리에 3, 경 자리에 2, 백경 자리에 1이 들어가는 숫자를 구하면 되는데,  첫 자리가 1로 시작하므로 제곱하여 백경이 되는 1,000,000,000부터 시작할 것이고, 첫 자리가 2보다 작아야 하므로 √2*1,000,000,000 보다는 작아야 할 것이다.

 

그리고, 1의 자리가 0이므로 마지막 숫자는 0이 되므로 이 사이의 숫자를 반복문을 통해 계산해서 어렵지 않게 구할 수 있었다.

135. Same Differences

 

양의 정수 x, y, z가 등차수열의 연속된 요소일 때, x2-y2-z2=n으로 구해지는 가장 작은 양의 정수 n은 n=27일 때 정확하게 2개의 해답이 있다:

342-272-202=122-92-62=27.

정확하게 10개의 해답이 있는 최소값은 n=1155일 때이다.

10개의 해답이 있는 1백만 이하의 n은 몇 개 인가?

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

 

등차수열이기 때문에 처음에는 x를 기준으로, x2-(x-a)2-(x-2a)2=n으로 수식을 만들어서, 정리하니 x2-6ax+5a2=-n이어서, (x-a)(x-6a)=-n이 되었다. 모양은 좀 이상했지만 처음 값 x와, 차이 a 기준으로 n의 약수의 곱이 된다는 것을 알 수 있었다.

(제대로 접근한 사람은 가운데 y를 기준으로 (y+a)2-y2-(y-a)2=n으로 수식을 만들어서, 전개하면 4ay-y2=n이 되고, 차이 a 기준으로 정리하면 a=(n+y2)/4y가 된다)

 

처음에는 약수의 갯수만 관련이 있다고 생각하고 약수가 20개 인 수(두 수의 곱이므로 절반인 10개의 해답을 만드는 수로 추정)의 갯수를 찾도록 구현했는데, 약수 만드는 함수의 성능이 나빠서 시간이 너무 많이 걸리고, 이를 개선해서 조금 빨리 돌아가도록 했는데 오답이 나왔다.

 

다시 확인해보니, 후보가 되는 것은 약수가 맞지만 두 약수의 곱이 아니기 때문에 약수를 대상으로 등차수열 조건(a=(n+y2)/4y, a<y, a는 정수)을 만족하는지 확인해야 되는 것이었다. 그렇게, 단순히 약수의 갯수를 세는 것이 아니라 약수를 대상으로 등차수열을 만들 수 있는 것이 몇 개인지 확인하도록 변경해서 답을 구할 수 있었다.

 

그리고, 처음에는 n의 약수를 1~n/2까지 비교하도록 되어 있던 함수 성능을 개선한 이후에야 수분 내에 답을 구할 수 있어서, 성능의 중요성을 다시 한 번 느꼈다.

130. Composites with Prime Repunit Property

 

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만 이상의 숫자까지 대상이 되면서, 제외되어야 하는 소수가 목록에 포함되었던 것이 문제였다.

129. Repunit Divisibility

 

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

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

A(n)이 10을 초과하는 최초의 n은 17이다.

A(n)이 1백만을 초과하는 최초의 n을 구하시오.

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

 

문제를 조금 부연설명하면 gcd(n,10)=1이라 했으므로, n은 2, 5와 공약수가 없는 숫자이다(2와 5로 나눠지지 않는다). 이것만 가지고 구현했을 때 예시에서 나온 A(7), A(41)이나 결과가 10이 넘는 A(n)의 값은 쉽게 구할 수 있는데, 결과가 1백만을 초과하는 것을 구하려면 시간이 대책없이 필요했다.

 

처음 2부터 입력해서 나온 n, k의 결과값 목록을 보면서도 생각하지 못했는데, 오일러 프로젝트를 풀고 있는 다른 블로거의 설명을 보고 빨리 해결하는 방법을 구할 수 있었다.

 

중요한 단서는 k가 n보다 클 수 없다는 것이다. 그것을 보고 시작지점을 변경해서 빠른 시간 내에 답을 구할 수 있었다.

125. Palindromic Sums

회문인 숫자 595는 다음과 같이 연속된 제곱수의 합계로 나타낼 수 있다는 점에서 흥미롭다.

62+72+82+92+102+112+122

천 이하에는 연속된 제곱수 합계로 나타낼 수 있는 회문이 11개 있고, 이들의 합계는 4164이다. 주의할 것은 1=02+12이지만 양의 정수의 합계를 고려하고 있으므로 해당하지 않는다.

108(1억) 이하의 숫자 중에 회문이면서 연속된 제곱수의 합계로 나타낼 수 있는 숫자의 합을 구하시오.

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

 

회문은 4번 문제에서 처음 나온 이후에 오일러 프로젝트에 몇 번 나온 문제이고 여기까지 풀었으면 함수로도 가지고 있을 것이다.

 

일단 문제에서 요구한 대로 구현해 봤다. 1은 제외한다고 했으므로 2에서 1억까지 올라가면서 회문에 해당하는 숫자를 대상으로, 각 숫자가 연속된 제곱수의 합계로 나타낼 수 있는지 판별하는 것이다. 이를 위해 제곱수의 목록을 만들어두고 시작하는 자리를 이동해가면서 차례로 합해나가는 과정을 반복하도록 하고, 제곱수가 비교할 숫자보다 크면 그 수에 대해서는 검증을 중단하도록 했다.

 

실행해보니 처음에는 빠르지만 천만이 넘어가면서 실행속도가 엄청나게 느려지는 것이 보였다. 하지만 조금 기다려주면 끝이 나는 수준이어서 이렇게 해결하기로 했는데, 제곱수를 1억까지 만들었다가 그것이 넘는 경우가 필요해지면서 거의 마지막에 리스트의 인덱스 에러가 생기고 결과를 확인하지 못했다. 제곱수 리스트를 조금 더 크게 만든 후에 답을 구할 수 있었다.

 

하지만, 다른 사람은 어떻게 접근했는지 확인했을 때, 정반대로 접근하는 것이 있었는데 빠른 해결을 위해서는 좋은 방법 같아서 아이디어를 적는다. 접근을 반대로 해서, 1만의 제곱이 10억이므로, 1만 이하의 제곱수 목록을 만들고 각 숫자를  연속해서 나오는 결과 목록을 생성한 후에, 이 중 회문인 것만 답으로 선택하는 방법이다. 실험삼아 구현해봤는데, 결과 목록을 만드는 데 생각보다 많은 시간이 걸려 큰 차이가 나지 않을 것 같았다.

+ Recent posts