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

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, 14, 8, 12, 8, 18, 9, 17, 8, 20, 8, 22, 10, 19, 11, 23, 11, 18, 11, 24, 12, 27, 12, 21, 10, 25, 14, 29, 11, 30, 15, 24, 16, 26, 13, 33, 17, 32, 12, 36, 16, 36

Offset: 1

Author

Vladimir Shevelev, Oct 10 2013

Keywords

• nonn
• base

Comments

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,...

Examples

			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.
		

Links

• Peter J. C. Moses, Table of n, a(n) for n = 1..5000

Crossrefs

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

Programs

Mathematica

odiouses=Select[Range[rng=100],OddQ[DigitCount[#,2][[1]]]&]; tmp=1; Table[Count[Map[CoprimeQ[n,#]&, Take[odiouses, tmp=NestWhile[#+1&,tmp+1, odiouses[[#]]
				

PARI

a(n) = sum(k = 1, n, gcd(k, n) == 1 && hammingweight(k) % 2); \\ Amiram Eldar, Nov 10 2024

Formula

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).