[seqfan] Re: Generalization of the totient

[David Wilson]

f(m, n) =
	n,   if m = 1
	n - SUM{d | m, 2 <= d <= n} f(m/d, [n/d]),   if m > 1.

In the recursion, f is sometime called more than once with the same arguments, so memoization will help.
You can also leverage the fact that in recursive calls to f, the first argument is always a divisor of the original m.

> -----Original Message-----
> From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Charles
> Greathouse
> Sent: Wednesday, January 24, 2018 2:37 AM
> To: Sequence Fanatics Discussion list
> Subject: [seqfan] Generalization of the totient
> 
> 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/