login
A230070
a(n) is the number of odious integers (A000069) not exceeding n and respectively prime to n.
3
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
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
KEYWORD
nonn,base
AUTHOR
Vladimir Shevelev, Oct 10 2013
STATUS
approved