Math::N...:Totient(3)

📦
version 75 · 2 versions
, in fedora 43

💖 Math::N...:Totient(3) 💖

okay so this page comes from the User Contributed Perl Documentation (section 3, perl module central, we stan) and it's all about a little module called Math::NumSeq::Totient. no cap, it's cute.

✨ NAME ✨

Math::NumSeq::Totient — Euler's totient function, aka the count of coprimes 🎀

🦋 SYNOPSIS 🦋

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

that's it. three lines. main character energy fr fr 💅

🌸 DESCRIPTION 🌸

Euler's totient function is the count of integers coprime to i. like, how many numbers from the ones below i share zero common factors with it. iconic behaviour.

1, 1, 2, 2, 4, 2, 6, 4, etc          (A000010)
starting i=1

(and yes bestie, starting i=1, that's the index convention, don't come at me.)

so for example, i=6 has no common factor with 1 or 5, which means the totient is 2. only two besties are coprime with 6, and they're 1 and 5. periodt.

the way you actually compute it is by peeking at the prime factorization: you take one copy of each distinct prime p and swap it for p-1. it's giving glow-up:

totient(n) =        product          (p-1) * p^(e-1)
              prime factors p^e in n

⭐ FUNCTIONS ⭐

lowkey, check out "FUNCTIONS" in Math::NumSeq for the behaviour that's common to all the sequence classes, because those are shared vibes.

  • $seq = Math::NumSeq::Totient->new () — creates and hands you back a brand new sequence object. a whole new seq, fresh out the box 🫶

🎀 Random Access 🎀

  • $value = $seq->ith($i) — returns totient(i).
⚠️ this calculation needs to factorize $i, and in the current code, after the small factors, there's a hard limit of 2**32 enforced in the interests of not sliding into a near-infinite loop. above that, the return is undef. so like, don't. 💀
  • $bool = $seq->pred($value) — returns true if $value actually occurs in the sequence, meaning $value is the totient of something. a little yes/no vibe check.

🧚 FORMULAS 🧚

💜 Predicate 💜

Totient(n) > 1 is always even, bestie. why? because the factor p-1 for an odd prime p is even, or if there are no odd primes in n then totient(2^k)=2^(k-1) which is also even. so odd numbers > 1 simply don't occur as totients. not invited to the party. 🙈

the strategy is to look at the divisors of the given value to find the p-1, q-1 etc parts arising as totient(n=p*q) etc. here's the whole search, verbatim, because it's literally the algorithm:

initial maxdivisor unlimited
try divisors of value, with divisor < maxdivisor
  if p=divisor+1 is prime then
    remainder = value/divisor
    loop
      if recurse pred(remainder, maxdivisor=divisor) then yes
      if remainder divisible by p then remainder/=p
      else next divisor of value

the divisors tried include 1 and the value itself. 1 becomes p=2, casting out possible factors of 2. and for the value itself, if p=value+1 is prime, then simply totient(value+1)=value means it is a totient. slay.

care must be taken not to repeat a prime p, since value=(p-1)*(p-1) is not a totient form. one way to do this is to demand only smaller divisors when recursing — hence the "maxdivisor". the way that constraint is doing the heavy lifting... 😭

any divisors > 1 will have to be even, to give p=divisor+1 odd, so it can be a prime. effectively each p-1, q-1, etc part of the target takes at least one factor of 2 out of the value. it might be possible to handle the 2^k part of the target value specially — for instance, noting that on reaching the last factor of 2 there can be no further recursion, only value=p^a*(p-1) can be a totient.

this search implicitly produces an n=p^a*q^b*etc with totient(n)=value, but for the pred() method that n is not required — only the fact that it exists. we don't need the receipt, we just need to know it happened. 💅

🌈 SEE ALSO 🌈

  • Math::NumSeq
  • Math::NumSeq::TotientCumulative
  • Math::NumSeq::TotientPerfect
  • Math::NumSeq::TotientSteps
  • "euler_phi" in Math::Prime::Util

the whole totient cinematic universe, iykyk 🦋

👑 HOME PAGE 👑

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

💖 LICENSE 💖

Copyright 2011, 2012, 2013, 2014, 2016, 2019, 2020, 2021 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.

and that's the whole page bestie 🫶 this one's running on perl v5.42.0, dated 2025-07-25, straight out of Math::N...:Totient(3). go be coprime with someone you love. periodt. 💅✨

📦 where this page comes from