29 lines
712 B
Perl
29 lines
712 B
Perl
use warnings;
|
|
use strict;
|
|
use Math::BigRat;
|
|
use ntheory qw/euler_phi vecsum/;
|
|
|
|
sub farey {
|
|
my $N = shift;
|
|
my @f;
|
|
my($m0,$n0, $m1,$n1) = (0, 1, 1, $N);
|
|
push @f, Math::BigRat->new("$m0/$n0");
|
|
push @f, Math::BigRat->new("$m1/$n1");
|
|
while ($f[-1] < 1) {
|
|
my $m = int( ($n0 + $N) / $n1) * $m1 - $m0;
|
|
my $n = int( ($n0 + $N) / $n1) * $n1 - $n0;
|
|
($m0,$n0, $m1,$n1) = ($m1,$n1, $m,$n);
|
|
push @f, Math::BigRat->new("$m/$n");
|
|
}
|
|
@f;
|
|
}
|
|
sub farey_count { 1 + vecsum(euler_phi(1, shift)); }
|
|
|
|
for (1 .. 11) {
|
|
my @f = map { join "/", $_->parts } # Force 0/1 and 1/1
|
|
farey($_);
|
|
print "F$_: [@f]\n";
|
|
}
|
|
for (1 .. 10, 100000) {
|
|
print "F${_}00: ", farey_count(100*$_), " members\n";
|
|
}
|