On a problem of Recaman and its generalization

On a p oblem o Recaman and i s gene aliza ion L. Hajdu and N. Sa adha Uni e si y o Deb ecen, Ins i u e o Ma hema ics and he Numbe Theo y Resea ch G oup o he Hunga ian Academy o Sciences Deb ecen, Hunga y 1 School o Ma hema ics, Ta a Ins i u e o Fundamen al Resea ch D . Homibhabha Road, Colaba, Mumbai, India Abs ac We sol e some cases o a conjec u e o Pome ance conce ning educed esidue sys- ems modulo kconsis ing o he i s φ(k) p imes no di iding k. We co e he case when kis a p ime, hus gi ing a comple e solu ion o a p oblem o Recaman. Key wo ds: he p oblem o Recaman, he p oblem o Pome ance, Jacobs hal unc ion, p imes in esidue classes PACS: 11N13 Dedica ed o P o esso K. Gy˝o y on he occasion o his 70 h bi hday 1 In oduc ion Le k > 1 be an in ege and deno e by φ(k) Eule ’s o ien unc ion. We say ha kis a P-in ege i he fi s φ(k) p imes cop ime o k o m a educed esidue sys em modulo k. No e ha a p ime pis a P-in ege i and only i he fi s pp imes o m a comple e esidue sys em modulo p. In 1980, Pome ance [3] showed ha he e a e only fini ely many P-in ege s. The eby he quali a i ely sol ed he p oblem o fini ely many p ime P-in ege s which was aised ea lie in 1978 by Recaman [4]. In his pape Pome ance conjec u ed ha he la ges Email add esses: [email p o ec ed],[email p o ec ed] (L. Hajdu and N. Sa adha). 1Resea ch suppo ed in pa by he Hunga ian Academy o Sciences, by he OTKA g an s K67580 and K75566, and by he g an T´ AMOP 4.2.1./B. P-in ege is k= 30. I is easy o check ha he only P-in ege s less han o equal o 30 a e k= 2,4,6,12,18,30. In his pape we p o e he conjec u e o Pome ance in wo “opposi e” ex- emal cases: when kis composed o “la ge” p ime ac o s (i.e. when all he p ime di iso s o ka e abo e log(k)), and when kis composed o “small” p ime ac o s (i.e. kis he p oduc o all p imes ≤x o some x). As a i ial consequence o he fi s esul we ge a comple e quan i a i e solu ion o he p oblem o Recaman. Fu he , we e i y he conjec u e o Pome ance o all k < 5.5·105. We no e ha Pome ance’s fini eness esul o P-in ege s [3] in p inciple can be made effec i e: one can possibly ge an explici uppe bound o P-in ege s k. Howe e , acco ding o ou calcula ions, his bound is a he huge, and i seems ha o co e he emaining gap some addi ional ( heo e i- cal and/o compu a ional) a gumen s a e needed. So he comple e esolu ion o he p oblem o Pome ance s ill emains an open ques ; we plan o a ack i in a u u e pape . The p oo s o ou esul s depend on some p ope ies o he Jacobs hal unc ion g(m) as in [3]. Among o he s we use he exac alues o g(m) when mis he p oduc o fi s h≤46 p imes, which we e ecen ly ob ained by Hagedo n [1]. Fu he , we apply se e al o mulas o Rosse and Schoen eld [5], conce ning a ious unc ions in ol ing p imes. 2 Main esul s Ou fi s esul sol es Recaman’s p oblem comple ely. Theo em 1 The only p ime P-in ege is 2. In ac Theo em 1 is a i ial consequence o he ollowing much mo e gene al esul . Fo k > 1 le ℓ(k) be he leas p ime di iso o k. Theo em 2 Le k > 1be an in ege wi h ℓ(k)>log(k). Then kis a P-in ege i and only i k∈ {2,4,6}. Fo fixed posi i e in ege and posi i e eal Xw i e N := {n|ω(n) = }and N (X) := {n∈N |n≤X}, whe e ω(n) deno es he numbe o dis inc p ime di iso s o n. Fu he , o any posi i e eal x, we le log1(x) = log(x) and o ≥2, log (x) = log(log −1(x)). 2 By a esul o Landau i is known ha |N (X)| ∼ X(log2(X)) −1 log(X)( −1)! (see Theo em 437, p. 368 o [2]). Le N′ (X) deno e he se o in ege s n in N (X) wi h ℓ(n)≤log(n). Then o any n∈N′ (X) we ha e ℓ(n)≤ log(X) and n/ℓ(n)∈N −1(X/ℓ(n)). Applying Landau’s esul o N −1(X/p) o e e y p≤log(X), and no ing ha (log2(x)) −2 log(x)is a dec easing unc ion o x o sufficien ly la ge x, we find ha |N′ (X)| ≤ c1∑ p≤log(X) X p(log2(X p)) −2 log (X p)( −2)! ≤c2 X(log2(X)) −2 log(X)( −2)! ∑ p≤log(X) 1 p≤ ≤c3 X(log2(X)) −2 log(X)( −2)! log3(X) whe e c1,c2and c3a e absolu e cons an s. Thus we see ha almos all in ege s in N has ℓ(n)>log(n). In pa icula , kis no a P-in ege whene e kis he p oduc o win p imes. Ou hi d heo em e ifies he conjec u e o Pome ance o in ege s kbeing he p oduc s o he fi s ew p imes. Theo em 3 Le kbe he p oduc o he p imes ≤x o some x≥2. Then k is a P-in ege i and only i k∈ {2,6,30}. Finally, we o mula e a s a emen conce ning he solu ion o he p oblem o Pome ance o “small” alues o k. Ou main mo i a ion o doing so is ha his esul will be e y use ul in he p oo o Theo em 2. P oposi ion 4 Suppose ha 1< k < 5.5·105. Then kis a P-in ege i and only i k∈ {2,4,6,12,18,30}. 3 Lemmas We need many lemmas o diffe en ypes o p o e ou heo ems. We shall make use o se e al es ima es o Rosse and Schoen eld [5] conce ning a ious unc ions ela ed o p ime numbe s. Fu he , we need ce ain esul s due o S e ens [6] and Hagedo n [1] abou he Jacobs hal unc ion. Finally, we need a heo em o Pome ance abou p imes in esidue classes modulo m. 3 3.1 Lemmas conce ning unc ions in ol ing p imes The ollowing ou lemmas a e es ima es om Rosse and Schoen eld [5] which we need la e on. Lemma 5 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. Lemma 6 Fo any x≥59 we ha e x log(x)(1 + 1 2 log(x))< π(x)<x log(x)(1 + 3 2 log(x)). Lemma 7 Fo x≥2w i e ϑ(x) = ∑ p≤x log(p). Fo any x≥563 we ha e x(1−1 2 log(x))< ϑ(x)< x (1 + 1 2 log(x)). Lemma 8 Fo any x > 1we ha e ∏ p≤x(1−1 p)<0.56146 log(x)(1 + 1 2 log2(x)). No e ha he e 0.56146 could be eplaced by any numbe exceeding e−γ, whe e γis Eule ’s cons an . 3.2 Lemmas abou he Jacobs hal unc ion 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. [6], [3] and [1] o 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 Table 1 o [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. 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. Ou fi s lemma conce ning he Jacobs hal unc ion is a e o mula ion o he Theo em o S e ens [6]. 4 Lemma 9 We ha e g(k)≤2ω(k)2+2elog(ω(k)) o all k > 1. The nex lemma is P oposi ion 1.1 o Hagedo n [1]. Lemma 10 We ha e g(h ∏ i=1 pi)≥2ph−1 o h > 2. 3.3 A esul o Pome ance 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. Obse e ha kis a P-in ege i and only i P(k) equals he φ(k)- h p ime no di iding k. Since he numbe o p imes di iding kis ω(k), we ge ha i kis a P-in ege hen pφ(k)≤P(k)≤pφ(k)+ω(k) holds. No e also ha since φ(k) + ω(k)≤k, we ha e P(k)≤pkwhene e k is a P-in ege . To p o e he fini eness o k’s which a e P-in ege s, Pome ance [3] de i ed a lowe bound o P(k) which ( o la ge k) u ns o be la ge han s anda d uppe bounds o pφ(k)+ω(k), ob ained by using es ima es om [5]. This lowe bound o Pome ance is based upon he ollowing esul om [3]. Lemma 11 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 Since in he p oo o Theo em 2 we use P oposi ion 4, we s a wi h he p oo o he la e esul . P oo o P oposi ion 4. Le kbe a bi a y wi h 1 < k < 5.5·105. Le q1< q2< q3< . . . be he p imes > k wi h = 1 i kis e en and = 2 i kis odd, espec i ely. We find he fi s index isuch ha qi− k is a p ime. Fo all kin he conside ed in e al we ound i≤34. I k+ 2 is a p ime hen le q=k+ 2, o he wise se q=qiwi h he abo e defined index i. A calcula ion wi h Maple based upon Lemma 5 ensu es ha o k > 210 we ha e q≤pφ(k). Thus he e exis wo p imes ≤pφ(k)being cop ime o kin he same esidue class modulo k, which p o es ha kis no a P-in ege in his case. Finally, o k≤210 we 5 check by Maple he fi s φ(k) p imes no di iding k o ge he asse ion o he p oposi ion. 2 P oo o Theo em 2. Le kbe a P-in ege wi h ℓ(k)>log k. Assume fi s ha k≥1090. We spli he p oo o his case in o wo pa s. Suppose fi s ha k < (ω(k)+2)20. Then, since we know ha ω(k) log(ℓ(k)) ≤log(k), we ob ain ω(k)≤log(k) log2(k). Hence using ou assump ion o kwe ge k < (log(k) log2(k)+ 2)20 . This implies ha k < 1090, which is a con adic ion, and he s a emen ollows in his case. Suppose nex ha we ha e k≥(ω(k) + 2)20. Le h=⌊0.92 log(k) log2(k)⌋+ 1. Then h < 0.946 log(k) log2(k)<log(k). Hence by Lemma 5 (ii) ph<0.946 log(k)<log(k). Le mbe he p oduc o he fi s hp imes cop ime o k. Since ph<log(k)< ℓ(k), by assump ion, we see ha mis indeed he p oduc o all he fi s h p imes. Hence m < ph h< e0.946 log(k)<k ω(k)+2 since we assumed ω(k)+2≤k1 20 . Thus by Lemmas 10 and 11, we ha e P(k)>(g(m)−1)k≥(2ph−1−1)k. Now h−1≥0.92 log(k) log2(k)−1>0.894 log(k) log2(k). Hence by Lemma 5 (i) ph−1≥X(log(X) + log2(X)−3 2) 6 whe e X= 0.894 log(k) log2(k). Le F(k) = 2X(log(X) + log2(X)−3 2)k−klog(k)−klog2(k)−k. Then F(k) = klog(k) (k) wi h (k) := 1.788 log2(k)(log(X) + log2(X)−3 2)−1−log2(k) log(k)−1 log(k). Obse e ha (k) is an inc easing unc ion o kand hence (k)≥ (1090), since k≥1090. As (1090)≥0.0803, we find ha F(k)>0 which implies ha P(k)> k log(k)+klog2(k)> pk≥pφ(k)+ω(k). Hence kis no a P-in ege . This con adic ion p o es he heo em o k≥1090 wi h ℓ(k)>log(k). Assume now ha k < 1090. By P oposi ion 4 we may suppose ha 5.5·105≤ k < 1090. We di ide he in e al [5.5·105,1090) in o sub-in e als and assign a alue h o each in e al as ollows. Le 0= 1090. The la ges in ege h such ha ph<log(1090) is 46. We se ou ini ial sub-in e al as [u0, 0) = [1087,1090), α0= 87 and h0=h= 46. Fo any kwi h ℓ(k)>log(k) in his in e al we ha e g(k) = ω(k)+1<log(k) + 1 <209. We check ha m0:= 46 ∏ j=1 pj<1087 210 ≤k g(k)+1. Now we p oceed induc i ely. Le i≥1 and ake hi=h0−i. We define he sub-in e al [ui, i) as [10αi,10αi−1) sa is ying he ollowing p ope ies: phi< αilog(10) (1) and mi:= h0−i ∏ j=1 pj<10αi (αi−1log(10) + 2).(2) Le k∈[ui, i) wi h ℓ(k)>log(k). Then phi<log(k) and hence by he assump ion on k,miis he p oduc o he fi s hip imes, and gcd(mi, k) = 1. Suppose ha g(mi)−1−αi−1log(10) −log(αi−1log(10)) >0.(3) Then, since k≤10αi−1, we find by Lemma 11 and Lemma 5 (ii) ha P(k)> k log(k) + klog2(k)> pk≥pφ(k)+ω(k) and hence k∈[ui, i) is no a P-in ege . In Table 1 we gi e he alues hi=h,αi=α, and he exac alue o g(m) wi h m=mi om Table 1 o [4]. Fo hese alues, we check ha (1), (2) 7 and (3) a e sa isfied and hence we conclude ha k < 108. Now conside kin Table 1 h7 8 9 10 11 12 13 14 15 16 g(m) 26 34 40 46 58 66 74 90 100 106 α8 9 10 13 14 17 18 19 21 24 h17 18 19 20 21 22 23 24 25 26 g(m) 118 132 152 174 190 200 216 234 258 264 α26 27 30 31 32 35 37 39 43 44 h27 28 29 30 31 32 33 34 35 36 g(m) 282 300 312 330 354 378 388 414 432 450 α45 47 48 55 56 57 60 61 65 66 h37 38 39 40 41 42 43 44 45 46 g(m) 476 492 510 538 550 574 600 616 642 660 α69 71 73 76 78 79 83 84 86 87 he in e als [3 ·107,108) wi h h= 7 and [5.5·105,3·107) wi h h= 6 and g(m) = 22, espec i ely. Then condi ions (1), (2) and (3) a e sa isfied again, showing ha kis no a P-in ege . Hence he s a emen ollows. 2 P oo o Theo em 3. Assume fi s ha x≥1000 and pu k=∏ p≤x p. Se m:= ∏ x<p≤y pwi h y= 1.777x. Fi s we show ha by hese choices we ha e m≤k/(1 + g(k)). This inequali y can be ew i en as 1 + g(k)≤exp(2ϑ(x)) exp(ϑ(y)) . Using Lemma 9, i is sufficien o show ha 1+2π(x)2+2elog(π(x)) ≤exp(2ϑ(x)−ϑ(1.777x)). Wi h he help o Maple, by Lemmas 6 and 7 his can be seen o be ue whene e x≥12000. Fo 1000 ≤x < 12000 he asse ion can be checked by calcula ing he exac alues o he unc ions π(x) and ϑ(x). Now we show ha (s ill wi h x≥1000) we ha e (g(m)−1)k≥pφ(k)+ω(k). By Lemma 11 his implies he s a emen . To p o e his, obse e ha g(m)> 8 ω(m) = π(y)−π(x). Hence using Lemma 5 (ii) i is sufficien o check ha π(1.777x)−π(x)≥  ∏ p≤x(1−1 p)+π(x) ∏ p≤x p  (ϑ(x) + log(ϑ(x))) o x≥1000. Again, by he help o Lemmas 6, 7 and 8 his inequali y can be e ified o x≥12000 wi h Maple. Fu he , o 1000 ≤x < 12000 he asse ion can be p o ed by calcula ing he exac alues o he exp essions in ol ed. Hence he s a emen is alid when x≥1000. Assume now ha x < 1000. Then we check he alues o kone by one. Fo k gi en, le q1=pπ(k)+1 and q2=pπ(k)+2. A calcula ion by Maple shows ha o k > 30 we ha e q2≤pφ(k)+ω(k), and also ha one o q1−k,q2−kis a p ime. Finally, as k= 2,6,30 a e P-in ege s indeed, he s a emen ollows. 2 5 Acknowledgemen The au ho s hank he e e ee o he use ul and help ul ema ks and sugges- ions. The au ho s a e g a e ul o P o esso C. Pome ance o d awing hei a en ion o his pape [3] whe e he p oblems conside ed in his pape a e posed. The second au ho also hanks P o esso K. Gy˝o y o his kind hospi- ali y du ing he isi o Deb ecen, Hunga y in No embe , 2009. Re e ences [1] T. R. Hagedo n,Compu a ion o Jacobs hal’s unc ion h(n) o n < 50, Ma h. Comp. 78 (2009), 1073–1087. [2] G. H. Ha dy, E. M. W igh ,An In oduc ion o he Theo y o Numbe s, Fi h Edi ion, Ox o d Uni e si y P ess, 1981. [3] C. Pome ance,A no e on he leas p ime in an a i hme ic p og ession, J. Numbe Theo y 12 (1980), 218–223. [4] B. M. Recaman,P oblem 672, J. Rec ea ional Ma h. 10 (1978), 283. [5] J. B. Rosse , L. Schoen eld,App oxima e o mulas o some unc ions o p ime numbe s, Illinois J. Ma h. 6(1992), 64–94. [6] H. S e ens,On Jacobs hal’s g(n) unc ion, Ma h. Ann. 226 (1977), 95–97. 9