login
a(n) is the number of odious integers (A000069) not exceeding n and respectively prime to n.
3

%I #29 Nov 10 2024 09:09:10

%S 1,1,2,1,3,1,3,2,5,2,5,3,6,3,8,4,9,4,9,5,8,5,12,5,12,6,13,5,15,5,15,8,

%T 14,8,12,8,18,9,17,8,20,8,22,10,19,11,23,11,18,11,24,12,27,12,21,10,

%U 25,14,29,11,30,15,24,16,26,13,33,17,32,12,36,16,36

%N a(n) is the number of odious integers (A000069) not exceeding n and respectively prime to n.

%C Let b(n) is the number of evil integers (A001969) not exceeding n and respectively prime to n. Then a(n) + b(n) = phi(n) (phi = A000010). For which numbers a(n) < b(n)? This sequence begins 28,... . For n = 1,2,3,15, we have a(n) = phi(n). What other solutions has this equation? When a(n) = phi(n)/2, we call n a balanced number. The sequence of balanced numbers begins 4,6,7,8,10,11,13,14,16,19,22,...

%H Peter J. C. Moses, <a href="/A230070/b230070.txt">Table of n, a(n) for n = 1..5000</a>

%F For odd prime p, a(p) = (p + 1 or - 1)/2. Primes p for which a(p) = (p+1)/2 are 3, 5, 17, 23, 29,..., i.e., evil primes (A027699), while odd primes p for which a(p) = (p-1)/2 are 7,11,13,19,..., i.e., odious primes (A027697).

%e For n = 30, we have the following numbers respectively prime to n: 1, 7, 11, 13, 17, 19, 23, 29, from which only 5 numbers 1, 7, 11, 13 and 19 are odious. So, a(30) = 5.

%t odiouses=Select[Range[rng=100],OddQ[DigitCount[#,2][[1]]]&]; tmp=1; Table[Count[Map[CoprimeQ[n,#]&, Take[odiouses, tmp=NestWhile[#+1&,tmp+1, odiouses[[#]]<n && !(Length[odiouses]<=tmp+1)&]-1]], True], {n,rng}]

%o (PARI) a(n) = sum(k = 1, n, gcd(k, n) == 1 && hammingweight(k) % 2); \\ _Amiram Eldar_, Nov 10 2024

%Y Cf. A000010, A000069, A001969, A027697, A027699.

%K nonn,base,changed

%O 1,3

%A _Vladimir Shevelev_, Oct 10 2013