콘텐츠로 건너뛰기
Home » project euler » Page 3

project euler

오일러 프로젝트 65

제곱근 2는 아래와 같이 연분수의 꼴로 나타낼 수 있습니다.

연분수에서 이렇게 끝없이 반복되는 부분은 √2 = [1;(2)]처럼 나타낼 수 있는데, 여기서 (2)는 숫자 2가 반복됨을 뜻합니다. 같은 방법으로 √23은 [4;(1,3,1,8)]이 됩니다. 이 연분수의 부분 합을 구하면, 해당 제곱근의 훌륭한 근사값으로 쓸 수 있습니다.. √2의 수렴 과정을 한 번 보겠습니다.

이런 식으로 처음 10번에 해당하는 값은 다음과 같이 됩니다.

정말 놀라운 사실은 가장 중요한 수학 상수 중 하나인 e가 다음과 같은 연분수 꼴로 나타내어진다는 것입니다.

e = [2;1,2,1,1,4,1,1,6,1,…, 1,2k,1…]

이 경우 수렴 과정의 처음 10번은 이렇습니다.

여기서 열 번째 값의 분자 자릿수를 모두 더하면 1+4+5+7 = 17이 되는 것을 알 수 있습니다. 그러면 e의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면 얼마가 됩니까?

더 보기 »오일러 프로젝트 65

오일러 프로젝트 64

제곱근을 연분수로 나타날 때 반복 주기가 홀수인 경우 세기

모든 제곱근은 아래와 같이 연분수로 나타낼 수 있는데, 이 때 반복되는 부분이 나타납니다.

\sqrt{N} = a_0 + \frac{1}{ a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}

예를 들어서 √23을 풀어 보면,

\sqrt{23} = 4 + (\sqrt{23} - 4) = 4 + \frac{1}{(\frac{1}{\sqrt{23} - 4})} = 4 + \frac{1}{\frac{\sqrt{23} + 4}{7}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}

같은 식으로 계속하면 아래와 같은 모양이 됩니다.

\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \cdots}}}}

이 과정을 상세히보면 다음과 같습니다.

