An euler's totient-related sequence

[Max A.]

On 1/2/07, Nick Hobson <nickh at qbyte.org> wrote:

> Is the following sequence of interest?
>
> 0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 3, 3, 5, 2, 6, 2, ... .
>
> a(n) = number of integers < n/3 that are coprime to n.  Equivalently, it
> is the number of fractions in their lowest terms that are < 1/3, with
> denominator equal to n.
>
> Is there an easy analytic form for this sequence?

a(n) = \sum_{d|n} mu(d)*[n/(3d)] = \sum_{d|n} mu(n/d)*[d/3]
where mu() is Moebius function. In PARI/GP:
a(n)=sumdiv(n,d,moebius(n\d)*(d\3))

Another formula:
for n>3, a(n) = (eulerphi(n) + c) / 3
where the term c is non-zero only if n is not divisible by 9 and all
prime divisors of n equal 0 or 2 modulo 3 (note that in this case
eulerphi(n) is not divisible by 3). For n=3^t*p1^k1*...*pm^km where
every prime pi=2 (mod 3) and t=0 or 1,
c = (-1)^(t+k1+...+km) * 2^(m-1)

> PS  Is it necessary to send to *both* addresses: seqfans at seqfan.net,
> seqfan at ext.jussieu.fr?  Are some people on just one of the lists?

I believe that seqfans at seqfan.net currently does not work at all, so
it is pointless but harmless to send anything there.

Max