책 이야기

Euler discovered the remarkable quadratic formula:

n²+n+41

It turns out that the formula will produce 40 primes for the consecutive integer values 0≤n≤39. However, when n=40,40²+40+41=40(40+1)+41 is divisible by 41, and certainly when n=41,41²+41+41 is clearly divisible by 41.

The incredible formula n²−79n+1601 was discovered, which produces 80 primes for the consecutive values 0≤n≤79. The product of the coefficients, −79 and 1601, is −126479.

Considering quadratics of the form:

    n²+an+b, where |a|<1000 and |b|≤1000
    where |n| is the modulus/absolute value of n
    e.g. |11|=11 and |−4|=4

Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n=0.

오일러는 놀라운 이차방정식을 발견했다:

n²+n+41

이 공식은 0≤n≤39 범위에서 연속된 40개의 소수를 만들어내는 것으로 밝혀졌다. 그러나, n=40일 때, 40²+40+41=40(40+1)+41은 41로 나눠지고, 당연하게도 n=41일 때,41²+41+41은 분명하게 41로 나눠진다.

믿을수 없는 공식 n²−79n+1601은 0≤n≤79에서 80개의 연속된 소수를 만드는 것으로 밝혀졌다. 계수인 -79와 1601의 곱은 −126479이다.

|a|<1000이고, |b|≤1000인 다음 형태의 이차방정식 n²+an+b을 생각해 보자.
|n|은 n의 계수값/절대값이다. 즉, |11|=11이고, |−4|=4이다.

n=0으로 시작해 최대 길이의 연속된 소수를 만들어 내는 계수 a와 b의 곱을 구하라.

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

아직 26번을 해결하는 아이디어가 떠오르지 않아 생략하고 진행한다.

문제는 읽기 까다로운 편인데, 반복문을 이용한 단순한 접근으로 해결 가능하다. a는 -999에서 999, b는 -1000에서 1000까지 검증하는 반복문에, n을 0부터 대입하면서 가장 길게 소수를 만드는 경우를 계산하면 된다.

출제 의도는 좀 더 효율적으로 계산하는 방법을 고민하기를 원했던 것 같은데 단순한 방법으로 해결 가능했다.

The Fibonacci sequence is defined by the recurrence relation:

F_n = F_n−1 + F_n−2, where F₁ = 1 and F₂ = 1.

Hence the first 12 terms will be:

    F₁ = 1

    F₂ = 1

    F₃ = 2

    F₄ = 3

    F₅ = 5

    F₆ = 8

    F₇ = 13

    F₈ = 21

    F₉ = 34

    F₁₀ = 55

    F₁₁ = 89

    F₁₂ = 144

The 12th term, F₁₂, is the first term to contain three digits.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

피보나치 배열은 회귀하는 관계로 정의된다:

F_n = F_n−1 + F_n−2,  F₁ = 1이고 F₂ = 1.

따라서, 처음 12개 요소는 F₁ = 1, F₂ = 1, F₃ = 2, F₄ = 3, F₅ = 5, F₆ = 8, F₇ = 13, F₈ = 21, F₉ = 34, F₁₀ = 55, F₁₁ = 89, F₁₂ = 144가 된다.

12번째인 F₁₂는 처음으로 3자리 숫자가 되는 요소이다.

처음으로 1000자리 숫자가 되는 요소는 몇번째인가인가?

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

재귀함수를 배울 때 가장 많이 사용되는 예시가 피보나치 수열이다. 이 문제는 특정 피보나치 수를 구하는 것이 아니라 일정 조건을 만족하는 피보나치 수를 찾는 문제이기 때문에 재귀함수 보다는 반복문이 더 적절한 것으로 판단되었다.

계속 얘기하지만 파이썬이 큰 숫자도 간단히 다룰 수 있게 구현되어 있기 때문에, 까다롭지 않게 해결 가능했다.

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로 시작되는 순열이 되는 것임을 알 수 있다. 이러한 방식으로 백만에서 숫자를 빼 나간다면 해당하는 순열의 숫자를 좀 더 빠른 시간내에 찾을 수 있겠지만 단순하게 구현 가능해서 실제로 코드를 작성해 보지는 않았다.

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

