Prime and Composite Terms in Sloane’s Sequence A056542

Tom Müller Institute for Cusanus-Research University and Theological Faculty of Trier Domfreihof 3 54290 Trier Germany

                     muel4503@uni-trier.de

Abstract We give the complete factorization of the first fifty terms of the sequence a_{n} := na_{n−1} + 1 with a_{1} := 0. We searched the terms a_{n} for primes up to n = 1019 with the result that only the indexes 4, 8, 18, 20 and 70 provide primes. A final section deals with some conjectures on prime terms in this sequence.

1 Introduction

Consider the sequence of integers defined by a_{n} := na_{n−1} + 1 with a_{1} := 0. This sequence is \underline{A056542} in Neil Sloane’s Online Encyclopedia of Integer Sequences [4]. In this paper we give the complete factorization of the first fifty terms and deal with the question what terms are prime numbers for n < 1020. To do this we need two equivalent expressions for the terms a_{n}.

Using a simple induction argument we can show that

a_{n} = ∑_{ν=2}^{n} \frac{n!}{ν!}.  (1)

The study of the convergence of the exponential series (which is, among other things, used to prove the irrationality of e) allows us moreover to write

a_{n} = ⌊n!(e − 2)⌋ = ⌊n!e⌋ − 2n!.  (2)

Using the first expression it is easy to prove a criterion for the compositeness of certain terms.

2 Composite terms

From the definition of the sequence it follows immediately that for odd n > 1 the term a_{n} is even and greater than 3 and hence composite. So only even indexes can provide potential prime numbers. Expression (1) implies the following result.

Theorem 2.1 Let p be a prime number and n be a natural number with p ≤ n. If p is a divisor of a_{n} then p divides a_{n+p} as well.

Proof: Writing

a_{n+p} = ∑_{ν=2}^{p−1} \frac{(n + p)!}{ν!} + ∑_{ν=p}^{n+p} \frac{(n + p)!}{ν!},  (3)

we see that the first sum on the right side contains the factor p. Concerning the second sum, we obtain (e.g., by induction on n)

∑_{ν=p}^{n+p} \frac{(n + p)!}{ν!} = (∑_{ν=0}^{n} \frac{n!}{ν!}) + pk  (4)

where k is a natural number. This is equivalent to

a_{n+p} = a_{n} + 2n! + pK

with another natural number K absorbing k and the respective factor of the first sum in (3). Hence a_{n+p} is a multiple of p if a_{n} is. □

One consequence of the theorem is the fact that for a given prime p it is enough to search among the terms a_{p}, a_{p+1}, …, a_{2p−1} for multiples of p. Numerical computations lead to the results presented in Table 1.

Furthermore, we can now use the theorem to sift the prime candidates and retain more than half of them as composites. The a_{n}’s that could not be identified being the product of two nontrivial factors with our sieve method were tested for compositeness by trying to find a small factor with a standard factorization algorithm, which again eliminated about half the terms. Each remaining term was subjected to the Fermat test

2^{a_{n}−1} ≡ 1 mod a_{n}.  (5)

It turned out that in all the cases, exept for n ∈ {4, 8, 18, 20, 70}, the congruence failed, and hence the respective a_{n} was composite. We studied the indexes n < 1020. Testing one term took an average CPU time of about one hour.

p n with p|a_{n} p n with p|a_{n}
2 3  113 163
5 7, 9  127 135
13 17, 23, 25 131 153, 164
19 25, 33  137 144, 153
23 37, 41  149 218
29 52  163 168
31 45, 50  167 242
37 53, 71, 73 173 336
41 78  179 351
43 62  181 276
59 100  193 250, 255
71 81, 120  197 228, 297
83 157  211 269, 357, 391, 415
97 123  223 363
103 109  227 411, 436
107 158  239 418
109 196, 213  251 279

Table 1: Prime numbers p dividing the term a_{n}

3 Prime terms

In the previous section we pointed out that only the terms

