[seqfan] Re: Generalization of the totient
timeroot.alex at gmail.com
Wed Jan 24 10:12:35 CET 2018
I believe that, when n >= m, we have f(m, n) = floor(n/m)*phi(m) + f(m,
n%m). Thus we only really need to consider when m < n.
I think an inclusion-exclusion type formula yields decently fast results
when m doesn't have too many distinct prime factors. (Specifically, it
takes time 2^k, if m is divisible by k distinct primes.) This means it's
fast when m is smooth, for instance; or when m is a semi-prime.
The formula is as follows: suppose m = p1^e1 * p2^e2 * p3^e3 ... pk^ek. Then
f(m, n) = n - floor(n/p1) - floor(n/p2) .. - floor(n/pk) + floor(n/p1*p2) +
floor(n/p1*p3) + floor(n/p2*p3) ... - floor(n/p1*p2*p3) ... (-1)^k
The first term, n, is all the numbers in [1..n]. The first term removes all
p1 multiples, the second term removes all p2 multiples, etc. But then we
doubly removed the p1*p2 multiples, so add them back in. And so on.
Obviously if n is significantly smaller than m then we won't need all the
terms in this sequence.
Thinking in these inclusion/exclusion terms reminded me of the prime
counting function, though, and that let me to a much more elegant
description -- by analogy with the Meissel-Lehmer algorithm (see
Let the largest prime factor (or any factor, really) of m be p1. Then
f(m, n) = f(m/p1, n) - f(m/p1, floor(n/p1))
... applying this recursively yields the inclusion-exclusion above. But
allows for nice use of earlier results, or a much simpler recursive
-- Alexander Meiburg
On Wed, Jan 24, 2018 at 12:27 AM, jean-paul allouche <
jean-paul.allouche at imj-prg.fr> wrote:
> Dear Charles
> Do you mean m and k coprime?
> Le 24/01/18 à 08:36, Charles Greathouse a écrit :
> I'm interested in the function f(m, n) which counts the number of k, 1 <= k
>> <= n, such that m and k are squarefree. This function generalizes Euler's
>> totient: f(n, n) = phi(n). Can this be computed efficiently in the more
>> general case where m and n are unequal? (You can assume the factorization
>> of m is known and m and n are of the same order of magnitude.) Is anything
>> interesting known about this function?
>> Charles Greathouse
>> Case Western Reserve University
>> Seqfan Mailing list - http://list.seqfan.eu/
> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan