| 1 | # Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 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 | |||||||||||
| 19 | package Math::NumSeq::Totient; | ||||||||||
| 20 | 3 | ▶ | use 5.004; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 21 | 3 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 22 | 3 | ▶ | use Math::Prime::XS 0.23 'is_prime'; # version 0.23 fix for 1928099 | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 23 | 3 | ▶ | use Math::Factor::XS 'factors'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 24 | |||||||||||
| 25 | 3 | ▶ | use vars '$VERSION', '@ISA'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 26 | 3 | $VERSION = 75; | |||||||||
| 27 | |||||||||||
| 28 | 3 | ▶ | use Math::NumSeq; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 29 | 3 | ▶ | use Math::NumSeq::Base::IterateIth; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 30 | 3 | @ISA = ('Math::NumSeq::Base::IterateIth', | |||||||||
| 31 | 'Math::NumSeq'); | ||||||||||
| 32 | 3 | *_is_infinite = \&Math::NumSeq::_is_infinite; | |||||||||
| 33 | |||||||||||
| 34 | 3 | ▶ | use Math::NumSeq::PrimeFactorCount;; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 35 | 3 | *_prime_factors = \&Math::NumSeq::PrimeFactorCount::_prime_factors; | |||||||||
| 36 | |||||||||||
| 37 | # uncomment this to run the ### lines | ||||||||||
| 38 | #use Smart::Comments; | ||||||||||
| 39 | |||||||||||
| 40 | |||||||||||
| 41 | # use constant name => Math::NumSeq::__('Totient'); | ||||||||||
| 42 | 3 | ▶ | use constant description => Math::NumSeq::__('Euler totient function, the count of how many numbers coprime to N.'); | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 43 | 3 | ▶ | use constant characteristic_count => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 44 | 3 | ▶ | use constant characteristic_smaller => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 45 | 3 | ▶ | use constant characteristic_increasing => 0; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 46 | 3 | ▶ | use constant values_min => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 47 | 3 | ▶ | use constant default_i_start => 1; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 48 | |||||||||||
| 49 | #------------------------------------------------------------------------------ | ||||||||||
| 50 | # cf A007617 non-totients, all odds, plus evens per A005277 | ||||||||||
| 51 | # A005277 even non-totients, n s.t. n==phi(something) no solution | ||||||||||
| 52 | # A058980 non-totients 0mod4 | ||||||||||
| 53 | # A056595 - sum non-square divisors | ||||||||||
| 54 | # A007614 totients ascending, with multiplicity | ||||||||||
| 55 | |||||||||||
| 56 | # Dressler (1970) N(x) = num phi(n)<=x, then N(x)/x -> A | ||||||||||
| 57 | # A = zeta(2)*zeta(3)/zeta(6) = product primes 1+1/(p*(p-1)) | ||||||||||
| 58 | # | ||||||||||
| 59 | # 2p is a non-totient if 2p+1 composite (p not an S-G prime) | ||||||||||
| 60 | # 4p is a non-totient iff 2p+1 and 4p+1 both composite | ||||||||||
| 61 | # if n non-totient and 2n+1 composite then 2n also non-totient | ||||||||||
| 62 | # | ||||||||||
| 63 | 3 | ▶ | use constant oeis_anum => 'A000010'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 64 | |||||||||||
| 65 | 0 | ▶ | sub ith { | ||||||||
|
Subroutine
ith: not called CC=1 SCAR=6.9
Pod
documented
| |||||||||||
| 66 | 0 | my ($self, $i) = @_; | |||||||||
| 67 | 0 | return _totient($i); | |||||||||
| 68 | } | ||||||||||
| 69 | 1135 | ▶ | sub _totient { | ||||||||
|
Subroutine
_totient: called CC=6 SCAR=18.0
| |||||||||||
| 70 | 1135 | my ($n) = @_; | |||||||||
| 71 | ### _totient(): $n | ||||||||||
| 72 | |||||||||||
| 73 | 1135 | ▶ | if (_is_infinite($n)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 74 | 0 | return $n; | |||||||||
| 75 | } | ||||||||||
| 76 | 1135 | ▶ | if ($n == 0) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 77 | 98 | return 0; | |||||||||
| 78 | } | ||||||||||
| 79 | 1037 | my ($good, @primes) = _prime_factors($n); | |||||||||
| 80 | 1037 | ▶ | return undef unless $good; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 81 | |||||||||||
| 82 | 1037 | my $prev = 0; | |||||||||
| 83 | 1037 | my $ret = 1; | |||||||||
| 84 | 1037 | foreach my $p (@primes) { | |||||||||
| 85 | 1467 | ▶ | if ($p == $prev) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 86 | 362 | $ret *= $p; | |||||||||
| 87 | } else { | ||||||||||
| 88 | 1105 | $ret *= $p - 1; | |||||||||
| 89 | 1105 | $prev = $p; | |||||||||
| 90 | } | ||||||||||
| 91 | } | ||||||||||
| 92 | 1037 | return $ret; | |||||||||
| 93 | } | ||||||||||
| 94 | |||||||||||
| 95 | # totient(x)=p^a.q^b.r^c=n | ||||||||||
| 96 | # seek a prime w for x with w-1 dividing in n | ||||||||||
| 97 | # combinations of the primes of n to make w-1 | ||||||||||
| 98 | # | ||||||||||
| 99 | # factor 2*f of n, arising from prime 2*f+1 | ||||||||||
| 100 | # | ||||||||||
| 101 | # 8 arises from totient(15=3*5) = (3-1)*(5-1)=2*4 | ||||||||||
| 102 | # 484=2*2*11*11 2*11=23 prime | ||||||||||
| 103 | # | ||||||||||
| 104 | 2 | ▶ | sub pred { | ||||||||
|
Subroutine
pred: called CC=5 SCAR=19.3
Pod
documented
| |||||||||||
| 105 | 2 | my ($self, $value) = @_; | |||||||||
| 106 | ### Totient pred(): $value | ||||||||||
| 107 | |||||||||||
| 108 | 2 | ▶ | if ($value <= 1) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 109 | 0 | return ($value == 1); # $value==0 no, $value==1 yes | |||||||||
| 110 | } | ||||||||||
| 111 | 2 | ▶ | if ($value % 2) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 112 | ### no because odd ... | ||||||||||
| 113 | 0 | return 0; | |||||||||
| 114 | } | ||||||||||
| 115 | 2 | ▶ | unless ($value <= 0xFFFF_FFFF) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 116 | 0 | return undef; | |||||||||
| 117 | } | ||||||||||
| 118 | 2 | $value = "$value"; # numize any Math::BigInt for factors() | |||||||||
| 119 | 2 | ▶ | if (_pred_f($value,$value)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 120 | 2 | return 1; | |||||||||
| 121 | } | ||||||||||
| 122 | 0 | return 0; | |||||||||
| 123 | } | ||||||||||
| 124 | 16 | ▶ | sub _pred_f { | ||||||||
|
Subroutine
_pred_f: called CC=10 SCAR=24.1
| |||||||||||
| 125 | 16 | my ($n, $prev_factor) = @_; | |||||||||
| 126 | ### _pred_f(): "n=$n prev=$prev_factor" | ||||||||||
| 127 | |||||||||||
| 128 | 16 | ▶ | if ($n & 1) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 129 | ### no odd ... | ||||||||||
| 130 | 6 | return 0; | |||||||||
| 131 | } | ||||||||||
| 132 | |||||||||||
| 133 | 10 | $n >>= 1; | |||||||||
| 134 | ### halved: $n | ||||||||||
| 135 | 10 | ▶ | if ($n == 1) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 136 | 0 | return 1; # totient(3)=2 occurs | |||||||||
| 137 | } | ||||||||||
| 138 | |||||||||||
| 139 | 10 | foreach my $f (1, factors($n)) { | |||||||||
| 140 | ### at: "n=$n f=$f" | ||||||||||
| 141 | 14 | ▶ | if ($f >= $prev_factor) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 142 | ### f too big, chop search ... | ||||||||||
| 143 | 6 | return 0; | |||||||||
| 144 | } | ||||||||||
| 145 | 8 | my $p = 2*$f+1; | |||||||||
| 146 | ### $p | ||||||||||
| 147 | |||||||||||
| 148 | 8 | my $r = $n / $f; | |||||||||
| 149 | ### divide out: "f=$f to r=$r" | ||||||||||
| 150 | |||||||||||
| 151 | 8 | ▶ | unless (is_prime($p)) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 152 | ### no, not prime ... | ||||||||||
| 153 | 0 | next; | |||||||||
| 154 | } | ||||||||||
| 155 | |||||||||||
| 156 | 8 | for (;;) { | |||||||||
| 157 | 14 | ▶ | if (_pred_f ($r, $f)) { # recurse | ||||||||
|
Branch: 1 branch
| |||||||||||
| 158 | 2 | return 1; | |||||||||
| 159 | } | ||||||||||
| 160 | 12 | ▶ | if ($r % $p) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 161 | 4 | last; | |||||||||
| 162 | } | ||||||||||
| 163 | 8 | ▶ | if ($r == $p) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 164 | 2 | return 1; | |||||||||
| 165 | } | ||||||||||
| 166 | 6 | $r /= $p; | |||||||||
| 167 | ### divide out prime: "p=$p to r=$r" | ||||||||||
| 168 | } | ||||||||||
| 169 | } | ||||||||||
| 170 | |||||||||||
| 171 | ### whole: "n=$n p=".(2*$n+1) | ||||||||||
| 172 | 0 | ▶ | if ($n >= $prev_factor) { | ||||||||
|
Branch: 1 branch
| |||||||||||
| 173 | ### f too big, chop search ... | ||||||||||
| 174 | 0 | return 0; | |||||||||
| 175 | } | ||||||||||
| 176 | 0 | return is_prime(2*$n+1); | |||||||||
| 177 | } | ||||||||||
| 178 | |||||||||||
| 179 | |||||||||||
| 180 | # sub _totient { | ||||||||||
| 181 | # my ($x) = @_; | ||||||||||
| 182 | # my $count = (($x >= 1) # y=1 always | ||||||||||
| 183 | # + ($x > 2 && ($x&1)) # y=2 if $x odd | ||||||||||
| 184 | # + ($x > 3 && ($x % 3) != 0) # y=3 | ||||||||||
| 185 | # + ($x > 4 && ($x&1)) # y=4 if $x odd | ||||||||||
| 186 | # ); | ||||||||||
| 187 | # for (my $y = 5; $y < $x; $y++) { | ||||||||||
| 188 | # $count += _coprime($x,$y); | ||||||||||
| 189 | # } | ||||||||||
| 190 | # return $count; | ||||||||||
| 191 | # } | ||||||||||
| 192 | # sub _coprime { # for x<y | ||||||||||
| 193 | # my ($x, $y) = @_; | ||||||||||
| 194 | # #### _coprime(): "$x,$y" | ||||||||||
| 195 | # if ($y > $x) { | ||||||||||
| 196 | # return 0; | ||||||||||
| 197 | # } | ||||||||||
| 198 | # for (;;) { | ||||||||||
| 199 | # if ($y <= 1) { | ||||||||||
| 200 | # return ($y == 1); | ||||||||||
| 201 | # } | ||||||||||
| 202 | # ($x,$y) = ($y, $x % $y); | ||||||||||
| 203 | # } | ||||||||||
| 204 | # } | ||||||||||
| 205 | |||||||||||
| 206 | |||||||||||
| 207 | 3 | 1; | |||||||||
| 208 | __END__ | ||||||||||