A138663 a(n) = number of positive integers k, k <= n, where the number of ones in the binary representation of each k is coprime to n.

1, 2, 3, 3, 5, 3, 7, 5, 8, 5, 11, 4, 13, 8, 11, 9, 17, 5, 19, 10, 15, 12, 23, 5, 25, 14, 18, 15, 29, 5, 31, 17, 23, 17, 34, 7, 37, 20, 26, 19, 41, 7, 43, 23, 28, 23, 47, 8, 49, 24, 33, 27, 53, 8, 52, 29, 37, 29, 59, 6, 61, 32, 42, 33, 59, 13, 67, 34, 46, 30

Offset

1,2

Links

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000

Formula

Floor(log_2(n)) <= a(n) <= n. - Charles R Greathouse IV, Feb 11 2014

Example

The integers 1 through 9 in binary are (1, 10, 11, 100, 101, 110, 111, 1000, 1001). So the numbers of 1's in these binary representations form the sequence (1,1,2,1,2,2,3,1,2,...) (sequence A000120, starting from A000120(1)). 9 is coprime to 8 of these integers. (9 is coprime to all of these integers except the 3.) So a(9) = 8.

Mathematica

a[n_] := Sum[Boole[CoprimeQ[n, DigitCount[k, 2, 1]]], {k, 1, n}]; Array[a, 100] (* Amiram Eldar, Jul 16 2023 *)

Prog

(PARI) a(n) = sum(k=1, n, gcd(hammingweight(k), n) == 1); \\ Michel Marcus, Feb 10 2014

Crossrefs

Cf. A138664, A000120.

Sequence in context: A367133 A065070 A070800 * A330834 A056149 A167494

Adjacent sequences: A138660 A138661 A138662 * A138664 A138665 A138666

Keyword

nonn,base

Author

Leroy Quet, Mar 25 2008

Extensions

More terms from Michel Marcus, Feb 10 2014

Status

approved