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

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

Links

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

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

Example

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.

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[[#]]<n && !(Length[odiouses]<=tmp+1)&]-1]], True], {n, rng}]

Prog

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

Crossrefs

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

Sequence in context: A046073 A309786 A162912 * A224762 A039776 A048864

Adjacent sequences: A230067 A230068 A230069 * A230071 A230072 A230073

Keyword

nonn,base

Author

Vladimir Shevelev, Oct 10 2013

Status

approved