파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 32번 - pandigital product

1부터 n까지 연속된 정수를 한번씩만 사용해서, n자리 수를 만들면, 그수는 pandigital 이라고 합니다. 예를 들면 15234 는 5의 pandigital 입니다.

문제는 39 x 186 = 7254 처럼 AxB=C 를 만족하면서 세수 A,B,C의 자릿수들을 모두 이으면 1부터 9까지의 9자리 pandigital 이 되는 C를 모두 찾아서 합을 구하는 것입니다.

Pandigital products

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once; for example, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

 

여러가지 방법이 있겠지만, 일단 9자리 pandigital 수를 제일 작은 "123456789" 부터 시작해서, 제일 큰 "987654321" 까자 순차적으로 만들면서, 예시의 성질을 만족하는 수가 있는지를 검사하도록 하겠습니다.

먼저 pandigital 수를 만드는 함수입니다. pandigital 을 만드는 함수는 24번 문제의 순열을 만드는 함수와 동일합니다.

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1
test = '123456789'
print(get_next_permutation(test))
123456798

"123456789" 숫자를 함수에 넣으면, 그다음 pandigital(또는 순열, permutation) 인 "123456798" 이 출력됩니다. 함수의 자세한 설명은 24번 문제를 참조해주세요. 

 

그다음으로 9자리 숫자를 세부분으로 나누어서 문제에 제시된 성질(세부분의 곱셈)을 체크하는 부분입니다.

test='123456789'
for i in range(1,9):
    str1=test[0:i]
    for j in range(i+1,9):
        str2=test[i:j]
        str3=test[j:9]
        print(str1,str2,str3,int(str1)*int(str2)==int(str3))
1 2 3456789 False
1 23 456789 False
1 234 56789 False
1 2345 6789 False
1 23456 789 False
1 234567 89 False
1 2345678 9 False
12 3 456789 False
12 34 56789 False
12 345 6789 False
12 3456 789 False
12 34567 89 False
12 345678 9 False
123 4 56789 False
123 45 6789 False
123 456 789 False
123 4567 89 False
123 45678 9 False
1234 5 6789 False
1234 56 789 False
1234 567 89 False
1234 5678 9 False
12345 6 789 False
12345 67 89 False
12345 678 9 False
123456 7 89 False
123456 78 9 False
1234567 8 9 False

위 계산이 하나의 pandigital에 대한 체크이고, 그다음 pandigital 수에 대해서 같은 과정을 되풀이 하면 됩니다.

성질을 만족할때(True)일때의 결과값C는 list 에 저장을 해서 마지막에 합계를 내도록 하겠습니다.

def get_next_permutation(string):
    i=len(string)-2
    while i >= 0:
        if string[i] < string[i+1]:
            target = sorted(string[i:])
            new_num = target.pop(target.index(string[i])+1)
            last_nums = ''.join(target)
            return string[:i] + new_num + last_nums
        i-=1

test = "123456789"
m=len(test)
total = []
while not test == None:
    for i in range(1,m):
        str1=test[0:i]
        for j in range(i+1,m):
            str2=test[i:j]
            str3=test[j:m]
            if int(str1)*int(str2)==int(str3):
                print(str1,str2,str3)
                total.append(int(str3))
    test = get_next_permutation(test)
print(total)
12 483 5796
138 42 5796
157 28 4396
159 48 7632
1738 4 6952
18 297 5346
186 39 7254
1963 4 7852
198 27 5346
27 198 5346
28 157 4396
297 18 5346
39 186 7254
4 1738 6952
4 1963 7852
42 138 5796
48 159 7632
483 12 5796
[5796, 5796, 4396, 7632, 6952, 5346, 7254, 7852, 5346, 5346, 4396, 5346, 7254, 6952, 7852, 5796, 7632, 5796]

 

마지막으로 결과가 저장된 리스트에서 중복을 제외하고 합산을 하면 됩니다.

print(total)
print(sum([x for i,x in enumerate(total) if total[:i].count(x)==1]))
[4396, 4396, 5346, 5346, 5346, 5346, 5796, 5796, 5796, 5796, 6952, 6952, 7254, 7254, 7632, 7632, 7852, 7852]
45228

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기