진약수의 합계가 원래 숫자와 같은 숫자를 완전수라고 한다. 예를 들어, 28의 진약수의 합은 1+2+4+7+14=28이며, 이것은 28이 완전수임을 의미한다.

어떤 숫자 n의 진약수의 합이 n보다 작은 경우 부족, 진약수의 합이 n보다 큰 경우 과잉이라 한다.

1+2+3+4+6=16인 12는 가장 작은 과잉수 이므로, 24는 두 과잉수의 합으로 표현될 수 있는 가장 작은 수이다. 수학적 분석에 의해, 28213보다 큰 모든 자연수는 두 과잉수의 합으로 표현될 수 있다. 그러나, 두 과잉수의 합으로 표현될 수 없는 가장 큰 숫자는 이 상한보다 작다고 알려져 있지만, 분석에 따라 이 상한은 더 작아질 수 없다.

두 과잉수의 합으로 표현될 수 없는 모든 양의 정수의 합계를 구하시오.

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

자신을 제외한 약수의 합계가 자신과 같으면 완전수, 작으면 부족수, 크면 과잉수라고 하는 것을 이번 문제에서 처음 알았다. 28213보다 큰 모든 자연수는 두 과잉수의 합으로 표현 가능하므로, 두 과잉수의 합으로 표현할 수 없는 양의 정수는 28213 이하의 숫자 중에 있다. 즉, 1~28213 사이의 숫자 중에 두 과잉수의 합으로 표현할 수 없는 숫자를 구하면 되는 것이다.

특정 숫자가 두 과잉수의 합으로 표현 가능한지 확인하는 방법을 구현하는 것이 이 문제를 해결하는 데 가장 중요한 부분인데, 조금 단순한 방법으로 해결하기로 했다. 12~28213(실제는 12를 뺀 28201) 사이 숫자 중 과잉수를 구하고, 두 과잉수를 반복해서 더해서 나오는 숫자 중 28213보다 작은 수를 구한 후에, 집합을 활용해서 중복을 제거했다.

Using names.txt (right click and 'Save Link/Target As...'), a 46K text file containing over five-thousand first names, begin by sorting it into alphabetical order. Then working out the alphabetical value for each name, multiply this value by its alphabetical position in the list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list. So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

5천 개 이상의 이름이 들어 있는 46K 크기의 names.txt를(우클릭하고 "(으)로 링크 저장") 이용하여, 우선 알파벳 순서로 정렬하시오. 그리고, 목록의 알파벳 순서 위치와 알파벳 값을 곱하여 점수를 구하라.

예를 들어, 알파벳 순서로 정렬된 목록에서 COLIN의 값은 3+15+12+9+14=53이며, 목록의 938번째 있다. 따라서, COLIN의 점수는 938x53=49714이다.

파일에서 모든 이름 점수의 합계는 무엇인가?

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

파일을 이용하는 첫번째 문제이다. 파일로 읽어들인 문자열을 쉼표 기준으로 구분하여 따옴표(")를 제거하면서 리스트로 바꾸고, 알파벳 값으로 딕셔너리를 만들면 문제를 해결하기 위한 기초 작업은 끝난 것이다.

내장 함수를 이용해 정렬하고, 딕셔너리를 활용해 각 단어의 글자를 값으로 바꾸고 순서를 활용해 점수를 구하는 과정을 모든 단어를 대상으로 반복하면 된다.

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).
If d(a) = b and d(b) = a, where a ≠ b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

d(n)을 n의 진약수(n을 나눌 수 있는 n보다 작은 수)의 합으로 정의하자.

a≠b이고 d(a)=b이고 d(b)=a이면, a와 b는 친화수의 쌍(amicable pair)이며 a와 b는 각각 친화수(amicable numbers)이다.

예를 들어, 220의 진약수는 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 100이므로 d(220)=284이다. 284의 진약수는 1, 2, 4, 71, 142이므로 d(284)=220이다.

10000 이하의 모든 친화수의 합계를 구하라.

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

약수를 구하고, 진약수의 합계를 구하는 함수를 만들고 나면 간단히 해결 가능한 문제이다.

1부터 10000까지 진약수를 구하면서, 진약수의 합계인 d(a)가 a보다 큰 경우에만 검사하도록 하여(d(a)가 작은 경우는 이미 검증했을 것이므로) 실행성능도 개선하고, 같은 수를 2번 계산하지 않도록 하였다.