a_{4} = 17
a_{8} = 28961
a_{18} = 4598708691828421
a_{20} = 1747509302894800001
a_{70} = 8603990361433692835766763032506384134769654780784715495311087517908153547994512075361554378508046501

remain potential prime numbers. For n = 4, 8, 18, 20 it is simple to prove their primality, for example by trial division up to the respective square roots. For a_{70}, which is a 100digit number, primality can be established using two theorems of Brillhart, Lehmer and Selfridge [1].

Theorem 3.1 Let N − 1 = ∏ p_{i}^{α_{i}} be the complete factorization of the integer N − 1. If for each prime factor p_{i} there exists an a_{i} such that N fulfills a_{i}^{N−1} ≡ 1 (mod N), but a_{i}^{(N−1)/p_{i}} ≢ 1 (mod N), then N is prime.

Theorem 3.2 Let N + 1 = ∏ p_{i}^{α_{i}} be the complete factorization of the integer N + 1. Let U be the set of Lucas sequences {U_{k}^{(i)}} with the given discriminant D for which the Jacobi symbol (D/N) = −1. If for each p_{i} there exists a Lucas sequence in U such that N is a divisor of U_{N+1}^{(i)}, but not a divisor of U_{(N+1)/p_{i}}^{(i)}, then N is prime.

Remark: Let P and Q be integers with the discriminant D := p^{2} − 4Q ≠ 0. Then the Lucas sequences are defined recursively by

U_{k+2} = P U_{k+1} − QU_{k},  k ≥ 0, U_{0} = 0, U_{1} = 1,  (6)

and

V_{k+2} = P V_{k+1} − QV_{k},  k ≥ 0, V_{0} = 2, V_{1} = P.  (7)

A simple method to compute large terms of a given Lucas sequence is presented in the paper of Brillhart et al. ([1, pp. 627–628]) as well.

With this we can settle the primality of a_{70}.

Theorem 3.3 The number a_{70} is prime.

Proof: We have

a_{70} + 1 = 2 · 3 · 11 · 471193 · p_{93},

where

p_{93} = 276666865434658243552094076373979681579672293479713404939810982616341330249301822966628239979

is a 93-digit probable prime. If we assume that p_{93} is prime, the claim follows with theorem 3.2 by setting D = −3. Then the divisibility criteria hold for the factor 2 with P = Q = 1, for the factor 3 with P = Q = 3 and for the other three factors with P = 5 and Q = 7.

So, we need the primality of p_{93}. To reach this goal, we consider the factorization

p_{93} − 1 = 2 · 3 · 167 · 263 · 457 · 8377 · p_{81}

with a 81-digit probable prime

p_{81} = 274238840573141405175902476234412618955309935656050257207045603051300234586527927.

Again, if we assume that p_{81} is prime the primality of p_{93} follows with a_{i} = 3 for all i = 1, …, 7 in theorem 3.1.

The next step consists in proving the primality of p_{81}. For this, we apply theorem 3.1 again with the base a_{i} = 3 to

p_{81} − 1 = 2 · q_{81}

where

q_{81} = 137119420286570702587951238117206309477654967828025128603522801525650117293263963

is another 81-digit probable prime. A final step shows the primality of q_{81}. This follows with theorem 3.2 and

q_{81} + 1 = 2^{2} · 3 · 13 · 29 · 4793 · 15227 · 20422008121 ·
·688270315985433959 · 28276698587131486301 ·
·1044884793638901916109.

These final factors are small enough to be easily proved prime. Here again a discriminant D = −3 gives the wanted results with P = 5 and Q = 7 for all ten prime factors. □

The results of this section are summarized in Sloane’s OEIS A070213 [4].

Remark: The sequence can be generalized to b_{n} := nb_{n−1} + 1 by defining another initial term b_{1} := b ∈ ℕ. Then we can establish the relation

b_{n} = bn! + a_{n}.

Therefore the sieve method will work for the generalized case too. How many primes are there in the respective sequences?

4 Complete factorization of the first fifty terms

