Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #14 Jul 16 2023 02:11:27
%S 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,
%T 29,5,31,17,23,17,34,7,37,20,26,19,41,7,43,23,28,23,47,8,49,24,33,27,
%U 53,8,52,29,37,29,59,6,61,32,42,33,59,13,67,34,46,30
%N 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.
%H Charles R Greathouse IV, <a href="/A138663/b138663.txt">Table of n, a(n) for n = 1..10000</a>
%F Floor(log_2(n)) <= a(n) <= n. - _Charles R Greathouse IV_, Feb 11 2014
%e 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.
%t a[n_] := Sum[Boole[CoprimeQ[n, DigitCount[k, 2, 1]]], {k, 1, n}]; Array[a, 100] (* _Amiram Eldar_, Jul 16 2023 *)
%o (PARI) a(n) = sum(k=1, n, gcd(hammingweight(k), n) == 1); \\ _Michel Marcus_, Feb 10 2014
%Y Cf. A138664, A000120.
%K nonn,base
%O 1,2
%A _Leroy Quet_, Mar 25 2008
%E More terms from _Michel Marcus_, Feb 10 2014