n! means n × (n − 1) × ... × 3 × 2 × 1

For example, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800,
and the sum of the digits in the number 10! is 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27.

Find the sum of the digits in the number 100!

n!은 n × (n − 1) × ... × 3 × 2 × 1을 뜻한다.

예를 들어, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 이고,

10!의 각 자리 숫자의 합은 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 이다.

100!의 각 자리 숫자의 합을 구하시오.

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

팩토리얼로 불렀던 !를 사전을 찾아보니 계승이라고 되어 있던데 익숙하지 않은 단어이다.

파이썬에서 integer의 크기가 크기 때문에 자료형 고민없이 100!을 구하면 되고, 이것을 리스트 형태로 변환하여 각 자리 숫자를 더하는 방법으로 어렵지 않게 해결하였다.

You are given the following information, but you may prefer to do some research for yourself.

• 1 Jan 1900 was a Monday.
• Thirty days has September,
  April, June and November.
  All the rest have thirty-one,
  Saving February alone,
  Which has twenty-eight, rain or shine.
  And on leap years, twenty-nine.
• A leap year occurs on any year evenly divisible by 4, but not on a century unless it is divisible by 400.

How many Sundays fell on the first of the month during the twentieth century (1 Jan 1901 to 31 Dec 2000)?

다음의 정보가 제공되어 있는데, 당신은 직접 연구해 보는 것을 더 선호할 것 같다.

• 1900년 1월 1일은 월요일이다.
• 9월, 4월, 6월, 11월에는 30일까지 있다.
  나머지 달에는 31일까지 있다.
  2월은 예외로 하는데, 항상 28일까지 있고, 윤년에는 29일까지 있다.
• 윤년은 4년 마다 발생하는데, 100년은 아니며, 400으로 나눠지는 해는 윤년이다.

20세기(1901년 1월 1일~2000년 12월 31일) 첫 달에는 일요일이 며칠이나 있는가?

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

늘 접하기 때문에 쉽게 생각하던 달력을 프로그램으로 만들려면 얼마나 많은 부분을 고려해야 하는지 몸으로 느끼게 만들어주는 문제이다. 복잡한 알고리즘을 새로 고안할 필요는 없지만, 예외사항 처리에 대한 섬세함이 요구된다.

매 해 1월 1일이 무슨 요일인지 계산하고(그 해의 날짜수(365 또는 366일)를 7로 나누는 방식), 해당 요일이 1월 1일인 경우 31일까지 일요일이 몇 번 있는지 계산하는 것을 100년 동안 반복하면 된다.

처음에 문제를 잘 못 이해해서 전체 일요일 갯수를 계산하였고(그것도 매 달 계산하는 방법으로), 덕분에 문제해결에 더 많은 시간이 들었다.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom of the triangle below:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be solved by brute force, and requires a clever method! ;o)

아래 삼각형의 정상에서 시작해서 아래에 있는 다음 줄의 인접한 숫자로 내려갈 때, 정상에서 바닥까지 최대 합계는 (굵게 표시된) 23이다.

3
7 4
2 4 6
8 5 9 3

즉, 3 + 7 + 4 + 9 = 23이다..

아래에 있는 삼각형의 정상에서 바닥까지 최대 합계를 구하시오:

75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

주의: 여기에는 16384개 경로밖에 없기 때문에, 모든 경로를 시도하는 방법으로 해결할 수 있다. 그러나, 100개 행이 있는 삼각형에서 동일한 방식으로 답을 구하는 67번 문제는 브루트 포스(brute force) 방법으로 해결할 수 없고, 현명한 방법이 필요하다.

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

모든 경로를 한번씩 다 운영해보고 최대값을 구하는 것이 가장 간단한 방법인데 문제의 마지막에서 다른 방법을 찾아보기를 권하고 있어 고민을 했던 문제이다.

고민해서 적용한 방법은 위에서 내려오는 방법으로 계산하는 것이 아니고, 밑에서 위로 올라가면서 계산하면 16384개 경로를 비교하는 것 보다는 조금 적은 복잡도를 가지는 방법이 가능했다. 14번째 행 첫번째 숫자인 63에 더해질 수 있는 숫자는 4와 62인데 이 중 더 큰 62를 더하는 방법을 반복해 나가면 숫자의 갯수만큼 반복해 나가는 것으로 답을 구할 수 있다.

