|
Search: id:A133755
|
|
|
| A133755 |
|
Number of positive integers less than n/3 which are coprime to n. |
|
+0
1
|
|
| 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
(list; graph; listen)
|
|
|
OFFSET
|
1,7
|
|
|
COMMENT
|
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.
|
|
FORMULA
|
a(n) = sum_{d|n} mu(d)*[n/(3d)] = sum_{d|n} mu(n/d)*d/3. (Max Alekseyev)
For n>3, a(n) = (eulerphi(n) + c) / 3, where c is nonzero if and only if eulerphi(n) is not divisible by 3. In that 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
For n>3, a(n) = (eulerphi(n) + c) / 3 where the term c is non-zero 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 (rgwv@rgwv.com), Jan 06 2008 *)
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 (rgwv@rgwv.com), Jan 06 2008 *)
|
|
PROGRAM
|
(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 */
(PARI) a(n) = ( eulerphi(n) + if(eulerphi(n)%3, (-1)^bigomega(n)*2^(omega(n)-1-(n%3==0))) )/3 /* - Max Alekseyev */
(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: A103284 A071287 A072084 this_sequence A070104 A131085 A134192
Adjacent sequences: A133752 A133753 A133754 this_sequence A133756 A133757 A133758
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
M. F. Hasler (Maximilian.Hasler(AT)gmail.com), Jan 04 2008, Jan 08 2008
|
|
|
Search completed in 0.002 seconds
|