\begin{array}{llll}
a_0 = 4, & \frac{1}{\sqrt{23} - 4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\
a_1 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\
a_2 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\
a_3 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\
a_4 = 8, & \frac{1}{\sqrt{23} - 4} = \frac{2(\sqrt{23} + 4)}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\
a_5 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\
a_6 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\
a_7 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\
\end{array}

위에서 보듯이 4라는 정수부 다음에 1, 3, 1, 8 이라는 숫자가 무한히 반복되는데, 이것을 을 √23 = [4;(1,3,1,8)] 과 같이 표시하기로 합니다. 이런식으로 해서 무리수인 제곱근들을 연분수로 나타내면 다음과 같이 됩니다.

√2=[1;(2)], 주기=1
√3=[1;(1,2)], 주기=2
√5=[2;(4)], 주기=1
√6=[2;(2,4)], 주기=2
√7=[2;(1,1,1,4)], 주기=4
√8=[2;(1,4)], 주기=2
√10=[3;(6)], 주기=1
√11=[3;(3,6)], 주기=2
√12=[3;(2,6)], 주기=2
√13=[3;(1,1,1,1,6)], 주기=5

반복주기가 홀수인 경우는 N ≤ 13 일 때 모든 4번 있음을 볼 수 있습니다. 그러면 N ≤ 10000 일 때 반복 주기가 홀수인 경우는 모두 몇 번이나 있습니까?

https://euler.synap.co.kr/problem=64
더 보기 »오일러 프로젝트 64

오일러 프로젝트 62

세제곱수인 41063625(=3453)로 순열을 만들어 보면 그 중에서 56623104(=3843)와 66430125(=4053)가 또 세제곱수입니다. 실제 41063625는, 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.

그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?

https://euler.synap.co.kr/problem=62
더 보기 »오일러 프로젝트 62

오일러 프로젝트 61

삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.

  • 삼각수 – P3n = n * ( n + 1) / 2 >> 1, 3, 5, 10, 15, …
  • 사각수 – P4n = n * n >> 1, 4, 9, 16, 25, …
  • 오각수 – P5n = (n * ( n * 3 – 1)) / 2 > 1, 5, 12, 22, 35, …
  • 육각수 – P6n = (n * (n * 2 – 1)) > 1, 6, 15, 28, 45, …
  • 칠각수 – P7n = ((n * (n * 5 – 3)) / 2 > 1, 7, 18, 34, 55, …
  • 팔각수 – P8n = n * (n * 3 – 2) > 1, 8, 21, 40, 65, …

그런데 4자리 숫자 8128, 2882, 8281 (순서대로 각각 3, 5, 4각수)에는 재미있는 성질이 있습니다. 먼저 각 숫자들은 두 자리씩 꼬리를 물고 진행합니다. 그리고 각 숫자들은 모두 서로 다른 다각수입니다. 이런 성질을 갖는 네자리 숫자 세 개는 이들이 유일합니다. 이렇게 순환하면서 서로 다른 다각수가 되는 4자리 숫자 여섯개의 유일한 순서쌍을 찾고 그 합을 구하세요.

더 보기 »오일러 프로젝트 61

오일러 프로젝트 60

네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.

더 보기 »오일러 프로젝트 60

오일러 프로젝트 59

컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다. 예를 들면 대문자 A는 65, 별표(‘*’)는 42, 소문자 k는 107이라는 값을 가집니다.

현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고 각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다. 이 방법의 장점은 암호화와 복호와에 동일한 키를 사용할 수 있다는 것입니다. 예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65가 됩니다. 암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다. 암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 2개를 함께 확보하지 않는 한 해독은 불가능합니다.

하지만 이 방법은 대부분의 경우 실용적이지 못하므로, 원문보다 짧은 비밀키를 사용하게 됩니다. 이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다. 이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만 또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.

이번 문제를 위해서 준비한 암호화 키는 단 3개의 영어 소문자이고, cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다. 원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고, 원문에 포함된 ASCII 코드값의 총합을 구하세요.

http://euler.synap.co.kr/prob_detail.php?id=59
더 보기 »오일러 프로젝트 59

오일러 프로젝트 58

숫자를 1부터 시작해서 하나씩 늘려나가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다. 우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 점입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다. 이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.

http://euler.synap.co.kr/prob_detail.php?id=58
더 보기 »오일러 프로젝트 58

오일러 프로젝트 56

구골(googol)은 10100을 일컫는 말로, 1뒤에 0이 백개나 붙는 어마어마한 수입니다. 100100은 1뒤에 0이 2백개나 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자리수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다. a, b가 100보다 작은 자연수일 때, ab에 대해서, 자릿수의 합이 최대인 경우, 그 값은 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=55
더 보기 »오일러 프로젝트 56

오일러 프로젝트 55

47이란 숫자를 골라서 뒤집은 다음 다시 원래 수에 더하면 47 + 74 = 121과 같이 대칭수(palidrome)가 됩니다. 물론 모든 숫자가 이토록 쉽게 대칭수를 만들어내지는 않습니다. 예를 들어 349의 경우에는

  • 349 + 943 = 1292
  • 1292 + 2912 = 4213
  • 4213 + 3124 = 7337

위에서 보는 것처럼 3번의 반복과정을 거쳐야 대칭수가 됩니다. 196과 같은 몇몇 숫자들은 이와 같은 과정을 아무리 반복해도 대칭수가 되지 않을 것이라고 추측되는데, 이런 수를 라이크렐 수라고 부릅니다. 아직 증명되지는 않았지만, 문제 풀이를 위해서 일단 라이크렐 수가 존재한다고 가정을 하겠습니다.

또한 1만 이하의 숫자들은 50번 미만의 반복으로 대칭수가 되든지 라이크렐 수이든지 둘 중 하나라고 합니다. 1만을 넘어서면 10677에 이르렀을 때 비로소 53번의 반복으로 4668731596684224866951378664라는 28자리의 대칭수가 만들어집니다.

그러면 1만 이하에는 몇 개의 라이크렐 수가 존재합니까?

http://euler.synap.co.kr/prob_detail.php?id=55
더 보기 »오일러 프로젝트 55

오일러 프로젝트 54

포커라는 카드 게임은 다섯 장으로 된 패의 높고 낮음에 따라 승부를 냅니다. (포커 규칙을 이미 아는 분이라면 규칙 설명 부분은 건너 뛰셔도 좋습니다.) 카드 한 장은 아래와 같은 순서대로 값이 높아집니다.

2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A

다섯장으로 이루어진 패의 계급은 낮은 것부터 높은 순서로 다음과 같습니다.

  • High Card : 가장 높은 카드의 값 비교
  • One Pair : 한 쌍이 같은 카드
  • Two Pairs: 서로 다른 두 쌍이 같은 카드
  • Three of a Kind: 세 장이 같은 카드
  • Straight : 모든 카드가 연속된 숫자 (Q, K, A, 2, 3 은 스트레이트가 아닙니다)
  • Flush : 모든 카드의 무늬가 같음
  • Full House : 세장이 같고, 또 한쌍이 같음
  • Four of a Kind : 네 장이 같은 카드
  • Royal Flush : 10, J, Q, K, A 가 무늬도 같음 (Royal Straight Flush가 아니냐고 하겠지만, Royal Straight라는 것은 없습니다.)

두 사람의 패가 같은 종류의 계급이라면, 계급을 구성하는 카드 중 높은 쪽을 쥔 사람이 이깁니다. 예를 들면 8 원페어는 5 원페어를 이깁니다. (풀하우스의 경우 Three of a Kind의 숫자를 먼저 비교하고, 원 페어의 숫자를 다시 비교) 계급을 이루는 카드 숫자까지 같으면 (둘 다 Q 원페어인 경우 등) 다른 카드를 높은 순서대로 비교해서 승부를 정합니다.

텍스트 파일 poker.txt에는 두 선수가 벌인 1,000회의 승부가 저장되어 있습니다. 한 줄에는 10장의 카드가 공백으로 분리되어 있는데, 앞의 다섯장은 1번 선수의 것이고 뒤의 다섯장은 2번 선수의 패입니다. 잘못되거나 중복된 데이터는 없으며, 무승부도 없습니다.

카드 숫자는 2, 3, …, 9, T, J, Q, K, A 로(숫자 10은 T로 표시), 무늬는 C, D, H, S로 표시되어 있습니다. 예를 들면 3C 3D 3S 9S 9D의 경우 3 풀하우스가 됩니다.

이 데이터를 분석하고 1번 선수가 이긴 횟수를 구하세요.

https://euler.synap.co.kr?problem=54
더 보기 »오일러 프로젝트 54