On generalizations of problems of Recaman and Pomerance

ON GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE L. HAJDU AND N. SARADHA Abstract. Answering a question of Balasubramanian, we find all primes pfor which there exist pconsecutive primes forming a complete residue system (mod p). On the other hand, under the prime ℓ-tuple conjecture we show that for any k≥2, there exist infinitely many sets of φ(k) consecutive primes forming reduced residue classes (mod k). The problems considered are generalizations of those of Recaman and Pomerance, respectively. 1. Introduction Let 2 = p1< p2<· · · denote the sequence of all primes. Let kand lbe positive integers with gcd(k, l) = 1. Denote by p(k, l) the least prime p≡l(mod k). We write P(k) for the maximal value of p(k, l) for all l. A prime pis called a Recaman prime, if the first pprimes form a complete residue system (mod p). Pomerance [11] showed that there are only finitely many Recaman primes. Recently, Hajdu and Saradha [4] proved that the only Recaman prime is p= 2. An integer k≥2 is called a P-integer, if the first φ(k) primes coprime to kform a reduced residue system (mod k). Pomerance [11] proved that there exist only finitely many P-integers. Under certain conditions, Hajdu and Saradha [4] and [13] determined all P-integers. Hajdu, Saradha and Tijdeman [5] proved that if kis a Pinteger, then k≤103500, and that if the Riemann Hypothesis is true, then the only P-integers are given by k= 2,4,6,12,18,30. Finally, this was unconditionally verified by Yang and Togb´e [14]. After the talk of the first author in the DMANT 2015 meeting, Balasubramanian proposed the variaton of the above problems where the 2010 Mathematics Subject Classification. 11N13. Key words and phrases. Recaman’s problem, Pomerance’s problem, primes in residue classes. Research supported in part by the OTKA grants K100339, K115479 and NK101680. 1 2 L. HAJDU AND N. SARADHA first k(resp. φ(k)) primes are replaced by any block of k(resp. φ(k)) consecutive primes. To be more precise, we introduce some new definitions. An integer kis called a B-prime if there exist kconsecutive primes forming a complete residue system (mod k). Further, an integer kis called a Binteger, if there exist φ(k)consecutive primes forming a reduced residue system (mod k). Note that the Recaman prime 2 is a B-prime also. Further the P-integers 2,4,6,12,18,30 are also B-integers. When a prime kis a B-prime, we have (1) P(k)≤pπ(k)+k−1. From well known estimates in Prime Number Theory, it is clear that pπ(k)+k−1≪klog k. In fact, the implicit constant lies between 1 and 1.04 for k≥1093.This leads us to make a more general definition as follows. We say that a prime kis a shifted Pα-prime if there exist kprimes not exceeding αk log kforming a complete residue system. Finally, an integer kis called a shifted Pα-integer if there exist φ(k) primes not exceeding αk log kforming a reduced residue system (mod k). In this paper, we show that the only B-primes are 2,3,7 and there is no shifted Pα-prime with α= 1.1954. Pomerance [11, Theorem 2] showed that if kis any positive integer, then P(k)≥(eγ+o(1))φ(k) log k where φdenotes the Euler totient function, and γ= 0.577 . . . is Euler’s constant. In particular when kis a prime, this gives P(k)≥(eγ+o(1))klog k. Here the implied constant is not explicit and may be very small. By Theorem 2.2 below, we see that P(k)>1.1954klog k for all primes k. It appears that one needs to take k > 101010 ,in order to get P(k)≥eγklog k by the method in this paper. Finding upper bound for P(k) is a well known problem. Linnik [8] showed that P(k)≤ckL where cand Lare effectively computable constants. There is a huge literature on finding the best constant L. GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 3 In 1992, Heath-Brown [6] had shown that Lcan be taken as 5.5. This has been improved to 5 by Xylouris [16] (see Theorem 2.1, p. 12) in 2011. A conjecture of Chowla [1] says that Lis 1 + ϵfor arbitrary ϵ > 0.Observe that as αincreases, the set of shifted Pα-primes (or integers) becomes larger and larger. Under Chowla’s conjecture, we see that α(as a function of k) must be of the order kϵso that all primes (or integers) kmay become shifted Pα-primes (or integers). On the other hand, if kis a B-integer, then we need to find φ(k)consecutive primes coprime to k. Assuming the prime ℓ-tuple conjecture of Hardy and Littlewood, we deduce that every integer kis a B-integer, and in fact one can choose appropriate blocks of φ(k) consecutive primes in infinitely many ways. We note that for k= 2,3,4,6 this assertion easily follows unconditionally. 2. Results Theorem 2.1. The only B-primes are given by 2,3,7. Theorem 2.2. There is no shifted Pα-prime with α= 1.1954. The above two results are contained in the following theorem. Theorem 2.3. Let kbe a prime with the property that there exist k primes not exceeding max(pπ(k)+k−1,1.1954klog k)which form a complete residue system. Then k∈ {2,3,7,11}. To get the assertions of Theorems 2.1 and 2.2 we first deduce that (2) max(pπ(k)+k−1,1.1954klog k) = {pπ(k)+k−1,if k < 6691068 1.1954klog k, otherwise. Further we find that 2,3,7 are B-primes since {2,3},{3,5,7},{7,11,13,17,19,23,29} form complete residue systems, respectively. Also 2,3,7 are not shifted Pα-primes with α= 1.1954 since π(1.1954klog(k)) < k in these cases. Further, 11 is not a B-prime, since no set of 11 consecutive primes forms a complete residue system (mod 11). Using the argument in the proof of [4, Theorem 2], one may obtain the following result which we state without proof. Let αbe a fixed positive number. Suppose kis a shifted Pα-integer with the least prime factor of kexceeding log(k).Then there exists an effectively computable number c(α)depending only on αsuch that k < c(α). 4 L. HAJDU AND N. SARADHA The above result leads us to speculate if there are only finitely many B-integers. We show below that the contrary is true under the prime ℓ-tuple conjecture of Hardy and Littlewood. In fact, assuming the conjecture we deduce that every integer kis a B-integer, and one can choose appropriate blocks of φ(k) consecutive primes in infinitely many ways. We note that for k= 2,3,4,6 this assertion easily follows unconditionally. Before formulating our next theorem, we recall the prime ℓ-tuple conjecture. A finite set Aof integers is called admissible, if for any prime p, no subset of Aforms a complete residue system (mod p). Conjecture 2.1 (The prime ℓ-tuple conjecture). Let {a1, . . . , aℓ}be an admissible set of integers. Then there exist infinitely many positive integers nsuch that n+a1, . . . , n +aℓare all primes. Remark. By a recent, deep result of Maynard [9] we know that for each ℓ, the above conjecture holds for a positive proportion of admissible ℓtuples. Theorem 2.4. Suppose that the prime ℓ-tuple conjecture is true. Then for every integer k≥2one can find infinitely many sets of φ(k)consecutive primes forming a reduced residue system (mod k). Remark. In fact, in the proof of Theorem 2.4 we need the numbers n+ a1, . . . , n+aℓoccurring in the prime ℓ-tuple conjecture to be consecutive primes. In case of ℓ= 2, by deep and celebrated results of Zhang [17] and Pintz [10] we know this to be true for infinitely many admissible sets {a1, a2}, even with a1= 0. In case of general ℓ, such a variant is known to follow from the following quantitative version of the prime ℓ-tuple conjecture, also made by Hardy and Littlewood. Let A0= {a1, . . . , aℓ}be an admissible set with a1< a2<···< aℓ.Put I0={n∈N:a1≤n≤aℓ}and A′ 0=I0\A0. For every prime plet vpbe the number of residue classes (mod p) met by A0.Clearly, for all pwe have 1 ≤vp≤p−1. Put δA0:= ∏ pprime 1−vp p (1−1 p)ℓ. Note that here the product on the right hand side is convergent for any admissible set. Further if A0⊆B, then δA0≥δB.Let S={n∈N:n+a1,· · · , n +aℓare all primes} GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 5 and S(X) = {n∈S:n≤X}. Then the quantitative version of the prime ℓ-tuple conjecture of Hardy and Littlewood asserts that |S(X)|= (δA0+o(1)) X (log X)ℓ. Now we explain how this implies that there are infinitely many integers nfor which n+a1,··· , n +aℓare all consecutive primes. Let S1={n∈S:n+a1,· · · , n +aℓare not consecutive primes}. It is enough to show that |S1(X)|=o(X (log X)ℓ). If n∈S1, then there exists a∈A′ 0such that n+ais prime. Also A(a) 0:= A0∪ {a}is an admissible set. For a∈A′ 0, let S(a) 1={n∈S1:n+a1,··· , n +aℓ, n +aare all primes}. 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)ℓ) for X→ ∞ as desired. However, in the proof of Theorem 2.4 we avoid the use of the quantitative version of the conjecture. In fact, we apply an elementary argument showing that the prime ℓ-tuple conjecture itself implies the existence of infinitely many nsuch that the numbers n+a1, . . . , n +aℓare consecutive primes. As a simple corollary of Theorem 2.4, we obtain Corollary 2.1. Suppose that the prime ℓ-tuple conjecture is true. Then every integer k≥2is a B-integer. Remark. It is obvious that 2 is a B-integer. Since for k= 3,4,6 there are only two coprime residue classes, and both classes contain infinitely many primes, there must be infinitely many “switches” between these classes in pairs of consecutive primes. Hence k= 3,4,6 are (unconditionally) also B-integers. 6 L. HAJDU AND N. SARADHA In view of the above remarks and theorems, we propose the following Conjecture 2.2. Every integer k≥2is a B-integer. 3. Lemmas The proof of Theorem 2.3 follows similar line of arguments as the proof of [4, Theorem 2]. We record here three lemmas necessary for the proof. The first lemma is from Rosser and Schoenfeld [12]. Lemma 3.1. Let pndenote the n-th prime. Then (i)pn> n(log(n) + log2(n)−3 2)for n > 1; (ii)pn< n(log(n) + log2(n)) for n≥6. Here and henceforth, log2(n) denotes log log(n) for any real number n > 1. For n≥1 the Jacobsthal function g(n) is defined as the smallest integer such that any sequence of g(n) consecutive integers contains an element which is coprime to n. This function has been studied by many authors, and good lower as well as upper bounds are known (see e.g. [7], [15], [11], [3] and [2] for some results and history). Further, the exact values of g(n) when nis the product of the first h < 50 primes is given in [3, Table 1]. It was observed by Jacobsthal that for integers kwith ℓ(k)>log(k) we have g(k) = ω(k) + 1 where ℓ(k) is the least prime divisor of k, and ω(k) is the number of distinct prime divisors of k. In particular this is true if kis a prime i.e., g(k) = 2 in this case. Further, g(k)≥ ω(k) + 1 is obviously valid for any k. We shall use these assertions throughout the paper without any further reference. The following lemma is Proposition 1.1 of Hagedorn [3]. Lemma 3.2. We have g(h ∏ i=1 pi)≥2ph−1for h > 2. The next result due to Pomerance [11] is an important ingredient in this problem. Lemma 3.3. Let kand mbe integers with 0< m ≤k 1+g(k)and gcd(m, k) = 1. Then P(k)>(g(m)−1)k. 4. Proofs Proof of Theorem 2.3. We restrict to kprime so that g(k) = 2.First take k≥1093.By (2), max(pπ(k)+k−1,1.1954klog k) = 1.1954klog k. GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 7 Put h=⌊0.9688 log(k) log2(k)⌋+ 1. Then h < 0.9946 log(k) log2(k) giving 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). Let mbe the product of the first hprimes coprime to k. Since ph< log(k)< k, we see that mis indeed the product of all the first hprimes. Hence m < ph h< e0.9946 log(k)<k 3. Thus by Lemmas 3.2 and 3.3, we have 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) where X= 0.943 log(k) log2(k). Let F(k) = 2X(log(X) + log2(X)−3 2−1 2X)k−1.1954klog(k). Then F(k) = klog(k)f(k) with f(k) := 1.886 log2(k)(log(X) + log2(X)−3 2−1 2X)−1.1954. Observe that f(k) is an increasing function of kand hence f(k)≥ f(1093), since k≥1093. As f(1093)≥0.0005, we find that F(k)>0 which implies that P(k)>1.1954klog k. Hence kis not a Pα-prime with α= 1.1954.This proves the theorem for k≥1093. Next consider 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 largest integer hsuch that ph<log(1043) is 25. Taking m= 25 ∏ j=1 pj, we find that gcd(m, k) = 1 and m < 1043 3≤k g(k) + 1. From [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 proves the proposition for k∈[1043,1093).Let k∈[10a,10b).In Table 1, we give the values of (a, b), h, the exact value of g(m) from [3, Table 1] where m=∏h i=1 piso that ph<log(10a), P (k)>1.1954klog(k). Then the assertion of the theorem follows for kin this interval. 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 of h,g(m) and (a, b). we conclude that k < 108.Further, we take k∈[6691068,108) with h= 7, g(m) = 26 to get the assertion of the theorem. Next, we take 90107 ≤k < 6691068.In this case, we find that pπ(k)+k−1<1.25klog(k).Then we take h= 6, g(m) = 22 to exclude these values of kby Lemma 3.3. Thus k < 90107.For these values of kwe give a computational argument. Let kbe fixed. Suppose Skdenotes the set of residues mod kof all the primes upto pπ(k)+k−1.If (3) |Sk|=k then, kmay be a B-prime. We check that (3) is valid only for k= 2,3,7,11.Further 11 is not a B-prime as there is no set of 11 consecutive primes among the first 15 primes which yields a complete residue system. On the other hand, 2,3,7 give consecutive primes forming a complete residue system as mentioned in Section 2. This proves the theorem.  GENERALIZATIONS OF PROBLEMS OF RECAMAN AND POMERANCE 9 Proof of Theorem 2.4. Let k≥2 be an arbitrary integer. We shall show that under the prime ℓ-tuple conjecture, kis a B-integer i.e., there exists φ(k) consecutive primes forming a reduced residue system mod k. Let A={a1, . . . , aφ(k)}be the set of all positive integers coprime to kwith 1 = a1<···< aφ(k)< k. The set Amay not be an admissible set. We construct an admissible set out of Aas follows. Put P=∏ p−prime p-k,p≤φ(k) p. Let B={b1, . . . , bφ(k)}be a set of positive integers such that (4) b1=a1= 1; bi≡ai(mod k) and bi≡1 (mod P) (for i≥2). Firstly, note that such bi’s exist by the Chinese Remainder Theorem. Next we show that Bis an admissible set. Since |B|=φ(k) and Bcontains integers coprime to k, it is enough to restrict to primes p≤φ(k) and p-k. Then by (4), every bi≡1(mod p),hence Bcannot have a complete residue system (mod p).By applying the prime ℓ-tuple conjecture to B, we find infinitely many n > k for which n+b1,· · · , n +bφ(k) are all primes and hence coprime to k. But these primes may not be consecutive primes. To ensure this, we proceed as follows. Let M= max b∈Bb and Ithe set of positive integers nwith n≤M. Further let C={c∈I\B:B∪ {c}is admissible}. Let t=|C|and write C′=I\(B∪C).Thus for c′∈C′, B ∪ {c′}is not an admissible set. Hence there exists a prime p≤Msuch that B∪ {c′}has a complete residue system (mod p). Note that M > k by (4). We construct an admissible set S⊇B, such that S∪ {c}is not admissible for any c∈C. If t= 0 then take S=B. If t≥1, take primes q1<· · · < qtexceeding Mand put Q=∏ p<q1+···+qt p. Let us enumerate the elements of Cas c1, . . . , ct.Corresponding to each ci,we construct a set D(i)as follows. Let d(i) 1satisfy d(i) 1> M, d(i) 1≡1(mod Q qi)and d(i) 1(mod qi)∈ B∪ {ci}.