[seqfan] Re: Generalization of the totient
David Wilson
davidwwilson at comcast.net
Fri Jan 26 05:22:38 CET 2018
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/
More information about the SeqFan
mailing list