[seqfan] Re: Generalization of the totient

[Max Alekseyev]

In other words,

f(m,n) = Sum_{d|m} moebius(d) * floor(n/d),

which generalizes the corresponding formula for phi(n).
Using the property of Moebius function, one can further replace m with its
radical (i.e., the product of its distinct prime factrors) to reduce the
number of terms.

Regards,
Max

On Wed, Jan 24, 2018 at 4:12 AM, Alex Meiburg <timeroot.alex at gmail.com>
wrote:

> 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
> floor(n/p1*p2*p3...pk).
>
> 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
> https://en.wikipedia.org/wiki/Prime-counting_function#
> Algorithms_for_evaluating_%CF%80(x)
> )
>
> 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
> implementation!
>
> -Alexander Meiburg
>
> -- 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?
> > best
> > jean-paul
> >
> > 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/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>