Farey sequence: Difference between revisions
Content deleted Content added
m →{{header|REXX}}: simplified computational formula, changed some comments and added whitespace. |
Add Perl |
||
Line 555:
%1 = [3045, 12233, 27399, 48679, 76117, 109501, 149019, 194751, 246327, 304193]</pre>
=={{header|Perl}}==
=== Recurrence ===
This uses the recurrence from Concrete Mathematics exercise 4.61 to create them quickly (this is also on the Wikipedia page). It also uses the totient sum to quickly get the counts.
<lang 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";
}</lang>
{{out}}
<pre>
F1: [0/1 1/1]
F2: [0/1 1/2 1/1]
F3: [0/1 1/3 1/2 2/3 1/1]
F4: [0/1 1/4 1/3 1/2 2/3 3/4 1/1]
F5: [0/1 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 1/1]
F6: [0/1 1/6 1/5 1/4 1/3 2/5 1/2 3/5 2/3 3/4 4/5 5/6 1/1]
F7: [0/1 1/7 1/6 1/5 1/4 2/7 1/3 2/5 3/7 1/2 4/7 3/5 2/3 5/7 3/4 4/5 5/6 6/7 1/1]
F8: [0/1 1/8 1/7 1/6 1/5 1/4 2/7 1/3 3/8 2/5 3/7 1/2 4/7 3/5 5/8 2/3 5/7 3/4 4/5 5/6 6/7 7/8 1/1]
F9: [0/1 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 1/1]
F10: [0/1 1/10 1/9 1/8 1/7 1/6 1/5 2/9 1/4 2/7 3/10 1/3 3/8 2/5 3/7 4/9 1/2 5/9 4/7 3/5 5/8 2/3 7/10 5/7 3/4 7/9 4/5 5/6 6/7 7/8 8/9 9/10 1/1]
F11: [0/1 1/11 1/10 1/9 1/8 1/7 1/6 2/11 1/5 2/9 1/4 3/11 2/7 3/10 1/3 4/11 3/8 2/5 3/7 4/9 5/11 1/2 6/11 5/9 4/7 3/5 5/8 7/11 2/3 7/10 5/7 8/11 3/4 7/9 4/5 9/11 5/6 6/7 7/8 8/9 9/10 10/11 1/1]
F100: 3045 members
F200: 12233 members
F300: 27399 members
F400: 48679 members
F500: 76117 members
F600: 109501 members
F700: 149019 members
F800: 194751 members
F900: 246327 members
F1000: 304193 members
F10000000: 30396356427243 members
</pre>
=== Mapped Rationals ===
Similar to Pari and Perl6. Same output, quite slow. Using the recursive formula for the count, utilizing the Memoize module, would be a big help.
<lang perl>use warnings;
use strict;
use Math::BigRat;
sub farey {
my $n = shift;
my %v;
for my $k (1 .. $n) {
for my $i (0 .. $k) {
$v{ Math::BigRat->new("$i/$k")->bstr }++;
}
}
my @f = sort {$a <=> $b }
map { Math::BigRat->new($_) }
keys %v;
@f;
}
for (1 .. 11) {
my @f = map { join "/", $_->parts } # Force 0/1 and 1/1
farey($_);
print "F$_: [@f]\n";
}
for (1 .. 10) {
my @f = farey(100*$_);
print "F${_}00: ", scalar(@f), " members\n";
}</lang>
=={{header|Perl 6}}==
| |||