[오일러프로젝트] 43번문제

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다.

d₁을 첫째 자리수, d₂를 둘째 자리수...라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

• d₂ d₃ d₄ = 406 → 2로 나누어 떨어짐
• d₃ d₄ d₅ = 063 → 3으로 나누어 떨어짐
• d₄ d₅ d₆ = 635 → 5로 나누어 떨어짐
• d₅ d₆ d₇ = 357 → 7로 나누어 떨어짐
• d₆ d₇ d₈ = 572 → 11로 나누어 떨어짐
• d₇ d₈ d₉ = 728 → 13으로 나누어 떨어짐
• d₈ d₉ d₁₀ = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?


팬디지털 생성만 알면 그 다음은 그냥 평이한문제..
순열을 사용해 10자리 팬디지털을 생성 후 조건에 맞는 것을 찾음


 

Python

	#Pandigital 생성
	import itertools
	p=list()
	permutations=list(itertools.permutations(list(range(0,10)),10))
	for t in permutations:
	s="".join(str(n) for n in t)
	p.append(s)
	sum_of_result = 0
	rule = {1:2, 2:3, 3:5, 4:7, 5:11, 6:13, 7:17}
	for pandigital in p:
	isRight = True
	for k in rule.keys():
	if not int(pandigital[k:k+3]) % rule[k] == 0:
	isRight = False
	break
	if isRight:
	sum_of_result += int(pandigital)
	print (sum_of_result)

view raw 43.py hosted with ❤ by GitHub

Ruby

	p = "0123456789".split("").permutation.to_a
	sum_of_result = 0
	rule = {"1"=>2, "2"=>3, "3"=>5, "4"=>7, "5"=>11, "6"=>13, "7"=>17}
	p.each do |pandigital|
	s=pandigital.join("")
	isRight = true
	rule.each do |k, v|
	#puts "#{k}, #{v}, #{s}, #{s[k.to_i, 3]}"
	if not s[k.to_i, 3].to_i % v == 0
	isRight = false
	break
	end
	end
	if isRight
	sum_of_result += s.to_i
	end
	end
	puts sum_of_result

view raw 43.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	use List::Permutor;
	my $perm = new List::Permutor qw /0 1 2 3 4 5 6 7 8 9/;
	my %rule = (1=>2, 2=>3, 3=>5, 4=>7, 5=>11, 6=>13, 7=>17);
	my $sum_of_result = 0;
	while (my @p = $perm->next) {
	my $s = join "", @p;
	my $is_right = 1;
	foreach my $k (keys %rule) {
	unless ((substr $s, $k, 3) % $rule{$k} == 0) {
	$is_right = 0;
	last;
	}
	}
	if ($is_right) {
	$sum_of_result += $s;
	}
	}
	print "$sum_of_result";

view raw 43.pl hosted with ❤ by GitHub