On generalizations of problems of Recaman and Pomerance

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}.