1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
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();
|
