[Project Euler 183] 분할곱

http://projecteuler.net/index.php?section=problems&id=183

N이 양의 정수이고, N을 k 개로 똑같이 나누자. r = N/k 즉, N = r + r + ... + r 이다.

P를 이 분할의 곱이라고 한다. 즉, P = r x r x ... x r = r^k

예를 들어, 11을 다섯 개로 나누면, 11 = 2.2 + 2.2 + 2.2 + 2.2 + 2.2 이고, P는P = 2.2⁵ = 51.53632 이다.

그리고, N에 대해 M(N) = P_max , 즉 P가 갖을 수 있는 최대값으로 정의하자.

N = 11일 때에는 다섯 개로 나누었을 때, P_max = (11/4)⁴ 로 최대가 되고, 다시, M(11) = 14641/256 = 57.19140625, 으로 10진수 유한소수 값이다.

그러나, N = 8 일 경우에는 세 개로 나누었을 때 최대값을 가지며, 따라서 M(8) = 512/27 이 되고, 이 값은 10진수 무한소수이다.

D(N)이란 함수를 또 정의하는데, M(N)이 10진수 무한소수일 때, D(N) = N 이고, M(N)이 10진수 유한소수일 때, D(N) = -N 이라고 하자.

예를 들어, ΣD(N) for 5 N 100 은 2438 이다.

ΣD(N) for 5 N 10000 을 구하라.

#!/usr/bin/env python

# Project Euler 183

#
# Some min-max analysis
#
# For y = ( n/k )^k, let's find k which makes y the max.
# If we consider the real k values, we only have to find k
# which makes the derivatitive, y' is 0.
#
# y' = ?
#
# ln y = k ln(n/k) = k( ln n - ln k )
# (y' / y ) = (ln n - ln k) + k ( - 1/k) = ln n - 1 - ln k 
# = ln n/e - ln k
#
# For y can't be 0 for positive k's.
#
# ln n/e - ln k = 0
# ln n/e = ln k
# k = n/e !!!
#


import math

def P(n, k):
    r = 1.0*n/k
    return r**k

def Max_P_and_K(n):
    k = int(n/math.exp(1))
    max1 = P(n, k)
    max2 = P(n, k+1)
    if max1 > max2 :
        return max1, k
    else:
        return max2, k+1

def k_makes_the_max(n, k):
    '''
    P(n, k) >= P(n, k+1)

          k          k+1
       n |       n  |
       - |  >= -----|
       k |      k+1 |

          k+1
      k+1|         n
      ---|   >=   ---
       k |         k
    '''

    return (1.0*(k+1)/k)**(k+1) >= 1.0*n/k

def K_for_Max_P(n):
    k = int(n/math.exp(1))
    if k_makes_the_max(n, k):
        return k
    else:
        return k+1

def gcd(max, min):
    if max % min == 0:
        return min
    else:
        return gcd(min, max%min)


def M_is_nonterminating_decimal(n):
    k = K_for_Max_P(n)
    #print n, k
    k = k/ gcd(n,k)  # At 1st trial, I miss this condition, which is actaully evident.
    while k % 2 == 0 or k % 5 == 0:
        if k % 2 == 0:
            k /= 2
        if k % 5 == 0:
            k /= 5
    if k == 1:
        return False
    else:
        return True

def D(n):
    if M_is_nonterminating_decimal(n) :
        #print n, n
        return n
    else:
        #print n, -n
        return -n

sum = 0
for i in range(5, 101):
    sum += D(i)
print sum

sum = 0
for i in range(5, 10001):
    sum += D(i)
print sum