If the numbers 1 to 5 are written out in words: one, two, three, four, five, then there are 3 + 3 + 5 + 4 + 4 = 19 letters used in total.

If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used?

NOTE: Do not count spaces or hyphens. For example, 342 (three hundred and forty-two) contains 23 letters and 115 (one hundred and fifteen) contains 20 letters. The use of "and" when writing out numbers is in compliance with British usage.

1에서 5까지 숫자를 영어 단어로 적으면 one, two, three, four, five이며, 여기에는 총 3+3+5+4+4=19개의 글자가 사용되었다. 1에서 1000(one thousand)까지 숫자가 영어 단어로 적혀 있으면, 몇 개의 글자가 사용되는가?

주의: 빈칸, 하이픈은 세지 마시오. 예를 들어, 342(three hundred and forty-two)에는 23개 글자가 있으며, 115(one hundred and fifteen)에는 20개 글자가 있다. "and"는 영국식 영어에서 숫자를 셀 때 사용하는 것에 따른다.

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

처음으로 딕셔너리를 이용하여 문제를 해결하였다. 문제 자체는 20까지 각 숫자, 30 등 십단위, 백, 천까지 사전에 넣고 반복문과 조건문을 이용하면 되는 것이어서, 신경을 조금 써야되지만 까다로운 문제는 아니었는데 학교에서 미국식 영어로 배웠던 덕분에 'and'가 들어가는 규칙을 확인하는 것이 더 까다로운 부분이었다.

ㄱ솔직히 이야기하면 문제 해결하는 시간만큼 숫자 딕셔너리 작성하는 데 시간이 소요되었다.

2¹⁵ = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.

What is the sum of the digits of the number 2¹⁰⁰⁰?

2¹⁵ = 32768이고, 각 자리 숫자의 합은 3 + 2 + 7 + 6 + 8 = 26이다.

2¹⁰⁰⁰ 각 자리 숫자의 합은 얼마인가?

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

2의 1000승은 매우 큰 수이지만 파이썬은 큰 수를 쉽게 다룰 수 있으므로 고려할 필요는 없고, 결과값의 각 자리 숫자를 어떻게 구할 것인지만 고민하면 되는 문제이다.

이 문제를 해결할 때에는 숫자, 리스트, 문자열 간 자료형 변환에 익숙하지 않아서 결과값을 10으로 계속 나누면서 나머지를 더하는 반복문으로 답을 구했다.

Starting in the top left corner of a 2×2 grid, and only being able to move to the right and down, there are exactly 6 routes to the bottom right corner.

How many such routes are there through a 20×20 grid?

2x2 격자의 왼쪽 위에서 출발하고, 오른쪽과 아래쪽으로만 이동할 수 있으면, 오른쪽 아래로 이동하는 데에는 정확히 6개의 경로만 있다.
20x20 격자에는 몇 개의 경로가 있는가?
--------------------------------------------------------------------------

격자를 만들고, 이동하는 형태로 반복문을 작성하면 해결 가능할 것 같았는데, 이상하게도 반복문이 만들어지지 않으면서 혼자 논리가 꼬이는 일이 계속되어 답을 구하는 데 많은 시간이 걸렸다. 그래도 아직 답을 구하는 규칙을 찾지 못한 26번에 비하면 빨리 답을 구한 편이긴 하다.

15번이면 비교적 앞쪽의 문제인데 해결방안을 못찾아 애먹으면서 답답했지만, 한 번 논리가 꼬여버린 논리를 푸는 것은 어려운 일이라는 것을 다시 한 번 느꼈고, 좋은 논리로 해결하지 못하고 단순하게 해결할 수 밖에 없어 답답했던 문제이다.

divide and conquer라는 분할정복 방법으로 접근할 수 밖에 없었고, 1x1에서는 2개, 2x2에서는 6개, 3x3에서는 20개로 늘어나는 과정을 쪼개어서(3x3 경로를 1x1, 2x2의 경로를 이용해 구하기) 이전 과정의 합계를 활용하는 규칙을 찾아 그것을 프로그램으로 해결하였다.

