[Project Euler] 44. 합과 차도 모두 오각수인 두 오각수 차의 최소값은?

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 | 는 가장 작을 때 얼마입니까?

Click

일단 문제를 해결 하기 위해 오각수를 판단하는 함수가 일단 필요하겠네요.

x = n(3n-1)/2
2x = 3n²- n
24x = 36n²- 12n
24x + 1 = 36n²- 12n +1
24x + 1 = (6n - 1)²
√(24x + 1) = 6n - 1
√(24x + 1) + 1 = 6n
(√(24x + 1) + 1) / 6 = n

참조 : 위키백과 - Pentagonal number

즉 위의 값 n이 정수값을 가지면 해당 수 x는 오각수가 됩니다.

<script language="Javascript" type="text/javascript">
/** 오각수 판단. **/
function isPentagonal(num){
    var n = (Math.sqrt(24*num + 1)+1)/6;
    if(parseInt(n) == n)
        return true;
    else
        return false;
}
</script>

이제 남은 것은 범위를 정하는 것인데요. k>j 이고, j는 최대 k-1 이니 d값은 최소 P(k) - P(k-1) 값이고, 이 값은.. 3k - 2 가 됩니다.

p(n) - p(n-1) = (n(3n-1) - (n-1)(3(n-1)-1))/2
p(n) - p(n-1) = (3n²- n - (3n²- 7n + 4))/2
p(n) - p(n-1) = 3n - 2

즉 3k-2가 min 보다 크다면 더 이상의 k값의 증가 탐색을 할 필요가 없겠죠.
그리고 j값은 k-1부터 시작해 d값이 min보다 크면 탐색 종료, P(j)가 3*k-2보다 작으면 d값은 오각수가 아니게 되므로 마찬가지로 탐색을 종료합니다.

<script language="Javascript" type="text/javascript">
/** 오각수. **/
function pentagonal(n){
    return (3*n*n - n)/2;
}
function p044(){
    var min = 1000000000;
    
    for(var k=2; 3*k-2<min; k++){
        var pk = pentagonal(k), d = 0, s;
        for(var j=k-1; j>0; j--){
            var pj = pentagonal(j);
            d = pk - pj;
            if(d>min)
                break;
            else if(pj<3*k-2)
                break;
            else if(isPentagonal(d) && isPentagonal(pk+pj))
                min = d;
        }
    }
    alert(min);
}
</script>

돌려보면 체감상으로도 바로 값이 안나오는 것이 느껴질 정도로 연산이 꽤 오래 걸리는 편입니다.

해당 조건을 만족하는 최초의 d 값이 가장 작은 값이라는 것은 예상이 가능하고 해당 d를 구하는 것은 빠른 편인데,
해당 d값이 과연 가장 작은 값인지에 대해, 그 이상의 값을 탐색하는게 오래걸리는 편이네요.

예상대로 첫번째 d가 가장 작은 수가 맞고.. 범위를 임의로 자르거나 첫번째로 구하는 d까지만 탐색한다면 더 빠른 시간이 걸리겠지만 해당 방법은 답은 맞을지라도 문제를 제대로 푼 것은 아니겠지요.

어떻게든 범위를 줄이는 것이 관건인데 더이상의 좋은 방법은 떠오르지 않는 군요.