Journal de Théorie des Nombres de Bordeaux

Harold G. Diamond

Janos Pintz

Oscillation of Mertens’ product formula

Patrick Ingram

A quantitative primitive divisor result for points on elliptic curves

Florian Luca

Ravindranathan Thangadurai

Florian LUCA et Ravindranathan THANGADURAI
On an arithmetic function considered by Pillai
Tome 21, no 3 (2009), p. 695-701.
<http://jtnb.cedram.org/item?id=JTNB_2009__21_3_695_0>
© Université Bordeaux 1, 2009, tous droits réservés.
L’accès aux articles de la revue « Journal de Théorie des Nom-
bres de Bordeaux » (http://jtnb.cedram.org/), implique l’accord
avec les conditions générales d’utilisation (http://jtnb.cedram.
org/legal/). Toute reproduction en tout ou partie cet article sous
quelque forme que ce soit pour tout usage autre que l’utilisation à
fin strictement personnelle du copiste est constitutive d’une infrac-
tion pénale. Toute copie ou impression de ce fichier doit contenir
la présente mention de copyright.
cedram
Article mis en ligne dans le cadre du
Centre de diffusion des revues académiques de mathématiques
http://www.cedram.org/
Journal de Théorie des Nombres
de Bordeaux 21 (2009), 695-701
On an arithmetic function considered by Pillai
par Florian LUCA et Ravindranathan THANGADURAI
Résumé. Soit n un nombre entier positif et p(n) le plus grand
nombre premier p ≤ n. On considère la suite finie décroissante
définie récursivement par n1 = n, ni+1 = ni − p(ni) et dont le
dernier terme, nr, est soit premier soit égal à 1. On note R(n) = r
la longueur de cette suite. Nous obtenons des majorations pour
R(n) ainsi qu’une estimation du nombre d’éléments de l’ensemble
des n ≤ x en lesquels R(n) prend une valeur donnée k.
Abstract. For every positive integer n let p(n) be the largest
prime number p ≤ n. Given a positive integer n = n1, we study
the positive integer r = R(n) such that if we define recursively
ni+1 = ni − p(ni) for i ≥ 1, then nr is a prime or 1. We obtain
upper bounds for R(n) as well as an estimate for the set of n
whose R(n) takes on a fixed value k.
1. Introduction
Let n > 1 be an integer. Let p(n) be the largest prime factor of n. Let
n2 = n1 − p(n1). If n2 > 1, let n3 = n2 − p(n2), and, recursively, if nk > 1,
we put nk+1 = nk − p(nk). Note that if nk is prime, then nk+1 = 0. We
put R(n) for the positive integer k such that nk is prime or 1. Hence, we
obtain a representation of n of the form
(1.1) n = p1 + p2 + · · ·+ pr,
with r = R(n), where p1 > p2 > · · · > pr are primes except for the last one
which might be 1.
The above representation of n was first considered by Pillai in [6] who ob-
tained a number of interesting results concerning the function R(n). Here,
we extend some of Pillai’s results on this function.
Since by Bertrand’s postulate the interval [x, 2x) contains a prime num-
ber for all x ≥ 1, it follows that if nk > 1, then nk+1 ≤ nk/2. This
immediately implies that R(n) = O(logn). Pillai proved that the better
estimate R(n) = o(logn) holds as n → ∞. He also showed, under the
Manuscrit reçu le 26 novembre 2007.
696 Florian Luca, Ravindranathan Thangadurai
Riemann Hypothesis, that the inequality R(n) < 2 log logn holds when-
ever n > n0. Here, we remove the conditional assumption on the Riemann
Hypothesis from Pillai’s result and prove the following theorem.
Theorem 1.1. The estimate
R(n) log logn
holds for all positive integers n ≥ 3.
Pillai also showed that
(1.2) lim sup
n→∞
R(n) =∞.
Our next result is slightly stronger than estimate (1.2) above. In what
follows, we put logk x for the function defined inductively as log1 x = log x
and logk x = max{1, log(logk−1 x)} for k > 1. When k = 1, we omit the
subscript. Note that if x is large, then logk x coincides with the kth fold
composition of the natural logarithm function evaluated in x.
Theorem 1.2. Let k ≥ 1 be any fixed integer. Then the estimate
# {n ≤ x : R(n) = k} k
x
logk x
holds.
Theorem 1.2 shows that for any fixed k, the asymptotic density of the
set of n with R(n) ≤ k is zero. This shows not only that estimate (1.2)
holds, but that R(n)→∞ holds on a set of n of asymptotic density 1.
Pillai also conjectured that perhaps the inequality R(n) log logn holds
for infinitely many n. We believe this conjecture to be false. Indeed, a
widely believed conjecture of Cramér [2] from 1936, asserts that if x >
x0, then the interval [x, x + (log x)2] contains a prime number. If true,
this implies that if nk > x0, then nk+1 < (lognk)2. Let f(n) be the
function which associates to each integer n > x0 the minimal number of
iterations of the function x 7→ (log x)2 required to take n just below x0.
Then Cramér’s conjecture implies that R(n) ≤ f(n) + O(1), where the
constant implied in O(1) can be taken to be max{R(n) : n ≤ x0}. Let
us take a look at these iterations. Assume that n is large. We then have
n1 = n, n2 ≤ (logn)2, n3 ≤ (logn2)2 ≤ (2 log(2 logn))2 < 8(log logn)2.
Inductively, one shows that if k is fixed and n is sufficiently large with
respect to k, then the inequality nk < 8(logk n)2 holds. Since k is arbitrary,
we conclude that f(n) = o(logk n) holds with any fixed k ≥ 1 as n → ∞,
so, in particular, the inequality f(n)  log logn cannot hold for infinitely
many positive integers n. Let us observe that the weaker assumption that
the interval [x, x + exp((log x)1/2)] contains a prime for all x > x0 will
easily lead to the conclusion that R(n) = O(log3 n). Indeed, in this case we
On an arithmetic function considered by Pillai 697
have lognk+1 ≤ (lognk)1/2, whenever nk > x0. In particular, lognk+1 ≤
(logn)1/2k , whenever nk+1 > x0. This implies easily that for some k of size
at most (log log logn)/ log 2 + O(1) we have nk+1 < x0, so that R(n) =
O(log3 n).
Pillai also looked at the sequence of local maxima (in modern terms
also called champions) for the function R(n). Recall that n is called a
champion if R(m) < R(n) holds for all m < n. Let {tk}k≥1 be the sequence
of champions. Pillai showed that t1 = 1 and that the recurrence tk+1 =
p(tk+1) + tk holds for all k ≥ 1. Furthermore, tk and tk+1 have different
parities for all k ≥ 1. He also showed that {tk}k≥1 grows very fast, namely
that for each positive constant A one has tk+1 A tk(log tk)A. He also
calculated the first 4 values of the sequence {tk}k≥1 obtaining
t1 = 1, t2 = 4 = 3 + 1, t3 = 27 = 23 + 4, t4 = 1354 = 1327 + 27.
He mentioned (seventy years ago!) that it is perhaps possible to compute
t5 but not t6. Consulting Thomas Nicely’s [5] tables of prime gaps, we get
t5 = 401429925999155061 = 401429925999153707 + 1354
and Cramér’s conjecture implies that t6 > exp(4 · 108), so indeed it is
perhaps not possible to compute t6.
2. Proof of Theorem 1.1
For the proof of the fact that R(n) < 2 log logn for n > n0 under the
Riemann Hypothesis, Pillai used the known consequence of the Riemann
Hypothesis that for each δ > 0, there is some xδ such that when x > xδ,
the interval [x, x+ x1/2+δ] contains a prime number.
In the same year as Pillai’s paper [6] appeared, Hoheisel proved his fa-
mous theorem about Prime Number Gaps.
Theorem 2.1 ([4]). There exist absolute constants θ ∈ (0, 1) and N0 such
that for every integer n ≥ N0, the interval [n − nθ, n] contains a prime
number.
The best known θ = 0.525 is due to Baker, Harman and Pinz [1]. The
proof of Theorem 1.1 follows easily from Pillai’s arguments by replacing the
prime number gaps guaranteed by the Riemann Hypothesis with Hoheisel’s
result.1
1It seems likely that Pillai was not aware of Hoheisel’s paper [4].
698 Florian Luca, Ravindranathan Thangadurai
Let n1 ≥ N0. By Theorem 2.1, p(n1) > n − nθ. Thus, the chain of
inequalities
n2 = n1 − p(n1) < n1 − n1 + nθ1 = nθ1;
n3 = n2 − p(n2) < nθ2 < nθ
2
1 ;
n4 < n
θ3
1 ;
. . . . . . . . .
n`+1 < n
θ`
1
holds as long as n` ≥ N0. We now let ` be that integer such that n`+2 <
N0 ≤ n`+1. We then have
nθ
`
1 ≥ N0,
therefore
θ` logn1 ≥ logN0,
which implies that
` log θ + log logn1 ≥ log logN0.
Hence,
log logn1 ≥ ` log (1/θ) ,
which in light of the fact that θ ∈ (0, 1) gives
` ≤ log logn1
log (1/θ)
.
Put b = max1≤m≤N0{R(m)}. Trivially, b ≤ π(N0). Thus,
R(n1) ≤ `+ 1 + b <
log logn1
log (1/θ)
+ 1 + b log logn1,
which is the desired inequality.
3. Proof of Theorem 1.2
For every prime number p we put p′ for the next prime following p. The
following result is certainly well-known but we shall supply a short proof
of it.
Lemma 3.1. For 2 ≤ y ≤ log x, put
P(x, y) =
{
p ≤ x : p′ − p 6∈ [y−1(log x), y(log x)]
}
.
Then,
(3.1) #P(x, y) π(x)
y
.
On an arithmetic function considered by Pillai 699
Proof. We first look at the primes p ≤ x which are in P(x, y) and p′− p >
y log x. The interval [1, x] is contained in the union of the subintervals
[(i − 1)y log x, iy(log x)] for i = 1, 2, . . . , bx/(y log x)c + 1. Since p′ − p >
y(log x), each one of the above intervals can contain at most one such prime
p. Thus, the number of such primes p does not exceed
#{p ≤ x : p′ − p > y(log x)} ≤ bx/(y log xc+ 1 ≤ 2x/(y log x)
 π(x)/y.(3.2)
We next look at the primes p ≤ x which are in P(x, y) and p′ − p = h <
z = y−1(log x). We fix h and look at the set of primes p ≤ x such that
p+ h is also prime. We write Ah(x) for this set. By Brun’s sieve (see, for
example, [3, Theorem 5.7]), we have
#Ah(x)
x
(log x)2
h
φ(h)
.
Summing up over all the acceptable values of h ≤ z, we get that
#{p ≤ x : p′ − p < z} ≤
∑
1≤h≤z
#Ah ≤
x
(log x)2
∑
1≤h≤z
h
φ(h)
 xz
(log x)2
 π(x)
y
.(3.3)
In the above estimates, we used the known fact that the estimate∑
1≤h≤t
h
φ(h)
 t
holds for all t ≥ 1 (see, for example, [7]). The desired conclusion follows
now immediately from estimates (3.2) and (3.3). 
Proof of Theorem 1.2. We put Rk = {n : R(n) = k} and Rk(x) = Rk ∩
[1, x]. We prove the theorem by induction on k having as a base the case
k = 1 for which the assertion is immediate by the Prime Number Theorem.
Assume that k ≥ 2. We first deal with the upper bound on #Rk(x). We
have, by the induction hypothesis,
#Rk(x) = #{n = p+m ≤ x : R(m) = k − 1, p ≤ n < p′}
=
∑
p≤x
#{m ≤ p′ − p : R(m) = k − 1}
≤
∑
p≤x
#Rk−1(p′ − p)k
∑
p≤x
(p′ − p)
logk−1(p′ − p)
.(3.4)
700 Florian Luca, Ravindranathan Thangadurai
We split the last sum above at z = (log x)1/3. If p′−p > z, then logk−1(p′−
p)k logk x, therefore
(3.5)
∑
p≤x
p′−p>z
(p′ − p)
logk−1(p′ − p)
k
1
logk x
∑
p≤x
(p′ − p) x
logk x
,
where for the last inequality above we used the fact that the intervals [p, p′)
for p ≤ x are disjoint and their union is contained in [1, 2x] by the Bertrand
postulate. For the range p′ − p ≤ z, we proceed as in the proof of Lemma
3.1 by first fixing h ≤ z and looking at the primes p ∈ Ah(x). The proof of
Lemma 3.1 shows that∑
p∈Ah(x)
(p′ − p)
logk−1(p′ − p)

∑
p∈Ah(x)
h ≤ h#Ah 
x
log x
h2
φ(h)
 xz
log x
h
φ(h)
,
therefore
(3.6)
∑
p≤x
p′−p≤z
(p′ − p)
logk−1(p′ − p)
 xz
log x
∑
h≤z
h
φ(h)
 xz
2
log x
= x
z
 x
logk x
.
Estimates (3.4), (3.5) and (3.6) imply the desired upper bound on #Rk(x).
We now turn our attention on the lower bound for #Rk(x). We proceed
again by induction on k ≥ 1. Let c1 > 0 be the constant implied in
inequality (3.1) and let y = 2c1. Then #P(x, y) ≤ π(x)/2. Let p ≤ x be a
prime not in #P(x, y) and m ∈ Rk−1((log x)/y). Put n = m+p. Then n =
m+p < (log x)/y+p < p′, therefore p = p(n). Thus, R(n) = 1+R(m) = k.
The number of pairs (p,m) with the above properties is
≥ (π(x)−#P(x, y))#Rk−1((log x)/y)k
π(x) log x
logk−1((log x)/y)
k
x
logk x
.
Each such pair (p,m) leads to a value of n ≤ x+ (log x)/y ≤ 2x. Further-
more, distinct pairs (p,m) lead to distinct values of n, for if p+m = p1 +m1
for some (p,m) 6= (p1,m1) then, assuming say that p1 > p, we get
p′ − p ≤ p1 − p = m−m1 < m < (log x)/y,
which is impossible. Hence, p1 = p and since p + m = p1 + m1, we also
get m = m1, which is impossible since the pairs (p,m) and (p1,m1) were
distinct. Thus, we showed that #Rk(2x) k x/ logk x, which implies the
desired lower bound.
On an arithmetic function considered by Pillai 701
Acknowledgements. We thank the referee for suggestions which im-
proved the quality of the paper. Work on this paper started during a
pleasant visit of F. L. to the Harish-Chandra Research Institute in August,
2007. This author thanks the people of this institute for their hospitality
as well as the TWAS for financial support. Research of F. L. was also
supported in part by grants SEP-CONACyT 79685 and PAPIIT 100508.
References
[1] R. C. Baker, G. Harman and J. Pintz, The difference between consecutive primes - II.
Proc. London Math. Soc., (3) 83 (2001), 532–562.
[2] H. Cramér, On the order of magnitude of the differences between consecutive prime num-
bers. Acta. Arith., 2 (1936), 396–403.
[3] H. Halberstam and H. E. Rickert, Sieve methods. Academic Press, London, UK, 1974.
[4] G. Hoheisel, Primzahlprobleme in der Analysis. Sitzunsberichte der Königlich Preussischen
Akademie der Wissenschaften zu Berlin, 33 (1930), 3–11.
[5] T. R. Nicely, Some Results of Computational Research in Prime Numbers.
http://www.trnicely.net/
[6] S. S. Pillai, An arithmetical function concerning primes. Annamalai University J. (1930),
159–167.
[7] R. Sitaramachandra Rao, On an error term of Landau - II in “Number theory (Winnipeg,
Man., 1983)”, Rocky Mountain J. Math. 15 (1985), 579–588.
Florian Luca
Mathematical Institute
UNAM, Ap. Postal
61-3 (Xangari), CP 58089
Morelia, Michoacán, Mexico
E-mail: fluca@matmor.unam.mx
Ravindranathan Thangadurai
Harish-Chandra Research Institute
Chhatnag Road, Jhunsi
Allahabad 211 019, India
E-mail: thanga@mri.ernet.in


On an arithmetic function considered by Pillai

Anitha Srinivasan

Markoff numbers and ambiguous classes

David J. Grynkiewicz

Luz E. Marchan

Oscar Ordaz

Representation of finite abelian group elements by subsequence sums

Karim Belabas

Mark van Hoeij

Jürgen Klüners

Allan Steel

Factoring polynomials over global fields

John Cullinan

Farshid Hajir

Elizabeth Sell

Algebraic properties of a family of Jacobi polynomials

Evelina Viada

The optimality of the Bounded Height Conjecture

Régis de la Bretèche

Fonctions zêta des hauteurs

Luis Dieulefait

Xavier Taixés i Ventosa

Congruences between modular forms and lowering the level mod $\ell ^n$

Not a member yet