이제 생각해보니 전체 2n개의 경로에 n개의 한 방향을 입력하면 되는 것이어서 조합을 이용하면 간단히 답을 구할 수 있는 것이었다.

The following iterative sequence is defined for the set of positive integers:

    n → n/2 (n is even)

    n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.

다음 반복되는 수열은 양수의 집합으로 정의된다.

    n → n/2 (n이 짝수인 경우)

    n → 3n + 1 (n이 홀수인 경우)

위 규칙을 적용하고 13부터 시작하면 다음 수열을 구할 수 있다.

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

(13에서 시작하여 1로 끝나는) 이 수열에는 10개 요소가 있음을 알 수 있다. 아직 이것이 증명되지는 않았지만(콜라츠 문제), 모든 숫자는 1로 끝나는 것으로 생각된다.

100만 미만 숫자 중 가장 긴 수열을 만드는 숫자는 무엇인가?

주의: 수열이 시작되면 1백만을 넘을 수 있다.

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

1에서 시작하여 반대방향으로 가는 형태로 접근해 봤는데 적절한 해결책을 찾아낼 수 없어서, 단순하게 1백만까지 반복해가면서 가장 길게 1을 구하는 수열을 찾는 형태로 해결하였다. 좀 더 빨리 답을 구할 수 있도록 개선할 방법이 있을 것 같은데 문제를 해결할 동안 떠오르지 않았다.

직관적으로는 모든 숫자가 1로 끝날 것 같은데 아직 증명되지 않은 추측이라 하니 수학의 세계는 생각보다 심오하다.

Work out the first ten digits of the sum of the following one-hundred 50-digit numbers.

37107287533902102798797998220837590246510135740250

46376937677490009712648124896970078050417018260538

74324986199524741059474233309513058123726617309629

91942213363574161572522430563301811072406154908250

23067588207539346171171980310421047513778063246676

89261670696623633820136378418383684178734361726757

28112879812849979408065481931592621691275889832738

44274228917432520321923589422876796487670272189318

47451445736001306439091167216856844588711603153276

70386486105843025439939619828917593665686757934951

62176457141856560629502157223196586755079324193331

64906352462741904929101432445813822663347944758178

92575867718337217661963751590579239728245598838407

58203565325359399008402633568948830189458628227828

80181199384826282014278194139940567587151170094390

35398664372827112653829987240784473053190104293586

86515506006295864861532075273371959191420517255829

71693888707715466499115593487603532921714970056938

54370070576826684624621495650076471787294438377604

53282654108756828443191190634694037855217779295145

36123272525000296071075082563815656710885258350721

45876576172410976447339110607218265236877223636045

17423706905851860660448207621209813287860733969412

81142660418086830619328460811191061556940512689692

51934325451728388641918047049293215058642563049483

62467221648435076201727918039944693004732956340691

15732444386908125794514089057706229429197107928209

55037687525678773091862540744969844508330393682126

18336384825330154686196124348767681297534375946515

80386287592878490201521685554828717201219257766954

78182833757993103614740356856449095527097864797581

16726320100436897842553539920931837441497806860984

48403098129077791799088218795327364475675590848030

87086987551392711854517078544161852424320693150332

59959406895756536782107074926966537676326235447210

69793950679652694742597709739166693763042633987085

41052684708299085211399427365734116182760315001271

65378607361501080857009149939512557028198746004375

35829035317434717326932123578154982629742552737307

94953759765105305946966067683156574377167401875275

88902802571733229619176668713819931811048770190271

25267680276078003013678680992525463401061632866526

36270218540497705585629946580636237993140746255962

24074486908231174977792365466257246923322810917141

91430288197103288597806669760892938638285025333403

34413065578016127815921815005561868836468420090470

23053081172816430487623791969842487255036638784583

11487696932154902810424020138335124462181441773470

63783299490636259666498587618221225225512486764533

67720186971698544312419572409913959008952310058822

95548255300263520781532296796249481641953868218774

76085327132285723110424803456124867697064507995236

37774242535411291684276865538926205024910326572967

23701913275725675285653248258265463092207058596522

29798860272258331913126375147341994889534765745501

18495701454879288984856827726077713721403798879715

