책 이야기

By using each of the digits from the set, {1, 2, 3, 4}, exactly once, and making use of the four arithmetic operations (+, −, *, /) and brackets/parentheses, it is possible to form different positive integer targets.

For example,

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

Note that concatenations of the digits, like 12 + 34, are not allowed.

Using the set, {1, 2, 3, 4}, it is possible to obtain thirty-one different target numbers of which 36 is the maximum, and each of the numbers 1 to 28 can be obtained before encountering the first non-expressible number.

Find the set of four distinct digits, a < b < c < d, for which the longest set of consecutive positive integers, 1 to n, can be obtained, giving your answer as a string: abcd.

{1, 2, 3, 4}의 각 숫자를 한 번씩 사용하고, 4개 연산자(+, -, *, /)와 괄호를 사용하여, 서로 다른 정수를 구할 수 있다.

예를 들면 다음과 같다.

    8 = (4 * (1 + 3)) / 2
    14 = 4 * (3 + 1 / 2)
    19 = 4 * (2 + 3) − 1
    36 = 3 * 4 * (2 + 1)

주의할 것은 숫자를 연결하여 12+34로 계산하는 것은 허용되지 않는다.

{1, 2, 3, 4} 집합을 이용하여 31가지 다른 숫자를 구할 수 있고, 최대값은 36이다. 그리고, 1~28까지는 연속해서 구할 수 있다.

1부터 n까지 가장 긴 연속으로 숫자를 구할 수 있는 a<b<c<d인 숫자 4개를 구하고, 답안은 abcd 형태로 작성하라.,

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

몇가지 고민할 사항이 있어 나중에 해결했는데, 인터넷에서 누군가가 알려준 eval() 함수를 활용하면서 많은 부담을 덜 수 있었다.

연산자는 +,-,*,/의 4가지를 사용하는데, 예시에 있는 것처럼 연산자의 우선순위와 관계없이 계산하기 위하여 괄호를 이용해 인위적으로 순서를 지정할 필요가 있다. 연산자가 들어갈 곳은 3자리이므로 괄호를 통해 순서를 강제하는 것은 연산자의 순서를 1,2,3이라 할 때 (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)의 6가지 경우가 있는데 이 중 (3,1,2)는 괄호를 통해서도 만들어낼 수 없는 경우이기 때문에 5가지 연산을 하게 만들면 된다.

4가지 숫자를 점차 커지는 순서로 만들고, 생성된 숫자 4개를 순열을 통해 다양한 순서를 만들고, 각 순서에 4가지 연산자 조합에 대해 5가지 연산을 해서, 결과가 양의 정수일 때 결과에 더하고, 모은 결과를 집합, 정렬을 통해 순서대로 배열해서 1부터 가장 긴 연속된 숫자가 있는 4가지 숫자 조합을 찾으면 된다.

위 경우 중 4가지 숫자를 커지는 순서로 만드는 데 반복문 4회, 순열 생성에 반복문 1회, 연산자를 3자리에 배열하는 데 반복문 3회를 해서 들여쓰기를 많이 하는 구조가 되었다.

그리고, 0으로 나누는 경우가 발생할 수 있으므로 exception을 사용하여 예외처리했는데, 개발툴인 Visual Studio Code가 익숙하지 않아서 exception을 무시하도록 설정하지 않아 처음에는 계속 F5를 눌러야 했다. 나중에 보니 Raised Exceptions을 Breakpoints로 설정하지 않도록 하는 옵션이 있어 결과를 빨리 볼 수 있었다.

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

The cube, 41063625 (3453), can be permuted to produce two other cubes: 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest cube which has exactly three permutations of its digits which are also cube.

Find the smallest cube for which exactly five permutations of its digits are cube.

(3453의) 세제곱 수인 41063625는 다른 두 세제곱 수인 56623104 (3843의 세제곱), 66430125 (4053의 세제곱)을 만들어 내도록 바뀔 수(순열을 만들 수) 있다. 실제로, 41063625는 그 자릿수로 세제곱 수인 3개의 순열을 만들 수 있는 가장 작은 수이다.

그 자릿수로 5개의 세제곱 수인 순열을 만들 수 있는 가장 작은 세제곱 수는 무엇인가.

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

가장 간단한 접근은 한 숫자의 세제곱 수를 구하고, 순열을 만들어서 4개 이상의 세제곱 수가 있는 가장 작은 수를 구하는 것이다.

이렇게 할 경우 세제곱 수에 대한 순열을 만들고, 이들 중 세제곱 수가 몇 개인지 검증하는데 많은 시간이 소요될 것으로 예상되어 접근을 다르게 해보기로 했다. 1부터 커가면서 세제곱 수를 만들고, 거기에 있는 자릿수를 정렬하여, 이전의 (정렬된) 세제곱 수 중 그 값과 같은 것이 4개 이상인 것을 찾는 방식으로 접근해 봤다. 논리는 조금 허술한 것 같았는데, 늦지 않는 시간에 정답을 구할 수 있었다.

It can be seen that the number, 125874, and its double, 251748, contain exactly the same digits, but in a different order.

Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits.

숫자 125874와 그 것의 2배인 251748에는 순서가 다르지만 정확히 같은 자릿수가 있다.

2배, 3배, 4배, 5배, 6배 한 숫자와 동일한 자릿수가 있는 가장 작은 양의 자연수는 무엇인가.

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

6배를 한 숫자와 동일한 자릿수가 되려면 1로 시작해야 한다는 것을 알 수 있다. 그 전제에서 원래 숫자와 2배, 3배, 4배, 5배, 6배 한 숫자를 리스트 형태로 정렬해서 비교한 것이 같은 숫자를 찾으면 된다.

51번 이후 문제를 100번까지 모두 풀고 순차적으로 포스팅할 생각이었는데, 아무리봐도 26번과 같이 해결 못하는 문제가 곳곳에 있을 것 같아서 해결하는 순서대로 포스팅하기로 했다.

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개 이상인 경우 각 수의 차이가 같은 것이 있는지 찾는 것을 반복하는 것이다. 이렇게 하면 중복되는 소수여부 검사, 순열 작성 등의 부담이 줄어들 것이다.

A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

순열은 객체의 정렬된 배열이다. 예를 들어, 3124는 1,2,3,4로 만들 수 있는 순열 중 하나이다. 모든 순열이 수치나 알파벳으로 나열되어 있으면 사전 순서(lexicographic order)라 부른다. 0,1,2의 사전 순열은 다음과 같다.

012   021   102   120   201   210

0,1,2,3,4,5,6,7,8,9의 백만번째 사전 순열은 무엇인가?

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

조금 머리를 쓰면 계산에 의해 풀수도 있을 것 같긴 했는데, 0123456789로 순열을 구해서 100만째 것을 찾는 단순한 방법으로 해결했다.

실제 조금만 머리를 쓰면 각 자리수를 바꾸는 조합은 순열이므로 팩토리얼(!)로 구할 수 있고, 첫자리가 0으로 시작되는 경우 가능한 순열은 9!=362880번 있으며, 이를 적용하면 2로 시작되는 순열이 되는 것임을 알 수 있다. 이러한 방식으로 백만에서 숫자를 빼 나간다면 해당하는 순열의 숫자를 좀 더 빠른 시간내에 찾을 수 있겠지만 단순하게 구현 가능해서 실제로 코드를 작성해 보지는 않았다.