A133755 Number of positive integers less than n/3 that are coprime to n.

0, 0, 0, 1, 1, 1, 2, 1, 2, 2, 3, 1, 4, 2, 3, 3, 5, 2, 6, 2, 4, 4, 7, 3, 7, 4, 6, 4, 9, 2, 10, 5, 7, 6, 8, 4, 12, 6, 8, 6, 13, 4, 14, 6, 8, 8, 15, 5, 14, 6, 11, 8, 17, 6, 14, 8, 12, 10, 19, 6, 20, 10, 12, 11, 16, 6, 22, 10, 15, 8, 23, 8, 24, 12, 13, 12, 20, 8, 26, 10, 18, 14, 27, 8, 22, 14, 19, 14

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

Sequence in context: A336471 A357975 A366605 * A357853 A336470 A351093

Adjacent sequences: A133752 A133753 A133754 * A133756 A133757 A133758

Keyword

nonn

Author

M. F. Hasler, Jan 04 2008, Jan 08 2008

Status

approved