오각수는 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 모듈을 사용했다.

소수점 뒤에 양의 정수를 차례대로 붙여 나가면 아래와 같은 무리수를 만들 수 있습니다.

0.123456789101112131415161718192021…

이 무리수의 소수점 아래 12번째 자리에는 1이 옵니다 (위에서 붉게 표시된 숫자).

소수점 아래 n번째 숫자를 d_n이라고 했을 때, 아래 식의 값은 얼마입니까?

d₁ × d₁₀ × d₁₀₀ × d₁₀₀₀ × d₁₀₀₀₀ × d₁₀₀₀₀₀ × d_1000000

perl의 주특기인 문자열 처리!

세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}

1000 이하의 둘레 p에 대해서, 직각삼각형이 가장 많이 만들어지는 p의 값은 얼마입니까?

30초가 넘게 걸린다.
식을 좀 예쁘게 정리하면 좀 빠르게 구할 수 있겠다.

숫자 192에 1, 2, 3을 각각 곱합니다.

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 ‘곱해서 이어붙이기’라고 부르기로 합니다.

같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다.

어떤 정수와 (1, 2, … , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1)

소수 3797에는 왼쪽부터 자리수를 하나씩 없애거나 (3797, 797, 97, 7) 오른쪽부터 없애도 (3797, 379, 37, 3) 모두 소수가 되는 성질이 있습니다.
이런 성질을 가진 소수는 단 11개만이 존재합니다. 이것을 모두 찾아서 합을 구하세요.
(참고: 2, 3, 5, 7은 제외합니다)

그냥 하자.
안느리다.

대칭수(palindrome)인 585는 2진수로 나타내도 1001001001₂가 되어 여전히 대칭수입니다.
10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요.
(주의: 첫번째 자리가 0이면 대칭수가 아님)

sprintf를 이용해 2진수로 변환한다.

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다.

이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다.

그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?

뭐 별 수 있겠는가? 그냥 짜야지…
역시 소수를 가져오는데는 모듈을 사용했다.