41은 소수이면서 다음과 같은 6개의 연속된 소수의 합으로도 나타낼 수 있습니다.

41 = 2 + 3 + 5 + 7 + 11 + 13

이것은 100 이하에서는 가장 길게 연속된 소수의 합으로 이루어진 소수입니다.

1000 이하에서는 953이 연속된 소수 21개의 합으로 가장 깁니다.

1백만 이하에서는 어떤 소수가 가장 길게 연속되는 소수의 합으로 표현될 수 있습니까?

백만 이하의 소수를 모두 구해 배열에 넣어 놓고 구하자.

1487, 4817, 8147은 3330씩 늘어나는 등차수열입니다. 이 수열에는 특이한 점이 두 가지 있습니다.

• 세 수는 모두 소수입니다.
• 세 수는 각각 다른 수의 자릿수를 바꿔서 만들 수 있는 순열(permutation)입니다.

1자리, 2자리, 3자리의 소수 중에서는 위와 같은 성질을 갖는 수열이 존재하지 않습니다. 하지만 4자리라면 위엣것 말고도 또 다른 수열이 존재합니다.

그 수열의 세 항을 이었을 때 만들어지는 12자리 숫자는 무엇입니까?

등차수열인 세 소수를 구해 순열인지 확인했다.

1¹ + 2² + 3³ + … + 10¹⁰ = 10405071317 입니다.

1¹ + 2² + 3³ + … + 1000¹⁰⁰⁰ 의 마지막 10자리 숫자는 무엇입니까?

Math::BigInt를 이용하여 구했다.
사실 마지막 10자리만 끊어서 계산해도 무방하지만, 약 10초 내로 결과가 나오기에 그냥 풀기로 했다.

서로 다른 두 개의 소인수를 갖는 수들이 처음으로 두 번 연달아 나오는 경우는 다음과 같습니다.

14 = 2 × 7
15 = 3 × 5

서로 다른 세 개의 소인수를 갖는 수들이 처음으로 세 번 연속되는 경우는 다음과 같습니다.

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19

서로 다른 네 개의 소인수를 갖는 수들이 처음으로 네 번 연속되는 경우를 찾으세요. 그 첫번째 숫자는 얼마입니까?

해쉬를 이용하여 좀 더 빠르게 구한다.

크리스티안 골드바흐는 모든 홀수인 합성수를 (소수 + 2×제곱수)로 나타낼 수 있다고 주장했습니다.

9 = 7 + 2×1²
15 = 7 + 2×2²
21 = 3 + 2×3²
25 = 7 + 2×3²
27 = 19 + 2×2²
33 = 31 + 2×1²

이 추측은 잘못되었음이 밝혀졌습니다.

위와 같은 방법으로 나타낼 수 없는 가장 작은 홀수 합성수는 얼마입니까?

우변의 2×제곱수 항을 좌변으로 넘겨, 좌변이 소수인지 확인한다.

삼각수, 오각수, 육각수는 아래 식으로 구할 수 있습니다.

삼각수		Tn = n (n + 1) / 2		1, 3, 6, 10, 15, …
오각수		Pn = n (3n − 1) / 2		1, 5, 12, 22, 35, …
육각수		Hn = n (2n − 1)		1, 6, 15, 28, 45, …

여기서 T₂₈₅ = P₁₆₅ = H₁₄₃ = 40755 가 됩니다.

오각수와 육각수도 되는, 그 다음으로 큰 삼각수를 구하세요.

이전 44번 문제를 풀었다면, n각수 판별식을 쉽게 만들 수 있다. 이를 이용하면 된다.

이 때, 변수가 정수인지 판별하는 함수가 필요한데, Scalar::Util::Numeric 모듈의 isint 함수를 사용해도 되겠지만, 정규식을 이용하여 판별하여도 성능상 크게 관계가 없다.

오각수는 P_n = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, …

위에서 P₄ + P₇ = 22 + 70 = 92 = P₈이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.

합과 차도 모두 오각수인 두 오각수 P_j, P_k 에 대해서, 그 차이 D = | P_k − P_j | 는 가장 작을 때 얼마입니까?

오각수 생성과 판별만 할줄 알면 풀수는 있지만…
정공법으로 가면 너무 오래걸린다.
가장 처음 나오는 $d값이 정답인걸 안다면 약 4초만에 문제가 해결되겠지만, 그렇지 않으면 족히 30분은 기다려야 답이 나올 것이다.

아래의 코드는 처음 나오는 값이 답이라는 것을 상정한 채 문제를 해결한 것이다.
만약 그렇지 않다면, getp 함수와 isp 함수를 캐싱하여 문제를 해결하고,
12열의 for문을 reverse하여 $p-$tp > $d 이면 last하여 쓸데없는 반복을 줄임으로서 시간을 좀 더 단축시킬 수 있겠다.

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.

d₁을 첫째 자리수, d₂를 둘째 자리수…라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

• d₂ d₃ d₄ = 406 → 2로 나누어 떨어짐
• d₃ d₄ d₅ = 063 → 3으로 나누어 떨어짐
• d₄ d₅ d₆ = 635 → 5로 나누어 떨어짐
• d₅ d₆ d₇ = 357 → 7로 나누어 떨어짐
• d₆ d₇ d₈ = 572 → 11로 나누어 떨어짐
• d₇ d₈ d₉ = 728 → 13으로 나누어 떨어짐
• d₈ d₉ d₁₀ = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?

그냥 문제에서 준 그대로 짜봤다.
마음속으로 둔 제한시간이 1분인데, 약 30초만에 끝났기 때문에 최적화는 하지 않았다.
만약 최적화를 한다면, 직접 나누지 않고 규칙(2의 배수는 끝자리만 확인하면 된다던가)을 이용해서 풀거나, 미리 세자리 수까지 나눗셈 사전을 만들어 놓는다거나 할 수 있겠다.

n번째 삼각수는 t_n = ½ n (n + 1) 이라는 식으로 구할 수 있는데, 처음 10개는 아래와 같습니다.

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

어떤 영어 단어에 대해서, 각 철자의 알파벳 순서(A=1, B=2, …, Z=26)를 모두 더한 값을 ‘단어값’이라 부르기로 합니다. 예를 들어 ‘SKY’의 단어값은 19 + 11 + 25 = 55가 되는데, 이것은 우연히도 t₁₀과 같습니다.
이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 ‘삼각단어’라 부르기로 합니다.

약 16KB의 텍스트 파일 words.txt에는 2000개 정도의 영어 단어가 수록되어 있습니다. 이 중에서 삼각단어는 모두 몇 개입니까?

해쉬를 이용하여 키에 단어값을, 해쉬값에 그 단어값을 가지는 단어들의 총 갯수를 저장하여, 삼각수인 단어값을 키로 가지는 해쉬값끼리 더한다!

1부터 n까지의 숫자를 하나씩만 써서 만든 n자리 숫자를 팬디지털(pandigital)이라고 부릅니다.
2143은 4자리 팬디지털인데, 이 수는 동시에 소수이기도 합니다.

n자리 팬디지털 소수 중에서 가장 큰 수는 무엇입니까?

1~9까지 합이 45이고, 1~8까지 합이 36이다. 이들의 합은 모두 3의 배수이고, 각 자릿수의 합이 3의 배수이면, 3의 배수이므로 9자리 팬디지털과 8자리 팬디지털은 3의 배수가 된다.
따라서 7자리 팬디지털 까지만 체크하면 된다.
중복없이 팬디지털을 생성하기 위해 Math::Permute::Array 모듈을 사용했다.