[seqfan] Re: Generalization of the totient

[Alex Meiburg]

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/
>