A094387 Numbers k such that gcd(k, A000120(k)) = 1.

1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 14, 15, 16, 17, 19, 22, 23, 25, 26, 27, 28, 29, 31, 32, 33, 35, 37, 38, 39, 41, 43, 44, 45, 47, 49, 50, 51, 52, 53, 56, 57, 59, 61, 62, 64, 65, 67, 70, 71, 73, 74, 75, 76, 77, 79, 82, 83, 85, 87, 88, 89, 91, 93, 94, 95, 97, 98, 99, 100, 101, 103

Offset: 1

Author

Benoit Cloitre, Jun 08 2004

Keywords

• nonn
• base

Comments

This sequence has density 6/Pi^2 (Olivier, 1975).

All primes, powers of 2, and powers of two plus one are terms of this sequence. - William Boyles, Jan 27 2022

References

• Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge University Press, 2003, p. 117.

Links

• Amiram Eldar, Table of n, a(n) for n = 1..10000
• Christian Mauduit, Carl Pomerance and András Sárközy, On the distribution in residue classes of integers with a fixed sum of digits, The Ramanujan Journal, Vol. 9, No. 1-2 (2005), pp. 45-62; alternative link.
• Michel Olivier, Sur la probabilité que n soit premier à la somme de ses chiffres, C. R. Math. Acad. Sci. Paris, Série A, Vol. 280 (1975), pp. 543-545.
• Michel Olivier, Fonctions g-additives et formule asymptotique pour la propriété (n, f(n)) = q, Acta Arithmetica, Vol. 31, No. 4 (1976), pp. 361-384; alternative link.

Crossrefs

Cf. A000120, A059956.

Programs

Mathematica

Select[Range[100], CoprimeQ[#, DigitCount[#, 2, 1]] &] (* Amiram Eldar, Nov 22 2020 *)

PARI

lista(nn) = {for (n=1, nn, if (gcd(n, norml2(binary(n))) == 1, print1(n, ", ")););} \\ Michel Marcus, May 25 2013

Python

from math import gcd
def ok(n): return gcd(n, bin(n).count('1')) == 1
print([k for k in range(104) if ok(k)]) # Michael S. Branicky, Jan 25 2022