1Math::NumSeq::Totient(3U)ser Contributed Perl DocumentatiMoanth::NumSeq::Totient(3)
2
3
4

NAME

6       Math::NumSeq::Totient -- Euler's totient function, count of coprimes
7

SYNOPSIS

9        use Math::NumSeq::Totient;
10        my $seq = Math::NumSeq::Totient->new;
11        my ($i, $value) = $seq->next;
12

DESCRIPTION

14       Euler's totient function, being the count of integers coprime to i,
15
16           1, 1, 2, 2, 4, 2, 6, 4, etc          (A000010)
17           starting i=1
18
19       For example i=6 has no common factor with 1 or 5, so the totient is 2.
20
21       The totient can be calculated from the prime factorization by changing
22       one copy of each distinct prime p to p-1.
23
24           totient(n) =        product          (p-1) * p^(e-1)
25                         prime factors p^e in n
26

FUNCTIONS

28       See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
29       classes.
30
31       "$seq = Math::NumSeq::Totient->new ()"
32           Create and return a new sequence object.
33
34   Random Access
35       "$value = $seq->ith($i)"
36           Return totient(i).
37
38           This calculation requires factorizing $i and in the current code
39           after small factors a hard limit of 2**32 is enforced in the
40           interests of not going into a near-infinite loop.  Above that the
41           return is "undef".
42
43       "$bool = $seq->pred($value)"
44           Return true if $value occurs in the sequence, ie. $value is the
45           totient of something.
46

FORMULAS

48   Predicate
49       Totient(n) > 1 is always even because the factors factor p-1 for odd
50       prime p is even, or if no odd primes in n then totient(2^k)=2^(k-1) is
51       even.  So odd numbers > 1 don't occur as totients.
52
53       The strategy is to look at the divisors of the given value to find the
54       p-1, q-1 etc parts arising as totient(n=p*q) etc.
55
56           initial maxdivisor unlimited
57           try divisors of value, with divisor < maxdivisor
58             if p=divisor+1 is prime then
59               remainder = value/divisor
60               loop
61                 if recurse pred(remainder, maxdivisor=divisor) then yes
62                 if remainder divisible by p then remainder/=p
63                 else next divisor of value
64
65       The divisors tried include 1 and the value itself.  1 becomes p=2
66       casting out possible factors of 2.  For value itself if p=value+1 prime
67       then simply totient(value+1)=value means it is a totient.
68
69       Care must be taken not to repeat a prime p, since value=(p-1)*(p-1) is
70       not a totient form.  One way to do this is to demand only smaller
71       divisors when recursing, hence the "maxdivisor".
72
73       Any divisors > 1 will have to be even to give p=divisor+1 odd to be a
74       prime.  Effectively each p-1, q-1, etc part of the target takes at
75       least one factor of 2 out of the value.  It might be possible to handle
76       the 2^k part of the target value specially, for instance noting that on
77       reaching the last factor of 2 there can be no further recursion, only
78       value=p^a*(p-1) can be a totient.
79
80       This search implicitly produces an n=p^a*q^b*etc with totient(n)=value
81       but for the pred() method that n is not required, only the fact it
82       exists.
83

SEE ALSO

85       Math::NumSeq, Math::NumSeq::TotientCumulative,
86       Math::NumSeq::TotientPerfect, Math::NumSeq::TotientSteps
87
88       "euler_phi" in Math::Prime::Util
89

HOME PAGE

91       <http://user42.tuxfamily.org/math-numseq/index.html>
92

LICENSE

94       Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 Kevin Ryde
95
96       Math-NumSeq is free software; you can redistribute it and/or modify it
97       under the terms of the GNU General Public License as published by the
98       Free Software Foundation; either version 3, or (at your option) any
99       later version.
100
101       Math-NumSeq is distributed in the hope that it will be useful, but
102       WITHOUT ANY WARRANTY; without even the implied warranty of
103       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
104       General Public License for more details.
105
106       You should have received a copy of the GNU General Public License along
107       with Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.
108
109
110
111perl v5.36.0                      2023-01-20          Math::NumSeq::Totient(3)
Impressum