OFFSET
1,7
COMMENTS
If the definition were changed to "... <= ...", the term a(3) would change from 0 to 1, but all others remain the same. Obviously a(n) is also the number of reduced fractions < 1/3 with denominator equal to n.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 1..10000
FORMULA
a(n) = Sum_{d|n} mu(d)*[n/(3d)] = Sum_{d|n} mu(n/d)*floor(d/3), for n>3. - Max Alekseyev [Corrected by Ridouane Oudra, Feb 22 2022]
For n>3, a(n) = (eulerphi(n) + c) / 3 where the term c is nonzero if and only if eulerphi(n) is not divisible by 3. In the latter case n=3^t*p1^k1*...*pm^km where every prime pi=2 (mod 3) and t=0 or 1 and the value of c is given by: c = (-1)^(t+k1+...+km) * 2^(m-1). - Max Alekseyev, Jan 07 2007
MATHEMATICA
f[n_] := Block[{c = 0, k = 1, lmt = n/3}, While[k < lmt, If[ GCD[k, n] == 1, c++ ]; k++ ]; c]; Array[f, 88] (* Robert G. Wilson v, Jan 06 2008 *)
PROG
(PARI) vector(100, i, sum(j=1, (i-1)\3, gcd(i, j)==1))
(PARI) a(n)=sumdiv(n, d, moebius(n\d)*(d\3)) /* Max Alekseyev, Jan 07 2007 */
(PARI) { a(n) = ( eulerphi(n) + if(eulerphi(n)%3, (-1)^bigomega(n)*2^(omega(n)-1-(n%3==0))) )/3 } /* Max Alekseyev, Jan 07 2007 */
CROSSREFS
KEYWORD
nonn
AUTHOR
M. F. Hasler, Jan 04 2008, Jan 08 2008
STATUS
approved