Blog


프로젝트 오일러 51번

  • 2013/09/20
  • Perl

두 자리 숫자 *3의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉 가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯 개는 소수입니다.

56**3 의 3번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에서는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요.
치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우 거기에 0은 올 수 없습니다.

이래저래 고생을 좀 한 문제.
자꾸 120383이 나오는데 이게 오답이여서 왜 그럴까 왜 그럴까 고심했다.

실행 소요시간은 약 10초




프로젝트 오일러 50번

  • 2013/09/18
  • Perl

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

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

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

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

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

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




프로젝트 오일러 49번

  • 2013/09/18
  • Perl

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

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

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

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

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




프로젝트 오일러 48번

  • 2013/09/18
  • Perl

11 + 22 + 33 + … + 1010 = 10405071317 입니다.

11 + 22 + 33 + … + 10001000 의 마지막 10자리 숫자는 무엇입니까?

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




프로젝트 오일러 47번

  • 2013/09/18
  • Perl

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

14 = 2 × 7
15 = 3 × 5

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

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

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

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




프로젝트 오일러 46번

  • 2013/09/18
  • Perl

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

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

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

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

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




프로젝트 오일러 45번

  • 2013/09/17
  • Perl

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

삼각수   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, …

여기서 T285 = P165 = H143 = 40755 가 됩니다.

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

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

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




프로젝트 오일러 44번

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

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

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

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

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

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




프로젝트 오일러 43번

  • 2013/09/17
  • Perl

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

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

  • d2 d3 d4 = 406 → 2로 나누어 떨어짐
  • d3 d4 d5 = 063 → 3으로 나누어 떨어짐
  • d4 d5 d6 = 635 → 5로 나누어 떨어짐
  • d5 d6 d7 = 357 → 7로 나누어 떨어짐
  • d6 d7 d8 = 572 → 11로 나누어 떨어짐
  • d7 d8 d9 = 728 → 13으로 나누어 떨어짐
  • d8 d9 d10 = 289 → 17로 나누어 떨어짐

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

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




프로젝트 오일러 42번

  • 2013/09/17
  • Perl

n번째 삼각수는 tn = ½ 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가 되는데, 이것은 우연히도 t10과 같습니다.
이렇게 어떤 단어의 단어값이 삼각수일 경우에는 이 단어를 ‘삼각단어’라 부르기로 합니다.

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

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