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개 단어 형태로 답하면 된다.

 

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

+ Recent posts