프로젝트 오일러 44. Pentagon numbers

중간에 뜬금없이 끼어있는 어려운 문제. 고민을 꽤 많이 했다.

물론 답을 때려맞추기는 꽤 쉽지만, 답의 정당성까지 보이기는 쉽지 않다.

 

문제는 다음과 같다.

오각수(pentagon number)는 $P_n = n(3n-1)/2$의 형태로 주어진다.

앞에서부터 1, 5, 12, 22, 35, 51...이 된다.

 

이제 오각수 한 쌍 $P_i$와 $P_j$를 찾아야 하는데, 두 오각수의 합과 차가 모두 오각수가 되어야 한다.

이를 만족하는 오각수의 쌍 중 두 수의 차이의 최솟값을 구하는 문제이다.

 

 

보통은 이렇게 푼다. 적당히 오각수를 생성해놓고(만 개 정도) pair별로 확인하며 합과 차가 둘다 오각수인지 확인한다.

이렇게 코드를 작성하면, 적당히 빠른 시간 안에 5482660이라는 답을 얻을 수 있다.

조금 더 자세히 보면, $P_{1020}= 1560090$과 $P_{2167}=7042750$의 차이는 $P_{1929}=5482660$이고, 합은 $P_{2395}=8602840$이다.

대충 인터넷을 살펴봤는데 대부분 다 이렇게 푼다.

 

하지만 이 5482660이라는 수가 과연 최소일까?

예를 들어 $P_{1000000}= 1499999500000$이고, $P_{1000001}= 1500002500001$로 둘의 차이는 3000001밖에 나지 않는데 (물론 이게 답은 아니지만) 이런 식으로 수백만 번째 오각수 중에 차이가 더 작은 답이 존재하지는 않을까?

 

 

문제를 제대로 풀기 위해 조금 다른 방법을 사용해보자. 두 오각수의 차이가 또다른 오각수가 되어야하니, 작은 오각수부터 차례대로

(i) 어떠한 두 오각수의 차이가 되는지 살펴보고

(ii) 그러한 두 오각수가 존재한다면 두 오각수의 합이 또다른 오각수가 되는지 살펴볼 것이다.

 

이를 위해서 먼저 간단히 함수 isPen()을 정의하고 가자.

임의의 자연수 n이 있을 때, n이 오각수인지 아닌지 판별할 수 있을까?

한 가지 방법으로, 위에 적힌 오각수를 생성하는 방정식 $P_n = n(3n-1)/2$를 풀어,

$x = (\sqrt{24n + 1} + 1) / 6$으로 x를 구한 뒤, x가 정수인지 확인하는 방법이 있다.

그런데 나는 정수 문제에 실수를 쓰는 것을 별로 선호하지 않는다. 다른 방법으로는 그냥 binary search를 해주면 $O(\log{n})$에 확인할 수 있다.

 

이제 (i)번, 어떤 수 n이 두 오각수의 차이가 되는지 확인하는 것이 관건이다.

관찰을 통해, 오각수의 차이는 4, 7, 10, 13, 16, ..., 4 + 3k, ...가 되는 것을 확인할 수 있다. (오각수가 2차식이므로 당연하다)

어떤 두 오각수의 차이는, 다르게 말해 저 수열의 연속되는 부분 수열의 합과 같다.

(가령 $P_1$과 $P_4$의 차이는 4 + 7 + 10이 된다)

 

이제 n이 주어졌을 때, n이 $P_{x+1} - P_x$가 될 수 있는지, $P_{x+2} - P_x$가 될 수 있는지, $P_{x+3} - P_x$가 될 수 있는지... 를 차례대로 확인할 것이다. 즉, 합이 n이 되는 해당 길이의 부분 수열이 존재하는지를 확인한다.

 

확인은 생각보다 간단한데, $P_{x+1} - P_x$가 될 수 있는지는 자명하다. n - 4가 3의 배수이면 된다.

$P_{x+2} - P_x$가 될 수 있는지는 n - 4 * 2 - 3 * (0 + 1)이 6의 배수가 되는지 확인하면 된다.

$P_{x+3} - P_x$가 될 수 있는지는 n - 4 * 3 - 3 * (0 + 1 + 2)가 9의 배수가 되는지 확인하면 된다.

이런식으로 각 길이에 대해 오각수가 그 차이가 될 수 있는지를 확인하다, 특정 길이 이상일 때 아예 불가능하게 되면 이 때 break 해주면 된다.

총 소요 시간은 $O(\sqrt{n})$정도가 소요된다.

 

이렇게 확인해가며 $P_{x+p} - P_x$가 가능한 것으로 나온다면, 위에서 정의한 isPen()함수를 이용해 두 오각수의 합 또한 오각수가 되는지 확인해주면 된다.

코드는 다음과 같다.

 

#include <iostream>
#include <cmath>
using namespace std;

bool isPen(long long t) {
  long long low = 0, high = (long long)sqrt(t) + 10;
  while (high - low != 1) {
    long long mid = (low + high) / 2;
    long long value = mid * (3 * mid - 1) / 2;
    if (value < t) low = mid;
    else high = mid;
  }
  if ((high * (3 * high - 1) / 2) == t) return 1;
  else return 0;
}

void canDif(long long n) {
  for (int len = 1; ; ++len) {
    long long m = n - 4 * len;
    m -= 3 * len * (len - 1) / 2;
    if (m < 0) break;
    if (m % (3 * len)) continue;
    else {
      long long num = m / (3 * len) + 1;
      long long low = num * (3 * num - 1) / 2;
      if (isPen(2 * low + n)) {
        cout << n << endl;
        exit(0);
      }
    }
  }
}

int main() {
  long long i = 1;
  while (1) {
    canDif(i * (3 * i - 1) / 2);
    i++;
  }
 }

총 소요시간은 차이가 $P_n$이 되는 수까지 확인하는 데에 $O(n^{2}\log{n})$이 소요된다.

 

이러한 성질을 만족하는 오각수는 유일할까?

수가 워낙 커져서 더이상 c++로는 구현하기가 버거워진다. python을 이용해 마저 계산해보자.

오랜 시간이 지난 후에 몇 가지 해를 더 찾을 수 있었다.

$P_{111972}=18806537190$과 $P_{121168}=22022465752$의 차이 $P_{46303}=3215928562$, 합 $P_{164983}=40829002942$

 

$P_{95506}=13682046301$과 $P_{110461}=18302393551$의 차이 $P_{55500}=4620347250$, 합 $P_{146024}=31984439852$

 

$P_{52430}=4123331135$과 $P_{91650}=12599537925$의 차이 $P_{75172}=8476206790$, 합 $P_{105587}=16722869060$

 

$P_{73745}=8157450665$과 $P_{129198}=25038120207$의 차이 $P_{106084}=16880669542$, 합 $P_{148763}=33195570872$

 

$P_{186517}=52182793675$과 $P_{224159}=75370773842$의 차이 $P_{124333}=23187980167$, 합 $P_{291609}=127553567517$