I’ve been doing the Weekly
Challenges. The
latest
involved generating more sequences. (Note that this is open until 10
April 2022.)
Task 1: Farey Sequence
You are given a positive number, $n
.
Write a script to compute Farey Sequence of the order $n
.
In other words, all the fractions from 0 to 1 with integral numerators
and denominators up to $n
, in increasing order of value, in reduced
forms (so you list 1/2 but not 2/4).
Of course some people might use floating point numbers for this. But
floating point is bad and wrong. So instead I work out the LCM for the
series of denominators (2 up to n), using the code from #155, then
store each fraction as a pair of numbers, keyed by (value × lcm),
which will always be an integer.
In JavaScript:
function farey (n) {
Calculate the lcm, just once.
let l=lcmseries(2,n)
Initialise the hash that'll hold the fractions, and the array that'll
hold the keys for later sorting.
let d=new Map()
let s=[]
Iterate denominators from 1 to n.
for (let i=1;i <= n;i++) {
Calculate the multiplier value for this denominator.
let m=l/i
Iterate numerators from 0 to denominator.
for (let j=0;j <= i;j++) {
The value of this fraction, multiplied by the lcm.
let k=m*j
If we haven't already seen this value, stick it in the hash, as a
two-element array. (This takes care of the reduced forms; if n=4, 2/4
produces a k value of 2, but we already got a 2 for 1/2.) Also push
the key value onto its list.
if (!d.has(k)) {
d.set(k,[j,i])
s.push(k)
}
}
}
Sort the key list. (Some languages, like this one, prefer to sort in
place; for others I don't need a separate key list, and I just sort
the keys of the hash and output in that order.)
s.sort(function(a,b) {
return a-b;
})
Then return the hash values in order of the sorted key list.
return s.map(i => d.get(i))
}
Kotlin has a Pair
class, and Raku has Rat
for storing fractions
without the hazards of floating point, but otherwise I just use
two-element arrays.
Task 2: Moebius Number
You are given a positive number $n
.
Write a script to generate the Moebius Number for the given number.
Please refer to wikipedia
page for more
informations.
Which comes down to: looking through the list of prime factors, if
there are any squares or higher powers, the result is 0; otherwise
it's +1 if the number of prime factors is even, -1 if it's odd.
Now obviously I could take a short cut by exiting early from the prime
factorisation algorithm, but primefactors
is useful library code, so
I'll lose a little efficiency by calculating them in full and then
analysing the result. (I did make the improvement to this algorithm I
mentioned back in 155.)
In Perl (reusing the standard genprimes
of course):
sub primefactor {
my $n=shift;
my %f;
my $m=$n;
foreach my $p (@{genprimes(int(sqrt($n)))}) {
while ($m % $p == 0) {
$f{$p}++;
$m=int($m/$p);
if ($m == 1) {
last;
}
}
}
if ($m > 1) {
$f{$m}++;
}
return \%f;
}
Then the actual Möbius analysis is nearly trivial:
sub moebius {
my $n=shift;
my $z=0;
foreach my $v (values %{primefactor($n)}) {
if ($v>1) {
return 0;
}
$z++;
}
if ($z % 2 == 0) {
return 1;
}
return -1;
}
Full code on
github.