38298203783031473527721580348144513491373226651381

34829543829199918180278916522431027392251122869539

40957953066405232632538044100059654939159879593635

29746152185502371307642255121183693803580388584903

41698116222072977186158236678424689157993532961922

62467957194401269043877107275048102390895523597457

23189706772547915061505504953922979530901129967519

86188088225875314529584099251203829009407770775672

11306739708304724483816533873502340845647058077308

82959174767140363198008187129011875491310547126581

97623331044818386269515456334926366572897563400500

42846280183517070527831839425882145521227251250327

55121603546981200581762165212827652751691296897789

32238195734329339946437501907836945765883352399886

75506164965184775180738168837861091527357929701337

62177842752192623401942399639168044983993173312731

32924185707147349566916674687634660915035914677504

99518671430235219628894890102423325116913619626622

73267460800591547471830798392868535206946944540724

76841822524674417161514036427982273348055556214818

97142617910342598647204516893989422179826088076852

87783646182799346313767754307809363333018982642090

10848802521674670883215120185883543223812876952786

71329612474782464538636993009049310363619763878039

62184073572399794223406235393808339651327408011116

66627891981488087797941876876144230030984490851411

60661826293682836764744779239180335110989069790714

85786944089552990653640447425576083659976645795096

66024396409905389607120198219976047599490197230297

64913982680032973156037120041377903785566085089252

16730939319872750275468906903707539413042652315011

94809377245048795150954100921645863754710598436791

78639167021187492431995700641917969777599028300699

15368713711936614952811305876380278410754449733078

40789923115535562561142322423255033685442488917353

44889911501440648020369068063960672322193204149535

41503128880339536053299340368006977710650566631954

81234880673210146739058568557934581403627822703280

82616570773948327592232845941706525094512325230608

22918802058777319719839450180888072429661980811197

77158542502016545090413245809786882778948721859617

72107838435069186155435662884062257473692284509516

20849603980134001723930671666823555245252804609722

53503534226472524250874054075591789781264330331690

50자리 숫자 100개의 합계에서 첫 10자리 숫자를 구하시오.

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

C언어에서 16비트 정수의 최대 크기는 65,535(2¹⁶-1)이고, 32비트 정수 최대 크기는 4,294,967,595(2³²-1)이다. 하지만 파이썬에서는 정수가 최대값을 넘어가면 자동으로 long으로 자료형을 바꾸기 때문에 이 문제를 파이썬으로 풀면 자료형에 대한 고민없이 해결 가능하다.

100개 숫자를 합하고 앞의 10개 숫자만 뽑아내면 된다.

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

 1: 1

 3: 1,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21

28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?

삼각수 수열은 자연수를 더하면서 생성된다. 따라서, 7번째 삼각수는 1+2+3+4+5+6+7=28이다. 처음 10개 요소는 다음과 같다.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

처음 일곱 개 삼각수의 인수를 나열해 보면,

 1: 1

 3: 1,3

 6: 1,2,3,6

10: 1,2,5,10

15: 1,3,5,15

21: 1,3,7,21
28: 1,2,4,7,14,28

28은 처음으로 5개가 넘는 약수를 가지는 수임을 알 수 있다. 500개 약수를 가지는 첫 삼각수는 무엇인가?

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

삼각수라는 단어가 익숙하지 않았는데, 1부터 시작하는 연속된 자연수의 합을 뜻한다고 한다. 인수를 구하는 함수를 작성하고, 반복문을 통해 인수가 처음으로 500개 이상인 삼각수를 구하면 된다.

좀 더 효율적으로 구하려면, 소수인 인수의 곱으로 나타내고, 제곱수를 이용하면 된다. 5번 문제와 연관있는 부분이기도 한데, 예를 들어 28은 2²x7¹이므로 제곱수는 각각 2, 1이며, 약수의 갯수는 (2+1)(1+1)=6이 되는 특성을 활용하여 답을 구할수도 있을 것이다.

In the 20×20 grid below, four numbers along a diagonal line have been marked in red.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

The product of these numbers is 26 × 63 × 78 × 14 = 1788696.

What is the greatest product of four adjacent numbers in the same direction (up, down, left, right, or diagonally) in the 20×20 grid?

