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

오각수는 P_n = n (3n − 1)/2 라는 공식으로 구할 수 있고, 처음 10개의 오각수는 다음과 같습니다.

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

위에서 P₄ + P₇ = 22 + 70 = 92 = P₈이 됨을 볼 수 있습니다. 하지만 두 값의 차인 70 − 22 = 48 은 오각수가 아닙니다.

합과 차도 모두 오각수인 두 오각수 P_j, P_k 에 대해서, 그 차이 D = | P_k − P_j | 는 가장 작을 때 얼마입니까?


위키피디아에 오각수를 찾아보면 오각수를 판별하는 공식이 있다.

어떤 수 n에 대해서 x= sqrt(24*n + 1) + 1 / 6에 나오는 x에 대해
x == int(x)를 만족하면 n은 오각수이다.

이것으로 오각수를 판별하고, 차가 가장 작으려면 제일 근접한 두 오각수이어야 하므로
pent_list에 오각수를 하나씩 생성해나가면서 합과 차가 모두 오각수인 것을 찾는다.
가장 먼저 찾아지는 것이 가장 작은 차.


 

Python

	import math
	def is_pentagonal(n):
	n = abs(n)
	p = ( math.sqrt(1 + 24*n) + 1 ) / 6
	return p==int(p)
	pent_list = [1]
	i = 0
	not_found = True
	while not_found:
	i+=1
	pent_list.append(int(i * (3*i - 1)/2))
	for j in range(2, len(pent_list) - 1):
	if is_pentagonal(pent_list[i] - pent_list[j]) and is_pentagonal(pent_list[i] + pent_list[j]):
	print (pent_list[i] - pent_list[j])
	not_found = False
	break

view raw 44.py hosted with ❤ by GitHub

Ruby

	def is_pentagonal(n)
	n = n.abs
	p = (Math.sqrt(1 + 24*n) + 1) / 6
	return p == p.to_i
	end
	pent_list = [1]
	i = 0
	not_found = true
	while (not_found)
	i+=1
	pent_list.push((i * (3*i - 1)/2).to_i)
	(2..pent_list.length - 1).each do |j|
	if is_pentagonal(pent_list[i] - pent_list[j]) and is_pentagonal(pent_list[i] + pent_list[j])
	puts pent_list[i] - pent_list[j]
	not_found = false
	break
	end
	end
	end

view raw 44.rb hosted with ❤ by GitHub

Perl

	use strict;
	use warnings;
	use Math::Complex;
	sub is_pentagonal {
	my ($n) = @_;
	$n = abs $n;
	my $p = (sqrt(1 + 24 *$n) + 1) / 6;
	return $p == int $p;
	}
	my @pent_list=qw (1);
	my $i = 0;
	my $not_found = 1;
	while ($not_found) {
	$i += 1;
	my $penta_n = $i * (3*$i - 1) / 2;
	push @pent_list, $penta_n;
	foreach my $j ((2..$#pent_list - 1)) {
	if (&is_pentagonal($pent_list[$i] - $pent_list[$j]) and
	&is_pentagonal($pent_list[$i] + $pent_list[$j])) {
	print scalar($pent_list[$i] - $pent_list[$j]);
	$not_found = 0;
	last;
	}
	}
	}

view raw 44.pl hosted with ❤ by GitHub