The following factorization results were obtained using Lenstra’s elliptic curve method [3]. The factors found were furthermore tested for their primality again using trial division up to the square root. All computations in this sections were realized in almost 100 hours of CPU time on two Pentium-I computers. The results can be found in Tables 3 and 4.

5 Conclusions and conjectures

Using a heuristic argument similar to those used, e.g., by Hardy and Wright ([2, p. 15]) for Fermat numbers, or by Wagstaff [5] for Mersenne numbers, we can formulate some conjectures about the asymptotic behavior of prime numbers in sequence A056542.

In order to do this, we extended Table 1 up to the first 10, 000 primes by steps of 1000 primes, noting only the number N(p) of n in the interval 1 < n < p, resp. p ≤ n < 2p − 1, for which p divides a_{n} and computed the averages

σ(x) = \frac{∑_{p≤x} N(p)}{2π(x)}

with these data. Here π(x) = #{p ∈ ℙ : p ≤ x} denotes the prime number counting function.

These results, which are given in Table 2, suggest that the average number of such n taken over all primes p less than a given x is approximately equal to 1, which might indicate that σ(x) → 1 for x → ∞.

\begin{matrix}π(x) = & 1000 & 2000 & 3000 & 4000 & 5000 \\ 1 < n < p & 1.019 & 1.024 & 1.006 & 1.005 & 1.000 \\ p ≤ n < 2p & 0.973 & 1.001 & 1.005 & 1.003 & 1.010 \\ σ(x) = & 0.996 & 1.013 & 1.006 & 1.004 & 1.005 \\ π(x) = & 6000 & 7000 & 8000 & 9000 & 10000 \\ 1 < n < p & 0.998 & 0.998 & 0.990 & 0.994 & 0.986 \\ p ≤ n < 2p & 1.004 & 1.004 & 1.008 & 1.005 & 0.999 \\ σ(x) = & 1.001 & 1.001 & 0.999 & 1.000 & 0.993 \end{matrix}

Table 2: The averages of terms a_{n} that are divides by primes p (rounded)

If we assume that this is the case, this would say that, on average, a prime p divides a_{n} (for large n) with probability \frac{1}{p}. But this would mean that the terms of our sequence behave just like “typical” numbers of the same size, and hence are just as likely to be prime. So, according to the famous Prime Number Theorem, the probability for any given a_{n} to be prime, would be \frac{1}{ln(a_{n})}. Applying the well known Stirling formula to expression (2), we get

ln(a_{n}) ≈ ln(n!) ≈ A · n ln(n)

with a constant A < 1. If this all is true, there are two consequences worth mentioning. On the one hand, the number P (x) of prime terms a_{n} with indices n ≤ x would be

P (x) ≈ A^{−1} ∑_{n=2}^{⌊x⌋} \frac{1}{n ln(n)}.  (8)

Hence, as the series in (8) diverges for x → ∞, there would be infinitely many prime terms in sequence A056542.

On the other hand, having a glance at the known prime terms suggests that A^{−1} ≈ 2.3. Using this parameter, solving the equation P (x) = 6 would predict a sixth prime term for an index n ≈ 780. A seventh prime term is expected to accure with the index n ≈ 33700. So, there should be a sixth prime in the interval 1020 ≤ n < 33700 (and more likely it should be found short after the index 1020), if we guessed right. Nevertheless, prime terms a_{n} look like being very rare after all.

Acknowledgements

The author is most grateful to the friendly referee who pointed out a mistake in the manuscript and made various most valuable suggestions to improve the paper.

References

[1] J. Brillhart, D. H. Lehmer and J. L. Selfridge, New primality criteria and factorizations of 2^{m} ± 1, Math. Comp. 29 (1975), 620–647.

[2] G. H. Hardy and E. L. Wright, An Introduction to the Theory of Numbers, Oxford University Press, 1979

[3] H. W. Lenstra, Jr., Factoring integers with elliptic curves, Ann. Math. 126 (1987), 649–673.

[4] Online Encyclopedia of Integer Sequences (OEIS), electronically published at:

    http://www.research.att.com/˜ njas/sequences/

