분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.
1/2= 0.5
1/3= 0.(3)
1/4= 0.25
1/5= 0.2
1/6= 0.1(6)
1/7= 0.(142857)
1/8= 0.125
1/9= 0.(1)
1/10= 0.1소괄호는 순환마디를 나타내는데, 1/6의 경우 순환마디는 “6”으로 0.166666…처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.
d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?
Carmichael function을 이용했다.
소요시간은 약 10초.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#!/usr/bin/env perl use 5.010; use strict; use warnings; use bigint; use Math::Prime::Util ':all'; my $c = 0; my $r = 0; for (1..1000) { $_ /= 2 while ($_ % 2 == 0); $_ /= 5 while ($_ % 5 == 0); for my $i (1..$_-1) { if (10**$i % $_ == 1) { if ($i > $c) { $c = $i; $r = $_; } last; } } } say $r; |