파이썬 자리수곱의합

문제

P(n)은 n을 십진수로 표시했을 때 0이 아닌 각 자리수의 곱으로 정의한다.

다음 값을 구하라.

  P(1) + P(2) + P(3) + ... + P(999999)

---

우선 무식한 방법

#!/usr/bin/python
##########################################################
# ZiffernProdukte
# ---------------------------------------------------------
# <45fe9e97$0$11610$3b214f66@aconews.univie.ac.at>
# ---------------------------------------------------------
# Mit P(n) bezeichnen wir das Produkt aller Ziffern
# 1,2,3,4,5,6,7,8,9 in der Dezimaldarstellung der Zahl n
# (die Ziffer 0 wird also nicht mitmultipliziert).
#
# Bestimme den Wert der Summe
#
#   P(1) + P(2) + P(3) + ... + P(999999)
##########################################################


def ziffprod(n):
    ret = 1
    while n > 0:
        z = n % 10
        if z != 0:
            ret = ret * z
        n = n // 10
    return ret


# -- main --
sum = 0
S_prev = 0

for i in range(1, 1000000):
    sum = sum + ziffprod(i)
    if i in (9, 99, 999, 9999, 99999, 999999, 9999999, 99999999):
        print(i, sum)
        print(46 * ( S_prev + 1) - 1)
        S_prev = sum
print(i, sum)

그리고, 조금 생각하여 만든 점화식을 만들어 봤다.

Sn을 P(1)부터 P(10^n - 1)까지의 합이라고 정의해보면, 즉

 S1 = P(1) + ... + P(9)
 S2 = P(1) + ... + P(99)
 S3 = P(1) + ... + P(999)
 S4 = P(1) + ... + P(9999)
 S5 = P(1) + ... + P(99999)
 S6 = P(1) + ... + P(999999)

S1은 쉽다.

 S1 = 1 + 2 + 3 + ... + 8 + 9 = 45

S2는 좀 복잡해 보인다. 그러나, 쭉 풀어서 써  놓아보면 패턴이 보인다.

 S2 =
                 1 +     2 +     3 + ... +     8 +     9 + //  1 ~  9  
         1 + 1 x 1 + 1 x 2 + 1 x 3 + ... + 1 x 8 + 1 x 9 + // 10 ~ 19  
         2 + 2 x 1 + 2 x 2 + 2 x 3 + ... + 2 x 8 + 2 x 9 + // 20 ~ 29  
         3 + 3 x 1 + 3 x 2 + 3 x 3 + ... + 3 x 8 + 3 x 9 +
                       ...
         9 + 9 x 1 + 9 x 2 + 9 x 3 + ... + 9 x 8 + 9 x 9   // 90 ~ 99  

    =                  S1 + //  1 ~  9
              1 +  1 x S1 + // 10 ~ 19 
              2 +  2 x S1 + // 20 ~ 29  
              3 +  3 x S1 +
                  ...
              9 +  9 x S1   // 90 ~ 99   
              
    =  S1 +  S1 + S1 x S1

다음번 수열과의 관계식을 잡아내기에는 아직 좀 부족하므로, S3를 살펴본다.

 S3 =
             1 +     2 +     3 + ... +     98 +     99 + //   1 ~  99 
     1 + 1 x 1 + 1 x 2 + 1 x 3 + ... + 1 x 98 + 1 x 99 + // 101 ~ 199
     2 + 2 x 1 + 2 x 2 + 2 x 3 + ... + 2 x 98 + 2 x 99 + // 201 ~ 299               
                                 ...  
     9 + 9 x 1 + 9 x 2 + 9 x 3 + ... + 9 x 98 + 9 x 99 + // 901 ~ 999
     
    =       S2 +  S1 + S1 x S2     
    = S1 x S2 + S1 + S2 
    = (S1+1)(S2+1) - 1

이렇게 까지 해보면 점화식이 아래와 같을 거라고 확신이 든다.

 Si = (S1 + 1)(S(i-1) + 1) - 1

그리고 코드.

#!/usr/bin/python
##########################################################
# ZiffernProdukte
# ---------------------------------------------------------
# <45fe9e97$0$11610$3b214f66@aconews.univie.ac.at>
# ---------------------------------------------------------
# Mit P(n) bezeichnen wir das Produkt aller Ziffern
# 1,2,3,4,5,6,7,8,9 in der Dezimaldarstellung der Zahl n
# (die Ziffer 0 wird also nicht mitmultipliziert).
#
# Bestimme den Wert der Summe #  #   P(1) + P(2) + P(3) + ... + P(999999)
##########################################################


# s1 = P(1) + ... + P(9)
s1 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9


# s[i] = P(1) + ... + P(10  -1)
s = []
for i in range(7):
    s.append(-1)  # initialize array with absurd value

s[0] = 0  # When i = 0, 10^i - 1 = 0, 0 is legitimate
s[1] = s1
for i in range(2, 7):
    s[i] = (s[1] + 1) * (s[i - 1] + 1) - 1
    
print(s)