ON GENERALIZATIONS OF PROBLEMS OF
RECAMAN AND POMERANCE
L. HAJDU AND N. SARADHA
Abs ac . Answe ing a ques ion o Balasub amanian, we ind all
p imes p o which he e exis pconsecu i e p imes o ming a com-
ple e esidue sys em (mod p). On he o he hand, unde he p ime
ℓ- uple conjec u e we show ha o any k≥2, he e exis in in-
i ely many se s o φ(k) consecu i e p imes o ming educed esidue
classes (mod k). The p oblems conside ed a e gene aliza ions o
hose o Recaman and Pome ance, espec i ely.
1. In oduc ion
Le 2 = p1< p2<· · · deno e he sequence o all p imes. Le kand
lbe posi i e in ege s wi h gcd(k, l) = 1. Deno e by p(k, l) he leas
p ime p≡l(mod k). We w i e P(k) o he maximal alue o p(k, l)
o all l.
A p ime pis called a Recaman p ime, i he fi s pp imes o m a
comple e esidue sys em (mod p). Pome ance [11] showed ha he e
a e only fini ely many Recaman p imes. Recen ly, Hajdu and Sa adha
[4] p o ed ha he only Recaman p ime is p= 2. An in ege k≥2 is
called a P-in ege , i he fi s φ(k) p imes cop ime o k o m a educed
esidue sys em (mod k). Pome ance [11] p o ed ha he e exis only
fini ely many P-in ege s. Unde ce ain condi ions, Hajdu and Sa adha
[4] and [13] de e mined all P-in ege s. Hajdu, Sa adha and Tijdeman
[5] p o ed ha i kis a Pin ege , hen k≤103500, and ha i he
Riemann Hypo hesis is ue, hen he only P-in ege s a e gi en by
k= 2,4,6,12,18,30. Finally, his was uncondi ionally e ified by Yang
and Togb´e [14].
A e he alk o he fi s au ho in he DMANT 2015 mee ing, Bal-
asub amanian p oposed he a ia on o he abo e p oblems whe e he
2010 Ma hema ics Subjec Classi ica ion. 11N13.
Key wo ds and ph ases. Recaman’s p oblem, Pome ance’s p oblem, p imes in
esidue classes.
Resea ch suppo ed in pa by he OTKA g an s K100339, K115479 and
NK101680.
1
2 L. HAJDU AND N. SARADHA
fi s k( esp. φ(k)) p imes a e eplaced by any block o k( esp. φ(k))
consecu i e p imes.
To be mo e p ecise, we in oduce some new defini ions. An in ege
kis called a B-p ime i he e exis kconsecu i e p imes o ming a
comple e esidue sys em (mod k). Fu he , an in ege kis called a B-
in ege , i he e exis φ(k)consecu i e p imes o ming a educed esidue
sys em (mod k).
No e ha he Recaman p ime 2 is a B-p ime also. Fu he he
P-in ege s 2,4,6,12,18,30 a e also B-in ege s. When a p ime kis a
B-p ime, we ha e
(1) P(k)≤pπ(k)+k−1.
F om well known es ima es in P ime Numbe Theo y, i is clea ha
pπ(k)+k−1≪klog k. In ac , he implici cons an lies be ween 1 and
1.04 o k≥1093.This leads us o make a mo e gene al defini ion as
ollows. We say ha a p ime kis a shi ed Pα-p ime i he e exis
kp imes no exceeding αk log k o ming a comple e esidue sys em.
Finally, an in ege kis called a shi ed Pα-in ege i he e exis φ(k)
p imes no exceeding αk log k o ming a educed esidue sys em (mod
k).
In his pape , we show ha he only B-p imes a e 2,3,7 and he e
is no shi ed Pα-p ime wi h α= 1.1954. Pome ance [11, Theo em 2]
showed ha i kis any posi i e in ege , hen
P(k)≥(eγ+o(1))φ(k) log k
whe e φdeno es he Eule o ien unc ion, and γ= 0.577 . . . is Eule ’s
cons an . In pa icula when kis a p ime, his gi es
P(k)≥(eγ+o(1))klog k.
He e he implied cons an is no explici and may be e y small. By
Theo em 2.2 below, we see ha
P(k)>1.1954klog k
o all p imes k. I appea s ha one needs o ake k > 101010 ,in o de
o ge
P(k)≥eγklog k
by he me hod in his pape .
Finding uppe bound o P(k) is a well known p oblem. Linnik [8]
showed ha
P(k)≤ckL
whe e cand La e effec i ely compu able cons an s. The e is a huge
li e a u e on finding he bes cons an L.
GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 3
In 1992, Hea h-B own [6] had shown ha Lcan be aken as 5.5.
This has been imp o ed o 5 by Xylou is [16] (see Theo em 2.1, p. 12)
in 2011. A conjec u e o Chowla [1] says ha Lis 1 + ϵ o a bi a y
ϵ > 0.Obse e ha as αinc eases, he se o shi ed Pα-p imes (o
in ege s) becomes la ge and la ge . Unde Chowla’s conjec u e, we
see ha α(as a unc ion o k) mus be o he o de kϵso ha all
p imes (o in ege s) kmay become shi ed Pα-p imes (o in ege s). On
he o he hand, i kis a B-in ege , hen we need o find φ(k)consecu i e
p imes cop ime o k. Assuming he p ime ℓ- uple conjec u e o Ha dy
and Li lewood, we deduce ha e e y in ege kis a B-in ege , and
in ac one can choose app op ia e blocks o φ(k) consecu i e p imes
in infini ely many ways. We no e ha o k= 2,3,4,6 his asse ion
easily ollows uncondi ionally.
2. Resul s
Theo em 2.1. The only B-p imes a e gi en by 2,3,7.
Theo em 2.2. The e is no shi ed Pα-p ime wi h α= 1.1954.
The abo e wo esul s a e con ained in he ollowing heo em.
Theo em 2.3. Le kbe a p ime wi h he p ope y ha he e exis k
p imes no exceeding max(pπ(k)+k−1,1.1954klog k)which o m a com-
ple e esidue sys em. Then k∈ {2,3,7,11}.
To ge he asse ions o Theo ems 2.1 and 2.2 we fi s deduce ha
(2) max(pπ(k)+k−1,1.1954klog k) = {pπ(k)+k−1,i k < 6691068
1.1954klog k, o he wise.
Fu he we find ha 2,3,7 a e B-p imes since
{2,3},{3,5,7},{7,11,13,17,19,23,29}
o m comple e esidue sys ems, espec i ely. Also 2,3,7 a e no shi ed
Pα-p imes wi h α= 1.1954 since π(1.1954klog(k)) < k in hese cases.
Fu he , 11 is no a B-p ime, since no se o 11 consecu i e p imes
o ms a comple e esidue sys em (mod 11).
Using he a gumen in he p oo o [4, Theo em 2], one may ob ain
he ollowing esul which we s a e wi hou p oo .
Le αbe a fixed posi i e numbe . Suppose kis a shi ed Pα-in ege
wi h he leas p ime ac o o kexceeding log(k).Then he e exis s
an effec i ely compu able numbe c(α)depending only on αsuch ha
k < c(α).
4 L. HAJDU AND N. SARADHA
The abo e esul leads us o specula e i he e a e only fini ely many
B-in ege s. We show below ha he con a y is ue unde he p ime
ℓ- uple conjec u e o Ha dy and Li lewood. In ac , assuming he
conjec u e we deduce ha e e y in ege kis a B-in ege , and one can
choose app op ia e blocks o φ(k) consecu i e p imes in infini ely many
ways. We no e ha o k= 2,3,4,6 his asse ion easily ollows un-
condi ionally.
Be o e o mula ing ou nex heo em, we ecall he p ime ℓ- uple
conjec u e. A fini e se Ao in ege s is called admissible, i o any
p ime p, no subse o A o ms a comple e esidue sys em (mod p).
Conjec u e 2.1 (The p ime ℓ- uple conjec u e).
Le {a1, . . . , aℓ}be an admissible se o in ege s. Then he e exis
infini ely many posi i e in ege s nsuch ha n+a1, . . . , n +aℓa e all
p imes.
Rema k. By a ecen , deep esul o Mayna d [9] we know ha o each
ℓ, he abo e conjec u e holds o a posi i e p opo ion o admissible ℓ-
uples.
Theo em 2.4. Suppose ha he p ime ℓ- uple conjec u e is ue. Then
o e e y in ege k≥2one can find infini ely many se s o φ(k)con-
secu i e p imes o ming a educed esidue sys em (mod k).
Rema k. In ac , in he p oo o Theo em 2.4 we need he numbe s n+
a1, . . . , n+aℓoccu ing in he p ime ℓ- uple conjec u e o be consecu i e
p imes. In case o ℓ= 2, by deep and celeb a ed esul s o Zhang [17]
and Pin z [10] we know his o be ue o infini ely many admissible
se s {a1, a2}, e en wi h a1= 0. In case o gene al ℓ, such a a ian is
known o ollow om he ollowing quan i a i e e sion o he p ime
ℓ- uple conjec u e, also made by Ha dy and Li lewood. Le A0=
{a1, . . . , aℓ}be an admissible se wi h a1< a2<···< aℓ.Pu
I0={n∈N:a1≤n≤aℓ}and A′
0=I0 A0.
Fo e e y p ime ple pbe he numbe o esidue classes (mod p) me
by A0.Clea ly, o all pwe ha e 1 ≤ p≤p−1. Pu
δA0:= ∏
pp ime
1− p
p
(1−1
p)ℓ.
No e ha he e he p oduc on he igh hand side is con e gen o any
admissible se . Fu he i A0⊆B, hen δA0≥δB.Le
S={n∈N:n+a1,· · · , n +aℓa e all p imes}
GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 5
and
S(X) = {n∈S:n≤X}.
Then he quan i a i e e sion o he p ime ℓ- uple conjec u e o Ha dy
and Li lewood asse s ha
|S(X)|= (δA0+o(1)) X
(log X)ℓ.
Now we explain how his implies ha he e a e infini ely many in ege s
n o which n+a1,··· , n +aℓa e all consecu i e p imes. Le
S1={n∈S:n+a1,· · · , n +aℓa e no consecu i e p imes}.
I is enough o show ha
|S1(X)|=o(X
(log X)ℓ).
I n∈S1, hen he e exis s a∈A′
0such ha n+ais p ime. Also
A(a)
0:= A0∪ {a}is an admissible se . Fo a∈A′
0, le
S(a)
1={n∈S1:n+a1,··· , n +aℓ, n +aa e all p imes}.
Then
S1=∪
a∈A′
0
S(a)
1.
Thus
|S1(X)| ≤ ∑
a∈A′
0
(δA(a)
0+o(1)) X
(log X)ℓ+1
≤(δA0+o(1))(aℓ−a1)X
(log X)ℓ+1 =o(X
(log X)ℓ)
o X→ ∞ as desi ed. Howe e , in he p oo o Theo em 2.4 we a oid
he use o he quan i a i e e sion o he conjec u e. In ac , we apply
an elemen a y a gumen showing ha he p ime ℓ- uple conjec u e i -
sel implies he exis ence o infini ely many nsuch ha he numbe s
n+a1, . . . , n +aℓa e consecu i e p imes.
As a simple co olla y o Theo em 2.4, we ob ain
Co olla y 2.1. Suppose ha he p ime ℓ- uple conjec u e is ue. Then
e e y in ege k≥2is a B-in ege .
Rema k. I is ob ious ha 2 is a B-in ege . Since o k= 3,4,6
he e a e only wo cop ime esidue classes, and bo h classes con ain
infini ely many p imes, he e mus be infini ely many “swi ches” be-
ween hese classes in pai s o consecu i e p imes. Hence k= 3,4,6
a e (uncondi ionally) also B-in ege s.

6 L. HAJDU AND N. SARADHA
In iew o he abo e ema ks and heo ems, we p opose he ollowing
Conjec u e 2.2. E e y in ege k≥2is a B-in ege .
3. Lemmas
The p oo o Theo em 2.3 ollows simila line o a gumen s as he
p oo o [4, Theo em 2]. We eco d he e h ee lemmas necessa y o
he p oo . The fi s lemma is om Rosse and Schoen eld [12].
Lemma 3.1. Le pndeno e he n- h p ime. Then
(i)pn> n(log(n) + log2(n)−3
2) o n > 1;
(ii)pn< n(log(n) + log2(n)) o n≥6.
He e and hence o h, log2(n) deno es log log(n) o any eal numbe
n > 1. Fo n≥1 he Jacobs hal unc ion g(n) is defined as he smalles
in ege such ha any sequence o g(n) consecu i e in ege s con ains an
elemen which is cop ime o n. This unc ion has been s udied by many
au ho s, and good lowe as well as uppe bounds a e known (see e.g.
[7], [15], [11], [3] and [2] o some esul s and his o y). Fu he , he
exac alues o g(n) when nis he p oduc o he fi s h < 50 p imes
is gi en in [3, Table 1].
I was obse ed by Jacobs hal ha o in ege s kwi h ℓ(k)>log(k)
we ha e g(k) = ω(k) + 1 whe e ℓ(k) is he leas p ime di iso o k,
and ω(k) is he numbe o dis inc p ime di iso s o k. In pa icula
his is ue i kis a p ime i.e., g(k) = 2 in his case. Fu he , g(k)≥
ω(k) + 1 is ob iously alid o any k. We shall use hese asse ions
h oughou he pape wi hou any u he e e ence. The ollowing
lemma is P oposi ion 1.1 o Hagedo n [3].
Lemma 3.2. We ha e
g(h
∏
i=1
pi)≥2ph−1 o h > 2.
The nex esul due o Pome ance [11] is an impo an ing edien in
his p oblem.
Lemma 3.3. Le kand mbe in ege s wi h 0< m ≤k
1+g(k)and
gcd(m, k) = 1. Then P(k)>(g(m)−1)k.
4. P oo s
P oo o Theo em 2.3. We es ic o kp ime so ha g(k) = 2.Fi s
ake k≥1093.By (2),
max(pπ(k)+k−1,1.1954klog k) = 1.1954klog k.
GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 7
Pu
h=⌊0.9688 log(k)
log2(k)⌋+ 1.
Then
h < 0.9946 log(k)
log2(k)
gi ing
log(h)<log2(k)−log3(k) and log2(h)<log3(k).
This by Lemma 3.1 (ii) implies
ph<0.9946 log(k)<log(k).
Le mbe he p oduc o he fi s hp imes cop ime o k. Since ph<
log(k)< k, we see ha mis indeed he p oduc o all he fi s hp imes.
Hence
m < ph
h< e0.9946 log(k)<k
3.
Thus by Lemmas 3.2 and 3.3, we ha e
P(k)>(g(m)−1)k≥(2ph−1−1)k.
Now
h−1≥0.9688 log(k)
log2(k)−1>0.943 log(k)
log2(k).
Hence by Lemma 3.1 (i)
ph−1≥X(log(X) + log2(X)−3
2)
whe e X= 0.943 log(k)
log2(k). Le
F(k) = 2X(log(X) + log2(X)−3
2−1
2X)k−1.1954klog(k).
Then F(k) = klog(k) (k) wi h
(k) := 1.886
log2(k)(log(X) + log2(X)−3
2−1
2X)−1.1954.
Obse e ha (k) is an inc easing unc ion o kand hence (k)≥
(1093), since k≥1093. As (1093)≥0.0005, we find ha F(k)>0
which implies ha P(k)>1.1954klog k. Hence kis no a Pα-p ime
wi h α= 1.1954.This p o es he heo em o k≥1093.
Nex conside 6691068 ≤k < 1093. By (2),
max(pπ(k)+k−1,1.1954klog k) = 1.1954klog(k).
8 L. HAJDU AND N. SARADHA
Suppose k∈[1043,1093).The la ges in ege hsuch ha ph<log(1043)
is 25. Taking
m=
25
∏
j=1
pj,
we find ha gcd(m, k) = 1 and
m < 1043
3≤k
g(k) + 1.
F om [3, Table 1], g(m) = 258.Hence by Lemma 3.3,
P(k)>257k > 1.1954 ×93 log(10)k > 1.1954 ×klog(k).
This p o es he p oposi ion o k∈[1043,1093).Le k∈[10a,10b).In
Table 1, we gi e he alues o (a, b), h, he exac alue o g(m) om [3,
Table 1] whe e m=∏h
i=1 piso ha
ph<log(10a), P (k)>1.1954klog(k).
Then he asse ion o he heo em ollows o kin his in e al. Thus
h7 8 9 11 14 18
g(m) 26 34 40 58 90 132
(a, b) (8,9) (9,10) (10,14) (14,19) (19,27) (27,43)
Table 1. Values o h,g(m) and (a, b).
we conclude ha k < 108.Fu he , we ake k∈[6691068,108) wi h
h= 7, g(m) = 26 o ge he asse ion o he heo em.
Nex , we ake 90107 ≤k < 6691068.In his case, we find ha
pπ(k)+k−1<1.25klog(k).Then we ake h= 6, g(m) = 22 o exclude
hese alues o kby Lemma 3.3.
Thus k < 90107.Fo hese alues o kwe gi e a compu a ional
a gumen . Le kbe fixed. Suppose Skdeno es he se o esidues mod
ko all he p imes up o pπ(k)+k−1.I
(3) |Sk|=k
hen, kmay be a B-p ime. We check ha (3) is alid only o k=
2,3,7,11.Fu he 11 is no a B-p ime as he e is no se o 11 consecu-
i e p imes among he fi s 15 p imes which yields a comple e esidue
sys em. On he o he hand, 2,3,7 gi e consecu i e p imes o ming a
comple e esidue sys em as men ioned in Sec ion 2. This p o es he
heo em. 
GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 9
P oo o Theo em 2.4. Le k≥2 be an a bi a y in ege . We shall
show ha unde he p ime ℓ- uple conjec u e, kis a B-in ege i.e.,
he e exis s φ(k) consecu i e p imes o ming a educed esidue sys em
mod k. Le A={a1, . . . , aφ(k)}be he se o all posi i e in ege s
cop ime o kwi h
1 = a1<···< aφ(k)< k.
The se Amay no be an admissible se . We cons uc an admissible
se ou o Aas ollows. Pu
P=∏
p−p ime
p-k,p≤φ(k)
p.
Le B={b1, . . . , bφ(k)}be a se o posi i e in ege s such ha
(4) b1=a1= 1; bi≡ai(mod k) and bi≡1 (mod P) ( o i≥2).
Fi s ly, no e ha such bi’s exis by he Chinese Remainde Theo em.
Nex we show ha Bis an admissible se . Since |B|=φ(k) and
Bcon ains in ege s cop ime o k, i is enough o es ic o p imes
p≤φ(k) and p-k. Then by (4), e e y bi≡1(mod p),hence Bcanno
ha e a comple e esidue sys em (mod p).By applying he p ime ℓ- uple
conjec u e o B, we find infini ely many n > k o which
n+b1,· · · , n +bφ(k)
a e all p imes and hence cop ime o k. Bu hese p imes may no be
consecu i e p imes. To ensu e his, we p oceed as ollows. Le
M= max
b∈Bb
and I he se o posi i e in ege s nwi h n≤M. Fu he le
C={c∈I B:B∪ {c}is admissible}.
Le =|C|and w i e C′=I (B∪C).Thus o c′∈C′, B ∪ {c′}is
no an admissible se . Hence he e exis s a p ime p≤Msuch ha
B∪ {c′}has a comple e esidue sys em (mod p).
No e ha M > k by (4). We cons uc an admissible se S⊇B,
such ha S∪ {c}is no admissible o any c∈C. I = 0 hen ake
S=B. I ≥1, ake p imes q1<· · · < q exceeding Mand pu
Q=∏
p<q1+···+q
p.
Le us enume a e he elemen s o Cas c1, . . . , c .Co esponding o each
ci,we cons uc a se D(i)as ollows. Le d(i)
1sa is y
d(i)
1> M, d(i)
1≡1(mod Q
qi)and d(i)
1(mod qi)∈ B∪ {ci}.