[5] S.S. Wagstaff, Divisors of Mersenne numbers, Math. Comp. 40 (1983), 385–397.

2000 Mathematics Subject Classification: Primary 11Y05; Secondary 11Y55. Keywords: factorization, integer sequence, prime number

(Concerned with sequences \underline{A056542} and \underline{A070213}.)

Received November 2 2004; revised version received June 24 2005. Published in Journal of Integer Sequences, July 6 2005.

Return to Journal of Integer Sequences home page.

\begin{matrix}n & factor(a_{n}) \\ 2 & 1 \\ 3 & 2^{2} \\ 4 & 17 \\ 5 & 2 · 43 \\ 6 & 11 · 47 \\ 7 & 2^{2} · 5 · 181 \\ 8 & 28961 \\ 9 & 2 · 5^{2} · 13 · 401 \\ 10 & 67 · 38903 \\ 11 & 2^{3} · 3583939 \\ 12 & 5 · 68811629 \\ 13 & 2 · 2236377943 \\ 14 & 5 · 661 · 2243 · 8447 \\ 15 & 2^{2} · 234819684019 \\ 16 & 349 · 8627 · 4991479 \\ 17 & 2 · 5 · 13 · 281 · 6993808273 \\ 18 & 4598708691828421 \\ 19 & 2^{5} · 5^{4} · 1579 · 12409 · 222967 \\ 20 & 1747509302894800001 \\ 21 & 2 · 107 · 347 · 461 · 1071999585919 \\ 22 & 5 · 48259 · 3345901481329483 \\ 23 & 2^{2} · 13 · 910619 · 392147324904187 \\ 24 & 5 · 1481 · 41813 · 287851 · 5000304083 \\ 25 & 2 · 13 · 19 · 103 · 257 · 852007193230945949 \\ 26 & 183644977 · 1577374632467830901 \\ 27 & 2^{3} · 5 · 195531926467458324861473137 \\ 28 & 119551 · 373670483 · 4902230134153477 \\ 29 & 2 · 5 · 635087697166304639150064748979 \\ 30 & 13 · 127 · 13511681593 · 8540798558040523807 \end{matrix}

Table 3: Factorization of a_{n} for n ≤ 30

n factor(a_{n})
31 2^{2} · 6793 · 6623384304659 · 32818224968844709
32 5^{2} · 157 · 329993 · 145922492103580626511308757
33 2 · 19 · 37 · 1549 · 2863807538994480264037164291179
34 5 · 330679 · 1341707 · 2303179 · 41504719765549572671
35 2^{4} · 1572242101 · 295044907934065408376485520711
36 13 · 179 · 3389 · 75793 · 2334397613 · 191495312948444419631
37 2 · 5 · 23 · 1407281 · 30543801770391751614358741298340689
38 13 · 1307 · 22110390324250839623066317140029038949371
39 2^{2} · 5 · 47 · 373 · 1913 · 73181 · 46498981·
·6419283046588931936893783
40 283 · 2207 · 452087 · 27443371 · 10961524829·
·6899549447021827237
41 2 · 23 · 67273 · 855946423 · 9984786337·
·908531145956175717351149
42 5 · 51787 · 59539 · 1306501657·
·50103819744552590244570709074233
43 2^{3} · 13 · 674672980073 · 1673513136729517·
·369560688696281328844439
44 5^{2} · 19 · 487 · 833893·

·9898316305621422245445307761627219210689201

45 2 · 31 · 503621 · 5349857·

·514362201527447374617886292288269244810309

46 613981 · 10339597·

·622595573454047871500475953343208441017551021

47 2^{2} · 5 · 1740373 · 25196940506279·
·211807964674353752193208733585193464069
48 262066528371751897 · 22100157339031818463
·1539560451909744956702071
49 2 · 5 · 13 · 36948815219 · 5938235313533·
·15317873368507025363816947275444788447
50 31 · 293 · 206506391500393 · 31126232036943157·
·374179843710832651624027922347

Table 4: Factorization of a_{n} for 30 < n ≤ 50