On a problem of Recaman and its generalization

On a problem of Recaman and its generalization L. Hajdu and N. Saradha University of Debrecen, Institute of Mathematics and the Number Theory Research Group of the Hungarian Academy of Sciences Debrecen, Hungary 1 School of Mathematics, Tata Institute of Fundamental Research Dr. Homibhabha Road, Colaba, Mumbai, India Abstract We solve some cases of a conjecture of Pomerance concerning reduced residue systems modulo kconsisting of the first φ(k) primes not dividing k. We cover the case when kis a prime, thus giving a complete solution to a problem of Recaman. Key words: the problem of Recaman, the problem of Pomerance, Jacobsthal function, primes in residue classes PACS: 11N13 Dedicated to Professor K. Gy˝ory on the occasion of his 70th birthday 1 Introduction Let k > 1 be an integer and denote by φ(k) Euler’s totient function. We say that kis a P-integer if the first φ(k) primes coprime to kform a reduced residue system modulo k. Note that a prime pis a P-integer if and only if the first pprimes form a complete residue system modulo p. In 1980, Pomerance [3] showed that there are only finitely many P-integers. Thereby he qualitatively solved the problem of finitely many prime P-integers which was raised earlier in 1978 by Recaman [4]. In his paper Pomerance conjectured that the largest Email addresses: [email protected],[email protected] (L. Hajdu and N. Saradha). 1Research supported in part by the Hungarian Academy of Sciences, by the OTKA grants K67580 and K75566, and by the grant T´ AMOP 4.2.1./B. P-integer is k= 30. It is easy to check that the only P-integers less than or equal to 30 are k= 2,4,6,12,18,30. In this paper we prove the conjecture of Pomerance in two “opposite” extremal cases: when kis composed of “large” prime factors (i.e. when all the prime divisors of kare above log(k)), and when kis composed of “small” prime factors (i.e. kis the product of all primes ≤xfor some x). As a trivial consequence of the first result we get a complete quantitative solution for the problem of Recaman. Further, we verify the conjecture of Pomerance for all k < 5.5·105. We note that Pomerance’s finiteness result for P-integers [3] in principle can be made effective: one can possibly get an explicit upper bound for P-integers k. However, according to our calculations, this bound is rather huge, and it seems that to cover the remaining gap some additional (theoretical and/or computational) arguments are needed. So the complete resolution of the problem of Pomerance still remains an open quest; we plan to attack it in a future paper. The proofs of our results depend on some properties of the Jacobsthal function g(m) as in [3]. Among others we use the exact values of g(m) when mis the product of first h≤46 primes, which were recently obtained by Hagedorn [1]. Further, we apply several formulas of Rosser and Schoenfeld [5], concerning various functions involving primes. 2 Main results Our first result solves Recaman’s problem completely. Theorem 1 The only prime P-integer is 2. In fact Theorem 1 is a trivial consequence of the following much more general result. For k > 1 let ℓ(k) be the least prime divisor of k. Theorem 2 Let k > 1be an integer with ℓ(k)>log(k). Then kis a P-integer if and only if k∈ {2,4,6}. For fixed positive integer rand positive real Xwrite Nr:= {n|ω(n) = r}and Nr(X) := {n∈Nr|n≤X}, where ω(n) denotes the number of distinct prime divisors of n. Further, for any positive real x, we let log1(x) = log(x) and for t≥2, logt(x) = log(logt−1(x)). 2 By a result of Landau it is known that |Nr(X)| ∼ X(log2(X))r−1 log(X)(r−1)! (see Theorem 437, p. 368 of [2]). Let N′ r(X) denote the set of integers n in Nr(X) with ℓ(n)≤log(n). Then for any n∈N′ r(X) we have ℓ(n)≤ log(X) and n/ℓ(n)∈Nr−1(X/ℓ(n)). Applying Landau’s result to Nr−1(X/p) for every p≤log(X), and noting that (log2(x))r−2 log(x)is a decreasing function of x for sufficiently large x, we find that |N′ r(X)| ≤ c1∑ p≤log(X) X p(log2(X p))r−2 log (X p)(r−2)! ≤c2 X(log2(X))r−2 log(X)(r−2)! ∑ p≤log(X) 1 p≤ ≤c3 X(log2(X))r−2 log(X)(r−2)! log3(X) where c1,c2and c3are absolute constants. Thus we see that almost all integers in Nrhas ℓ(n)>log(n). In particular, kis not a P-integer whenever kis the product of twin primes. Our third theorem verifies the conjecture of Pomerance for integers kbeing the products of the first few primes. Theorem 3 Let kbe the product of the primes ≤xfor some x≥2. Then k is a P-integer if and only if k∈ {2,6,30}. Finally, we formulate a statement concerning the solution of the problem of Pomerance for “small” values of k. Our main motivation of doing so is that this result will be very useful in the proof of Theorem 2. Proposition 4 Suppose that 1< k < 5.5·105. Then kis a P-integer if and only if k∈ {2,4,6,12,18,30}. 3 Lemmas We need many lemmas of different types to prove our theorems. We shall make use of several estimates of Rosser and Schoenfeld [5] concerning various functions related to prime numbers. Further, we need certain results due to Stevens [6] and Hagedorn [1] about the Jacobsthal function. Finally, we need a theorem of Pomerance about primes in residue classes modulo m. 3 3.1 Lemmas concerning functions involving primes The following four lemmas are estimates from Rosser and Schoenfeld [5] which we need later on. Lemma 5 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. Lemma 6 For any x≥59 we have x log(x)(1 + 1 2 log(x))< π(x)<x log(x)(1 + 3 2 log(x)). Lemma 7 For x≥2write ϑ(x) = ∑ p≤x log(p). For any x≥563 we have x(1−1 2 log(x))< ϑ(x)< x (1 + 1 2 log(x)). Lemma 8 For any x > 1we have ∏ p≤x(1−1 p)<0.56146 log(x)(1 + 1 2 log2(x)). Note that here 0.56146 could be replaced by any number exceeding e−γ, where γis Euler’s constant. 3.2 Lemmas about the Jacobsthal function 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. [6], [3] and [1] for history). Further, the exact values of g(n) when nis the product of the first h < 50 primes is given in Table 1 of [1]. It was observed by Jacobsthal that for integers kwith ℓ(k)>log(k) we have g(k) = ω(k) + 1. Further, g(k)≥ω(k) + 1 is obviously valid for any k. We shall use these assertions throughout the paper without any further reference. Our first lemma concerning the Jacobsthal function is a reformulation of the Theorem of Stevens [6]. 4 Lemma 9 We have g(k)≤2ω(k)2+2elog(ω(k)) for all k > 1. The next lemma is Proposition 1.1 of Hagedorn [1]. Lemma 10 We have g(h ∏ i=1 pi)≥2ph−1for h > 2. 3.3 A result of Pomerance 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. Observe that kis a P-integer if and only if P(k) equals the φ(k)-th prime not dividing k. Since the number of primes dividing kis ω(k), we get that if kis a P-integer then pφ(k)≤P(k)≤pφ(k)+ω(k) holds. Note also that since φ(k) + ω(k)≤k, we have P(k)≤pkwhenever k is a P-integer. To prove the finiteness of k’s which are P-integers, Pomerance [3] derived a lower bound for P(k) which (for large k) turns to be larger than standard upper bounds for pφ(k)+ω(k), obtained by using estimates from [5]. This lower bound of Pomerance is based upon the following result from [3]. Lemma 11 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 Since in the proof of Theorem 2 we use Proposition 4, we start with the proof of the latter result. Proof of Proposition 4. Let kbe arbitrary with 1 < k < 5.5·105. Let q1< q2< q3< . . . be the primes > tk with t= 1 if kis even and t= 2 if kis odd, respectively. We find the first index isuch that qi−tk is a prime. For all kin the considered interval we found i≤34. If k+ 2 is a prime then let q=k+ 2, otherwise set q=qiwith the above defined index i. A calculation with Maple based upon Lemma 5 ensures that for k > 210 we have q≤pφ(k). Thus there exist two primes ≤pφ(k)being coprime to kin the same residue class modulo k, which proves that kis not a P-integer in this case. Finally, for k≤210 we 5 check by Maple the first φ(k) primes not dividing kto get the assertion of the proposition. 2 Proof of Theorem 2. Let kbe a P-integer with ℓ(k)>log k. Assume first that k≥1090. We split the proof of this case into two parts. Suppose first that k < (ω(k)+2)20. Then, since we know that ω(k) log(ℓ(k)) ≤log(k), we obtain ω(k)≤log(k) log2(k). Hence using our assumption for kwe get k < (log(k) log2(k)+ 2)20 . This implies that k < 1090, which is a contradiction, and the statement follows in this case. Suppose next that we have k≥(ω(k) + 2)20. Let 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). Let mbe the product of the first hprimes coprime to k. Since ph<log(k)< ℓ(k), by assumption, we see that mis indeed the product of all the first h primes. 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 have 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 where X= 0.894 log(k) log2(k). Let F(k) = 2X(log(X) + log2(X)−3 2)k−klog(k)−klog2(k)−k. Then F(k) = klog(k)f(k) with f(k) := 1.788 log2(k)(log(X) + log2(X)−3 2)−1−log2(k) log(k)−1 log(k). Observe that f(k) is an increasing function of kand hence f(k)≥f(1090), since k≥1090. As f(1090)≥0.0803, we find that F(k)>0 which implies that P(k)> k log(k)+klog2(k)> pk≥pφ(k)+ω(k). Hence kis not a P-integer. This contradiction proves the theorem for k≥1090 with ℓ(k)>log(k). Assume now that k < 1090. By Proposition 4 we may suppose that 5.5·105≤ k < 1090. We divide the interval [5.5·105,1090) into sub-intervals and assign a value hto each interval as follows. Let v0= 1090. The largest integer h such that ph<log(1090) is 46. We set our initial sub-interval as [u0, v0) = [1087,1090), α0= 87 and h0=h= 46. For any kwith ℓ(k)>log(k) in this interval we have g(k) = ω(k)+1<log(k) + 1 <209. We check that m0:= 46 ∏ j=1 pj<1087 210 ≤k g(k)+1. Now we proceed inductively. Let i≥1 and take hi=h0−i. We define the sub-interval [ui, vi) as [10αi,10αi−1) satisfying the following properties: phi< αilog(10) (1) and mi:= h0−i ∏ j=1 pj<10αi (αi−1log(10) + 2).(2) Let k∈[ui, vi) with ℓ(k)>log(k). Then phi<log(k) and hence by the assumption on k,miis the product of the first hiprimes, and gcd(mi, k) = 1. Suppose that 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) that P(k)> k log(k) + klog2(k)> pk≥pφ(k)+ω(k) and hence k∈[ui, vi) is not a P-integer. In Table 1 we give the values hi=h,αi=α, and the exact value of g(m) with m=mifrom Table 1 of [4]. For these values, we check that (1), (2) 7 and (3) are satisfied and hence we conclude that k < 108. Now consider 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 the intervals [3 ·107,108) with h= 7 and [5.5·105,3·107) with h= 6 and g(m) = 22, respectively. Then conditions (1), (2) and (3) are satisfied again, showing that kis not a P-integer. Hence the statement follows. 2 Proof of Theorem 3. Assume first that x≥1000 and put k=∏ p≤x p. Set m:= ∏ x<p≤y pwith y= 1.777x. First we show that by these choices we have m≤k/(1 + g(k)). This inequality can be rewritten as 1 + g(k)≤exp(2ϑ(x)) exp(ϑ(y)) . Using Lemma 9, it is sufficient to show that 1+2π(x)2+2elog(π(x)) ≤exp(2ϑ(x)−ϑ(1.777x)). With the help of Maple, by Lemmas 6 and 7 this can be seen to be true whenever x≥12000. For 1000 ≤x < 12000 the assertion can be checked by calculating the exact values of the functions π(x) and ϑ(x). Now we show that (still with x≥1000) we have (g(m)−1)k≥pφ(k)+ω(k). By Lemma 11 this implies the statement. To prove this, observe that g(m)> 8 ω(m) = π(y)−π(x). Hence using Lemma 5 (ii) it is sufficient to check that π(1.777x)−π(x)≥  ∏ p≤x(1−1 p)+π(x) ∏ p≤x p  (ϑ(x) + log(ϑ(x))) for x≥1000. Again, by the help of Lemmas 6, 7 and 8 this inequality can be verified for x≥12000 with Maple. Further, for 1000 ≤x < 12000 the assertion can be proved by calculating the exact values of the expressions involved. Hence the statement is valid when x≥1000. Assume now that x < 1000. Then we check the values of kone by one. For k given, let q1=pπ(k)+1 and q2=pπ(k)+2. A calculation by Maple shows that for k > 30 we have q2≤pφ(k)+ω(k), and also that one of q1−k,q2−kis a prime. Finally, as k= 2,6,30 are P-integers indeed, the statement follows. 2 5 Acknowledgement The authors thank the referee for the useful and helpful remarks and suggestions. The authors are grateful to Professor C. Pomerance for drawing their attention to his paper [3] where the problems considered in this paper are posed. The second author also thanks Professor K. Gy˝ory for his kind hospitality during her visit to Debrecen, Hungary in November, 2009. References [1] T. R. Hagedorn,Computation of Jacobsthal’s function h(n)for n < 50, Math. Comp. 78 (2009), 1073–1087. [2] G. H. Hardy, E. M. Wright,An Introduction to the Theory of Numbers, Fifth Edition, Oxford University Press, 1981. [3] C. Pomerance,A note on the least prime in an arithmetic progression, J. Number Theory 12 (1980), 218–223. [4] B. M. Recaman,Problem 672, J. Recreational Math. 10 (1978), 283. [5] J. B. Rosser, L. Schoenfeld,Approximate formulas for some functions of prime numbers, Illinois J. Math. 6(1992), 64–94. [6] H. Stevens,On Jacobsthal’s g(n)function, Math. Ann. 226 (1977), 95–97. 9