20x20 격자에서 대각선으로 연속된 4개 숫자는 굵게 표시되어 있다.

08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08

49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00

81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65

52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91

22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80

24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50

32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70

67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21

24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72

21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95

78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92

16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57

86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58

19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40

04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66

88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69

04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36

20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16

20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54

01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48

네 숫자의 곱은 26x63x78x14=1788696이다.

20x20 격자에서 같은 방향으로(위쪽, 아래쪽, 왼쪽, 오른쪽, 대각선) 연속된 4개 숫자의 곱이 가장 큰 것은 얼마인가?

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

파이썬 자료형 처리에 익숙하지 않아서, 이 문제도 문제해결 보다는 자료형을 어떻게 처리하는 것이 효율적인지 고민하는 데 더 많은 시간이 들었던 문제이다. 위 격자를 읽어서 20x20 크기의 2중 리스트를 생성하기로 결정하고, 문제 자체는 반복문을 이용하여 곱이 가장 큰 경우를 구하면 되기 때문에 어렵지 않게 해결할 수 있었다.

연속된 4개의 숫자를 곱하기 때문에, 첫 줄을 가로로 곱하는 경우 17번을 하면 끝까지 확인할 수 있는 것처럼 각 방법별 반복횟수를 조금 신경써주면 된다. 각 방법별 시작, 끝 위치가 달라 가로, 세로, 왼쪽 대각선, 오른쪽 대각선의 4가지 반복구조를 구성해서 구하였다.

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

10 이하 소수의 합은 2+3+5+7=17이다.

2백만 이하 소수의 합을 구하시오.

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

단순하게 200만 이하의 소수를 구해서 합했는데, 속도를 빠르게 하기 위해서 2, 3으로 나눠지는 숫자는 소수 여부를 판별하지 않고 지나가도록 했다.

A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

There exists exactly one Pythagorean triplet for which a + b + c = 1000.

Find the product abc.

피타고라스 세 쌍은 a<b<c이며, a² + b² = c²인 자연수 3개를 말한다.

예를 들어, 3² + 4² = 9 + 16 = 25 = 5²이다.

a+b+c=1000인 피타고라스 세 쌍은 정확히 하나가 있다.

세 수의 곱을 구하시오.

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

많이 들어왔던 직각삼각형의 세 변을 구하는 피타고라스의 정리를 활용한 문제이다.

a는 1, b는 a+1에서 시작해서 1씩 키워가면서 두 수의 제곱의 합이 1000-a-b의 제곱인지 확인하는 형태로 구하였다. 단순하게는 반복 횟수가 a=998, b=999이지만, 조금 더 생각해서 이 숫자를 낮추는 것이 정답을 빨리 구하는 방법이 될 것이다.

The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.

73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450

Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?

위에 있는 1000자리 숫자 중 곱의 크기가 가장 큰 인접한 숫자 4개는 9x9x8x9=5832이다.

1000자리 숫자 중 곱의 크기가 가장 큰 인접한 숫자 13개를 찾아라. 곱은 얼마인가?

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

문제를 해결하는 논리 구성은 어렵지 않았는데 자료형을 어떻게 처리하는 것이 좋을지 결정하는 데 많은 시간이 필요했던 문제였다. 전체를 하나의 문자열로 받아 1000자리 숫자를 각각 한 요소로 하는 리스트로 구성하기로 하고, 자료형 변환 방법을 공부하고 나서야 문제를 해결하기 시작할 수 있었다.

연속으로 숫자 13개를 곱해 가장 큰 수를 구하면 되었고, 효율을  높이기 위해 중간에 0이 나오면 넘어가도록 했다.

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

처음 6개 소수는 2, 3, 5, 7, 11, 13이고, 6번째 소수는 13이다.

10001번째 소수는 무엇인가?

소수를 판별하는 함수를 사용하고, 10001번째 소수를 구하면 된다.

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

소수를 판별하는 함수는 프로그램의 성능에 영향을 많이 주기 때문에 빨리 결과를 볼 수 있도록 속도가 빠른 것이 좋고, 10001번째 소수는 리스트의 길이로 판별하는 것보다는 카운트를 사용하는 것이 더 효과적이지만, 값을 정확히 계산하는지 확인하기 위해 리스트 형태로 처리하였다.