A386917 Numbers k such that k * Product_{p prime <= sqrt(k)} (1 - 1/p) is an integer.

1, 2, 3, 4, 6, 8, 9, 12, 15, 18, 21, 24, 30, 45, 70, 105, 154

Offset

1,2

Comments

Also, numbers k such that PrimePi(k) = PrimePi(sqrt(k)) + k * Product_{p prime <= sqrt(k)} (1 - 1/p) - 1.

Links

Table of n, a(n) for n=1..17.

Solomon W. Golomb, Some Problems About Primes, Golomb's Puzzle Column, IEEE Information Theory Society Newsletter, Vol. 58, No. 3 (September 2008), p. 4. See Problems 5 and 6; Some Problems About Primes Solutions, ibid., Vol. 58, No. 4 (December 2008), p. 47.

Mathematica

q[k_] := IntegerQ[k * Product[1 - 1/p, {p, Select[Range[Sqrt[k]], PrimeQ]}]]; Select[Range[200], q]

Prog

(PARI) isok(k) = {my(r = k); forprime(p = 1, sqrtint(k), r *= (1 - 1/p)); denominator(r) == 1; }

Crossrefs

Cf. A000720.

Sequence in context: A002348 A019469 A081491 * A048716 A010434 A074230

Adjacent sequences: A386914 A386915 A386916 * A386918 A386919 A386920

Keyword

nonn,easy,fini,full

Author

Amiram Eldar, Aug 08 2025

Status

approved