책 이야기

예를 들어 134468과 같이, 숫자를 왼쪽에서 오른쪽으로 읽을 때 각 자릿수가 이전 자릿수보다 작지 않으면 증가수라고 한다.

비슷하게, 예를 들어 66420과 같이 각 자릿수가 이전 자릿수보다 크지 않으면 감소수라고 한다.

예를 들어, 155349와 같이 증가하지도 감소하지도 않는 숫자를 bouncy number라고 한다.

명백하게, 100 미만으로는 bouncy number가 있을 수 없다. 1000 미만으로는 절반이 넘는 525개 숫자가 bouncy number이다. 실제로, bouncy number의 비중이 처음으로 50%가 되는 숫자는 538이다.

놀랍게도, bouncy number는 점차 많아져서 21780이 되면 bouncy number의 비중이 90%가 된다.

bouncy number가 정확히 99%가 되는 가장 작은 숫자를 찾으시오.

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

한 자리 숫자는 증가, 감소, bouncy가 있을 수 없으므로 10부터 시작해서 솟자를 계속 키워나가면서 증가수, 감소수, bouncy number를 판별하게 구성하면 된다.

구성할 때 한 가지 고려할 것은 이전 숫자와 값이 같으면 아직 증가수인지 감소수인지 판별을 유보해야 한다는 것이다. 처음에 이 부분을 잘못 생각하고 유보할 때 증가수, 감소수 플래그를 무조건 True로 값을 넣도록 프로그램을 만들었는데, 3자리에서는 유효하지만 4자리 숫자에서 오류를 만들게 되어 있어서 판별할 숫자를 50%만 제시했으면 이유를 찾지 못할뻔 했다. (값이 같을 때 이전에 증가수/감소수로 판별된 경우 이전 판별을 유지해야 되는데 잘 못 생각해서 계속 유보하게 만든 것이 문제였다)

조건문만 잘 구성하면, 반복문을 통해 까다롭지 않게 구할 수 있다.

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)을 리스트로 만들어 정렬해서 두 값이 같은지 비교하는 것이 훨씬 빠르게 순열 여부를 확인할 수 있었다.