|
%I #23 Apr 09 2022 09:46:41
%S 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,
%T 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,
%U 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
%N Number of positive integers less than n/3 that are coprime to n.
%C 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.
%H Vincenzo Librandi, <a href="/A133755/b133755.txt">Table of n, a(n) for n = 1..10000</a>
%F 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]
%F 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
%t 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 *)
%o (PARI) vector(100,i, sum(j=1,(i-1)\3,gcd(i,j)==1))
%o (PARI) a(n)=sumdiv(n,d,moebius(n\d)*(d\3)) /* _Max Alekseyev_, Jan 07 2007 */
%o (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 */
%K nonn
%O 1,7
%A _M. F. Hasler_, Jan 04 2008, Jan 08 2008
|
