72 Jean-Marie De Koninck

320

• the

12th

number n such that n! + 1 is prime (see the number 116).

323

• the smallest Fibonacci pseudoprime : the only other one known is 377; for the

definition of a Fibonacci pseudoprime, see Ribenboim [169], pp. 126-127.

324

• the

13th

number n such that n! − 1 is prime (see the number 166).

325

• the third pseudoprime in base 7: the ten smallest pseudoprimes in base 7 are

6, 25, 325, 561, 703, 817, 1 105, 1 825, 2 101 and 2 353;

• the smallest (and possibly the only one) 3-hyperperfect number: we say that

a number n is 3-hyperperfect if it can be written as n = 1 + 3

d|n

1dn

d (which is

equivalent to the condition 3σ(n) = 4n + 2); see the number 21;

• the smallest number which can be written as the sum of two squares in three

distinct ways: 325 = 12 + 182 = 62 + 172 = 102 + 152 (see the number 50).

330

• the smallest number n such that π(n) = n/5; if, for each integer m ≥ 2, we set

Am = {n ∈ N : n/π(n) = m}, one can prove that #Am ≥ 1

for78

each m ≥ 2;

a clever computation provides the following table:

78Here

is how one can prove this result, first established in 1962 by S.W. Golomb [91]. Let as

usual p1, p2, . . . stand for the increasing sequence of prime numbers. Given an arbitrary integer

m ≥ 2, one needs to show that equation

n

π(n)

= m has at least one solution n. Since π(x) = o(x),

it follows that for all ε 0, there exists n0 = n0(ε) such that

π(n)

n

ε for all n ≥ n0. This is why

there exists a largest prime number pk such that

π(pk )

pk

=

k

pk

≥

1

m

, so that (∗) pk ≤ mk. But then,

either mk pk+1 or else mk ≥ pk+1. This last case cannot occur, because one would then have

k+1

pk+1

k

pk+1

≥

1

m

, contradicting the minimal choice of pk. Therefore, mk pk+1, an inequality

which coupled with (∗) yields pk ≤ mk ≤ pk+1 − 1, so that k = π(pk) ≤ π(mk) ≤ π(pk+1 − 1) = k,

which establishes that π(mk) = k. Setting n = mk, it follows that n/π(n) = m, thus providing

the required solution n. It is clear on the other hand that the result holds for an arbitrary set of

positive integers of zero density. In other words, one can also prove the following result:

Let {an} be an infinite sequence of positive integers, and let C(x) = #{an ≤ x}.

Assume that C(x) = o(x) when x → ∞. Then there exists a positive integer η such that

the set of integer values taken by the quotient n/C(n) is equal to the set {m : m ≥ η}.

Moreover, η = 1 if and only if a1 = 1.