| 1 | # Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde | ||||||||||||||||||||||||||||||||||
| 2 | |||||||||||||||||||||||||||||||||||
| 3 | # This file is part of Math-NumSeq. | ||||||||||||||||||||||||||||||||||
| 4 | # | ||||||||||||||||||||||||||||||||||
| 5 | # Math-NumSeq is free software; you can redistribute it and/or modify | ||||||||||||||||||||||||||||||||||
| 6 | # it under the terms of the GNU General Public License as published by the | ||||||||||||||||||||||||||||||||||
| 7 | # Free Software Foundation; either version 3, or (at your option) any later | ||||||||||||||||||||||||||||||||||
| 8 | # version. | ||||||||||||||||||||||||||||||||||
| 9 | # | ||||||||||||||||||||||||||||||||||
| 10 | # Math-NumSeq is distributed in the hope that it will be useful, but | ||||||||||||||||||||||||||||||||||
| 11 | # WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY | ||||||||||||||||||||||||||||||||||
| 12 | # or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | ||||||||||||||||||||||||||||||||||
| 13 | # for more details. | ||||||||||||||||||||||||||||||||||
| 14 | # | ||||||||||||||||||||||||||||||||||
| 15 | # You should have received a copy of the GNU General Public License along | ||||||||||||||||||||||||||||||||||
| 16 | # with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>. | ||||||||||||||||||||||||||||||||||
| 17 | |||||||||||||||||||||||||||||||||||
| 18 | package Math::NumSeq::MobiusFunction; | ||||||||||||||||||||||||||||||||||
| 19 | 2 | ▶ | use 5.004; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 20 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 21 | 2 | ▶ | use List::Util 'min','max'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 22 | |||||||||||||||||||||||||||||||||||
| 23 | 2 | ▶ | use vars '$VERSION','@ISA'; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 24 | 2 | $VERSION = 75; | |||||||||||||||||||||||||||||||||
| 25 | |||||||||||||||||||||||||||||||||||
| 26 | 2 | ▶ | use Math::NumSeq; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 27 | 2 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 28 | 2 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||||||||||||||||||||||||||
| 29 | 'Math::NumSeq'); | ||||||||||||||||||||||||||||||||||
| 30 | 2 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||||||||
| 32 | 2 | ▶ | use Math::NumSeq::Fibonacci; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 33 | 2 | *_blog2_estimate = \&Math::NumSeq::Fibonacci::_blog2_estimate; | |||||||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||||||||
| 35 | # uncomment this to run the ### lines | ||||||||||||||||||||||||||||||||||
| 36 | #use Smart::Comments; | ||||||||||||||||||||||||||||||||||
| 37 | |||||||||||||||||||||||||||||||||||
| 38 | |||||||||||||||||||||||||||||||||||
| 39 | # use constant name => Math::NumSeq::__('Mobius Function'); | ||||||||||||||||||||||||||||||||||
| 40 | 2 | ▶ | use constant description => Math::NumSeq::__('The Mobius function, being 1 for an even number of prime factors, -1 for an odd number, or 0 if any repeated factors (ie. not square-free).'); | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 41 | 2 | ▶ | use constant characteristic_increasing => 0; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 42 | 2 | ▶ | use constant characteristic_integer => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 43 | 2 | ▶ | use constant values_min => -1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 44 | 2 | ▶ | use constant values_max => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 45 | 2 | ▶ | use constant default_i_start => 1; | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 46 | |||||||||||||||||||||||||||||||||||
| 47 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||||||||
| 48 | # cf A030059 the -1 positions, being odd number of distinct primes | ||||||||||||||||||||||||||||||||||
| 49 | # A030229 the 1 positions, being even number of distinct primes | ||||||||||||||||||||||||||||||||||
| 50 | # A013929 the 0 positions, being square factor, ie. the non-square-frees | ||||||||||||||||||||||||||||||||||
| 51 | # A005117 square free numbers, mobius -1 or +1 | ||||||||||||||||||||||||||||||||||
| 52 | # | ||||||||||||||||||||||||||||||||||
| 53 | 2 | ▶ | use constant oeis_anum => 'A008683'; # mobius -1,0,1 starting i=1 | ||||||||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||||||||
| 54 | |||||||||||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||||||||
| 56 | #------------------------------------------------------------------------------ | ||||||||||||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||||||||||||
| 58 | 114 | ▶ | sub ith { | ||||||||||||||||||||||||||||||||
|
Subroutine
ith: called CC=13 SCAR=25.8
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 59 | 114 | my ($self, $i) = @_; | |||||||||||||||||||||||||||||||||
| 60 | ### MobiusFunction ith(): $i | ||||||||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||||||||
| 62 | 114 | my $ret = 0; | |||||||||||||||||||||||||||||||||
| 63 | |||||||||||||||||||||||||||||||||||
| 64 | 114 | ▶ | if (_is_infinite($i) || $i < 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
_is_infinite($i) or $i < 0
MC/DC50%1/2
_is_infinite($i) or $i < 0
_is_infinite($i)
$i < 0
Truth table66%2/3
A or B
A= _is_infinite($i)B= $i < 0
| |||||||||||||||||||||||||||||||||||
| 65 | 3 | return undef; | |||||||||||||||||||||||||||||||||
| 66 | } | ||||||||||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||||||||
| 68 | 111 | ▶ | if (($i % 2) == 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 69 | 58 | $i /= 2; | |||||||||||||||||||||||||||||||||
| 70 | 58 | ▶ | if (($i % 2) == 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 71 | 25 | return 0; # square factor | |||||||||||||||||||||||||||||||||
| 72 | } | ||||||||||||||||||||||||||||||||||
| 73 | 33 | $ret = 1; | |||||||||||||||||||||||||||||||||
| 74 | } | ||||||||||||||||||||||||||||||||||
| 75 | |||||||||||||||||||||||||||||||||||
| 76 | 86 | ▶ | if ($i <= 0xFFFF_FFFF) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 77 | 86 | $i = "$i"; # numize Math::BigInt for speed | |||||||||||||||||||||||||||||||||
| 78 | } | ||||||||||||||||||||||||||||||||||
| 79 | |||||||||||||||||||||||||||||||||||
| 80 | 86 | my $sqrt = int(sqrt($i)); | |||||||||||||||||||||||||||||||||
| 81 | 86 | ▶ | my $limit = min ($sqrt, | ||||||||||||||||||||||||||||||||
|
Condition50%1/2
_blog2_estimate($i) || 1
MC/DC0%0/1
_blog2_estimate($i) || 1
_blog2_estimate($i)
Truth table50%1/2
A
A= _blog2_estimate($i)
| |||||||||||||||||||||||||||||||||||
| 82 | 10_000 / (_blog2_estimate($i) || 1)); | ||||||||||||||||||||||||||||||||||
| 83 | ### $sqrt | ||||||||||||||||||||||||||||||||||
| 84 | ### $limit | ||||||||||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||||||||
| 86 | 86 | ▶ | for (my $p = 3; $p <= $limit; $p += 2) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 87 | 34 | ▶ | if (($i % $p) == 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 88 | 14 | $i /= $p; | |||||||||||||||||||||||||||||||||
| 89 | 14 | ▶ | if (($i % $p) == 0) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 90 | ### square factor, zero ... | ||||||||||||||||||||||||||||||||||
| 91 | 8 | return 0; | |||||||||||||||||||||||||||||||||
| 92 | } | ||||||||||||||||||||||||||||||||||
| 93 | 6 | $ret ^= 1; | |||||||||||||||||||||||||||||||||
| 94 | 6 | $sqrt = int(sqrt($i)); # new smaller limit | |||||||||||||||||||||||||||||||||
| 95 | 6 | $limit = min ($sqrt, $limit); | |||||||||||||||||||||||||||||||||
| 96 | ### factor: "$p new ret $ret new limit $limit" | ||||||||||||||||||||||||||||||||||
| 97 | } | ||||||||||||||||||||||||||||||||||
| 98 | } | ||||||||||||||||||||||||||||||||||
| 99 | 78 | ▶ | if ($sqrt > $limit) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 100 | ### not all factors found up to limit ... | ||||||||||||||||||||||||||||||||||
| 101 | # ENHANCE-ME: prime_factors() here if <2^32 | ||||||||||||||||||||||||||||||||||
| 102 | 0 | return undef; | |||||||||||||||||||||||||||||||||
| 103 | } | ||||||||||||||||||||||||||||||||||
| 104 | 78 | ▶ | if ($i != 1) { | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 105 | 62 | $ret ^= 1; | |||||||||||||||||||||||||||||||||
| 106 | } | ||||||||||||||||||||||||||||||||||
| 107 | 78 | ▶ | return ($ret ? -1 : 1); | ||||||||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||||||||
| 108 | } | ||||||||||||||||||||||||||||||||||
| 109 | |||||||||||||||||||||||||||||||||||
| 110 | 6 | ▶ | sub pred { | ||||||||||||||||||||||||||||||||
|
Subroutine
pred: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||||||||
| 111 | 6 | my ($self, $value) = @_; | |||||||||||||||||||||||||||||||||
| 112 | 6 | ▶ | return ($value == 0 || $value == 1 || $value == -1); | ||||||||||||||||||||||||||||||||
|
Condition83%5/6
$value == 0 || $value == 1 || $value == -1
$value == 0 or $value == 1
MC/DC0%0/3
$value == 0 || $value == 1 || $value == -1
$value == 0
$value == 1
$value == -1
Truth table75%3/4
A or B || C
A= $value == 0B= $value == 1C= $value == -1
| |||||||||||||||||||||||||||||||||||
| 113 | } | ||||||||||||||||||||||||||||||||||
| 114 | |||||||||||||||||||||||||||||||||||
| 115 | 2 | 1; | |||||||||||||||||||||||||||||||||
| 116 | __END__ | ||||||||||||||||||||||||||||||||||