diff options
Diffstat (limited to 'challenge-159')
| -rw-r--r-- | challenge-159/colin-crain/blog.txt | 1 | ||||
| -rw-r--r-- | challenge-159/colin-crain/blog1.txt | 1 | ||||
| -rwxr-xr-x | challenge-159/colin-crain/perl/ch-1.pl | 125 | ||||
| -rwxr-xr-x | challenge-159/colin-crain/perl/ch-2.pl | 145 | ||||
| -rwxr-xr-x | challenge-159/colin-crain/raku/ch-1.raku | 27 | ||||
| -rwxr-xr-x | challenge-159/colin-crain/raku/ch-2.raku | 40 |
6 files changed, 339 insertions, 0 deletions
diff --git a/challenge-159/colin-crain/blog.txt b/challenge-159/colin-crain/blog.txt new file mode 100644 index 0000000000..d107cfe0eb --- /dev/null +++ b/challenge-159/colin-crain/blog.txt @@ -0,0 +1 @@ +https://colincrain.com/2022/04/11/fareys-wear-boots diff --git a/challenge-159/colin-crain/blog1.txt b/challenge-159/colin-crain/blog1.txt new file mode 100644 index 0000000000..ec4c6406fd --- /dev/null +++ b/challenge-159/colin-crain/blog1.txt @@ -0,0 +1 @@ +https://colincrain.com/2022/04/11/squarefree-is-only-one-side-of-the-story diff --git a/challenge-159/colin-crain/perl/ch-1.pl b/challenge-159/colin-crain/perl/ch-1.pl new file mode 100755 index 0000000000..2cff1df4fb --- /dev/null +++ b/challenge-159/colin-crain/perl/ch-1.pl @@ -0,0 +1,125 @@ +#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
+#
+# fareys-wear-boots.pl
+#
+# Farey Sequence
+# Submitted by: Mohammad S Anwar
+# You are given a positive number, $n.
+#
+# Write a script to compute Farey Sequence of the order $n.
+#
+# Example 1:
+# Input: $n = 5
+# Output: 0/1, 1/5, 1/4, 1/3, 2/5,
+# 1/2,
+# 3/5, 2/3, 3/4, 4/5, 1/1
+#
+# Example 2:
+# Input: $n = 7
+# Output: 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
+#
+# Example 3:
+# Input: $n = 4
+# Output: 0/1, 1/4, 1/3,
+# 1/2,
+# 2/3, 3/4, 1/1
+#
+# method:
+#
+# The Fahey sequence or a given order n is a list of all
+# subunary fractions with denominators up to the value of the
+# order, reduced to their lowest terms and placed in ascending
+# order. One interesting property of this sequence is that for
+# any triplet of successive terms selected, the central term
+# will be the mediant of the two outer, which is to say we can
+# obtain the ratio of the intermediate value by summing the two
+# numerators and two denominators of the outside terms: for the
+# two terms in example 2 above 2/7 and 2/5 the intermediate
+# numerator is 2+2 and denominator is 7+5, yielding 4/12, wich
+# can be reduced to 1/3. This can be seen to be the case by
+# examination of the example.
+#
+# Two algorithms suggest themselves to produce the Fahey
+# sequence for a given order: we can either construct all the
+# fractions exhaustively, reduce them to their lowest terms,
+# remove duplicates and sort them; or alternately we can bisect
+# each set of adjacent fractions in the the previous order to
+# construct the next, reducing them as possible along the way,
+# until we arrive at the order requested.
+#
+# As it
+# © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+use warnings;
+use strict;
+use utf8;
+use feature ":5.26";
+use feature qw(signatures);
+no warnings 'experimental::signatures';
+
+
+package Rat;
+{
+ use Moo;
+ use feature qw(signatures);
+ no warnings 'experimental::signatures';
+
+ has n => ( is => 'ro');
+ has d => ( is => 'ro');
+
+ has num => ( is => 'rw');
+ has den => ( is => 'rw');
+ has val => ( is => 'rw');
+
+ around BUILDARGS => sub {
+ my ( $orig, $class, @args ) = @_;
+ return { n => $args[0],
+ d => $args[1] };
+ };
+
+ sub BUILD ($self, $args) {
+ my $gcd = gcd( $self->n, $self->d );
+ $self->num( $self->n / $gcd );
+ $self->den( $self->d / $gcd );
+ $self->val( $self->n / $self->d );
+ };
+
+ sub gcd ($m, $n) {
+ return $n if $m == 0; ## gcd of (0,n) is n
+ while ( $n != 0 ) {
+ $n > $m and ($m, $n) = ($n, $m);
+ my $r = $m - $n * ( int ($m/$n));
+ return $n if $r == 0;
+ ($m, $n) = ($n, $r);
+ }
+ }
+
+ sub string ($self) {
+ return $self->num . "/" . $self->den;
+ };
+
+}
+
+
+
+package main;
+
+my $order = shift @ARGV // 7;
+
+my @rats;
+for my $den (1..$order) {
+ for my $num ( 0..$den) {
+ push @rats, new Rat($num, $den);
+ }
+}
+
+my %farey = map { $_->string => $_->val } @rats;
+
+say join ' ', sort { $farey{$a} <=> $farey{$b} } keys %farey;
+
+
diff --git a/challenge-159/colin-crain/perl/ch-2.pl b/challenge-159/colin-crain/perl/ch-2.pl new file mode 100755 index 0000000000..3455954f9c --- /dev/null +++ b/challenge-159/colin-crain/perl/ch-2.pl @@ -0,0 +1,145 @@ +#!/Users/colincrain/perl5/perlbrew/perls/perl-5.32.0/bin/perl
+#
+# squarefree-is-only-one-side-of-the-story.pl
+#
+# Moebius Number
+# Submitted by: Mohammad S Anwar
+# 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.
+#
+# Example 1:
+# Input: $n = 5
+# Output: -1
+#
+# Example 2:
+# Input: $n = 10
+# Output: 1
+#
+# Example 3:
+# Input: $n = 20
+# Output: 0
+#
+# method:
+#
+# Named after August Ferdinand Möbius, of mongonal strip fame,
+# the Möbius function serves as a classifier
+# for number factorization: whether a number is squarefree,
+# and, if so, whether is has an odd or even number of prime
+# factors.
+#
+# The squarefree numbers, that we visited in PWC150, are
+# numbers whose prime decompositions have no squared values.
+# This in turn leads to the conclusion that the list of prime
+# factors contains only unique values, as any factor repeated more
+# than two times also contains the second power within that
+# higher exponent. What we are left with is that the only remaining
+# permissible exponent is 1.
+#
+# If a number is not squarefree it in given the Möbius number
+# 0.
+#
+# If the number is 1 it is given the Möbius number 1.
+#
+# If the number is squarefree and greater than 1, is will have
+# a list of distinct prime factors, and if this list has an
+# even number of values the Möbius number is 1, and if odd the
+# number -1. This can also be expressed as (-1)ⁿ, with n the
+# number of prime factors.
+
+# So what do we do with this function?
+#
+# Number throry, as a matter of course, is not traditionally
+# known for its practical application — an observation made
+# albeit a notable turnabout to that trend with the
+# applicability of prime number theory to modern cryptographic
+# techniques. However within the field of number theory the
+# Möbius function is well explored and often encountered. Well,
+# often enough at least.
+
+# Summing over divisors is something commonly studied in the discipline,
+# and there the Möbius function is thus most often seen as a
+# component of the Möbius inversion function, which describes a
+# multiplicative relationship between certain pairs of
+# functions in this domain. The inversion function can be generalized into
+# arbitrary abelian groups in group theory and
+# partially-ordered sets in order theory.
+
+# One property of the Möbius function is that the meta-function
+# describing the average order of the Möbius function can be
+# shown to be equivalent to the prime number theorum. From this
+# proof we can infer that the average order is 0, meaning that
+# there are equal numbers of squarefree numbers with even and
+# odd numbers of factors as the scale tends towards infinity.
+
+# Which is an interesting observation, if you're into that sort
+# of thing.
+#
+#
+# © 2022 colin crain
+## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
+
+
+
+use warnings;
+use strict;
+use utf8;
+use feature ":5.26";
+use feature qw(signatures);
+no warnings 'experimental::signatures';
+
+my $input = shift @ARGV ;
+say moebius_function( $input ) if defined $input;
+
+sub moebius_function ( $input ) {
+ return 1 if $input == 1;
+
+ our @primes = (2,3); ## shared with subroutine
+ my $count = 0;
+
+ add_next_prime() while $primes[-1] <= $input;
+
+ ## check squarefree
+ for (@primes) {
+ if ($input % $_ == 0) {
+ return 0 if $input % $_ ** 2 == 0 ;
+ $count++;
+ }
+ }
+
+ ## return based on odd or even count
+ return (-1)**$count;
+
+ sub add_next_prime ( ) {
+ ## adds the next prime to external sequence
+
+ my $candidate = $primes[-1] ;
+ CANDIDATE: while ( $candidate += 2 ) {
+ my $sqrt_candidate = sqrt( $candidate );
+ for my $test ( @primes ) {
+ next CANDIDATE if $candidate % $test == 0;
+ last if $test > $sqrt_candidate;
+ }
+ push @primes, $candidate;
+ last;
+ }
+ }
+}
+
+
+use Test::More;
+
+is moebius_function( 5), -1, 'ex-1';
+is moebius_function(10), 1, 'ex-2';
+is moebius_function(20), 0, 'ex-3';
+
+is moebius_function( 2), -1, 'edge-2';
+is moebius_function( 3), -1, 'dege-3';
+
+is moebius_function(46), 1, 'mid-46';
+is moebius_function(47), -1, 'mid-47';
+is moebius_function(48), 0, 'mid-48';
+
+
+done_testing();
diff --git a/challenge-159/colin-crain/raku/ch-1.raku b/challenge-159/colin-crain/raku/ch-1.raku new file mode 100755 index 0000000000..e0cd7afa21 --- /dev/null +++ b/challenge-159/colin-crain/raku/ch-1.raku @@ -0,0 +1,27 @@ +#!/usr/bin/env perl6 +# +# +# fareys-wear-boots.raku +# +# +# +# © 2022 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + +unit sub MAIN ( $order = 20 ) ; + +sub tri-cross { [X] (0..$^a.Num) , $^a.Num } ; + +my @f = ((1..$order).map: &tri-cross) + .flat + .rotor(2) ; +my @rats; +my @frac; + +@rats.push: ($_[0]/$_[1]).Rat for @f; +@frac.push: |(@rats.sort.unique).map: *.nude ; + +@frac .= map({ $_[0] ~ '/' ~ $_[1] }); +@frac.put; diff --git a/challenge-159/colin-crain/raku/ch-2.raku b/challenge-159/colin-crain/raku/ch-2.raku new file mode 100755 index 0000000000..58c2da92b5 --- /dev/null +++ b/challenge-159/colin-crain/raku/ch-2.raku @@ -0,0 +1,40 @@ +#!/usr/bin/env perl6 +# +# +# 159-2-squarefree-is-only-one-side-of-the-story.raku +# +# +# +# © 2022 colin crain +## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ## + + + + + +unit sub MAIN ( $num = 302 ) ; + +sub moebius ($num) { + my @primes = (2..$num).grep: { .is-prime && $num %% $_ }; + + return 0 if @primes.grep: $num %% *² ; + return (-1)**@primes.elems ; +} + + +## testing + +use Test; +plan 8; + +is moebius( 5), -1, 'ex-1'; +is moebius(10), 1, 'ex-2'; +is moebius(20), 0, 'ex-3'; + +is moebius( 2), -1, 'edge-2'; +is moebius( 3), -1, 'dege-3'; + +is moebius(46), 1, 'mid-46'; +is moebius(47), -1, 'mid-47'; +is moebius(48), 0, 'mid-48'; + |