1Math::NumSeq::Totient(3U)ser Contributed Perl DocumentatiMoanth::NumSeq::Totient(3)
2
6 Math::NumSeq::Totient -- Euler's totient function, count of coprimes
7
9 use Math::NumSeq::Totient;
10 my $seq = Math::NumSeq::Totient->new;
11 my ($i, $value) = $seq->next;
12
14 Euler's totient function, being the count of integers coprime to i,
15 1, 1, 2, 2, 4, 2, 6, 4, etc (A000010)
17 starting i=1
18 For example i=6 has no common factor with 1 or 5, so the totient is 2.
20 The totient can be calculated from the prime factorization by changing
22 one copy of each distinct prime p to p-1.
23 totient(n) = product (p-1) * p^(e-1)
25 prime factors p^e in n
26
28 See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence
29 classes.
30 "$seq = Math::NumSeq::Totient->new ()"
32 Create and return a new sequence object.
33 Random Access
35 "$value = $seq->ith($i)"
36 Return totient(i).
37 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 "$bool = $seq->pred($value)"
44 Return true if $value occurs in the sequence, ie. $value is the
45 totient of something.
46
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 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 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 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 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 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 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
85 Math::NumSeq, Math::NumSeq::TotientCumulative,
86 Math::NumSeq::TotientPerfect, Math::NumSeq::TotientSteps
87 "euler_phi" in Math::Prime::Util
89
91 <http://user42.tuxfamily.org/math-numseq/index.html>
92
94 Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 Kevin Ryde
95 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 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 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/>.
108perl v5.36.0 2022-07-22 Math::NumSeq::Totient(3)