Primes in Fibonacci n-step and Lucas n-step Sequences

Tony D. Noe 14025 NW Harvest Lane Portland, OR 97229 USA

                   noe@sspectra.com

Jonathan Vos Post 3225 North Marengo Avenue Altadena, CA 91001 USA

                  jvospost2@yahoo.com

Abstract

We search for primes in the Fibonacci n-step and Lucas n-step sequences, which are the natural generalizations of the Fibonacci and Lucas numbers. While the Fibonacci n-step sequences are nearly devoid of primes, the Lucas n-step sequences are primerich. We tabulate the occurrence of primes in the first 10000 terms for n ≤ 100. We also state two conjectures about Diophantine equations based on these sequences.

1 Introduction

As illustrated in the tome by Koshy [9], the Fibonacci and Lucas numbers are arguably two of the most interesting sequences in all of mathematics. The sequence of Fibonacci numbers F_{k} is defined by the second-order linear recurrence formula and initial terms:

F_{k+1} = F_{k} + F_{k−1}, F_{0} = 0, F_{1} = 1

Similarly, the sequence of Lucas numbers L_{k} is defined by

L_{k+1} = L_{k} + L_{k−1}, L_{0} = 2, L_{1} = 1

Simple generalizations of these sequences are F_{k}^{(n)}, the Fibonacci n-step sequence, and L_{k}^{(n)}, the Lucas n-step sequence, which are defined by linear recurrence formulas of order n > 1:

F_{k+1}^{(n)} = F_{k}^{(n)} + F_{k−1}^{(n)} + ⋯ + F_{k−n+1}^{(n)}  (1)
L_{k+1}^{(n)} = L_{k}^{(n)} + L_{k−1}^{(n)} + ⋯ + L_{k−n+1}^{(n)}  (2)

and n initial terms

F_{1−n}^{(n)} = 1, F_{k}^{(n)} = 0, k = −n + 2, …, 0  (3)
L_{0}^{(n)} = n, L_{k}^{(n)} = −1, k = −n + 1, …, −1  (4)

The sequence generated by equations (1) and (3) is also known as the k-generalized Fibonacci numbers, which are discussed by Flores [7]. Observe that equations (1) and (2) are equivalent to the three-term recursions

F_{k+1}^{(n)} = 2F_{k}^{(n)} − F_{k−n}^{(n)}
L_{k+1}^{(n)} = 2L_{k}^{(n)} − L_{k−n}^{(n)}

which are computationally superior for large n, and which show that all of these n-step sequences grow at a rate less than 2^{k}. This recursion requires one more initial term, which we can take to be F_{1}^{(n)} = L_{1}^{(n)} = 1. Also observe that the Lucas n-step sequence can be obtained from the Fibonacci n-step sequence with the identity

L_{k}^{(n)} = F_{k}^{(n)} + 2F_{k−1}^{(n)} + ⋯ + (n − 1)F_{k−n+2}^{(n)} + nF_{k−n+1}^{(n)}

which follows from the generating functions of these two sequences.

Dickson [4] cites a long history of generalizations of the Fibonacci numbers. Miles [11] used equation (1) in 1960. Fielder [6] appears to be the first to generalize the Lucas numbers to the Lucas n-step sequences. Catalani [3] has also written about these sequences. More recently, Benjamin and Quinn [2] briefly discuss a combinatorial interpretation of these nstep sequences.

The usual Fibonacci and Lucas numbers are obtained for n = 2. For small values of n, these sequences are called tribonacci (n = 3), tetranacci or quadranacci (n = 4), pentanacci or pentacci (n = 5), hexanacci or esanacci (n = 6), heptanacci (n = 7), and octanacci (n = 8). Examples of these sequences and their A-numbers in Sloane’s [12] OEIS database are given on the next page.

The unique primes in each table appear in boxes. Note that these abbreviated sequences have many primes and that there appear to be more Lucas primes than Fibonacci primes. Also note that every Mersenne prime — a prime of the form 2^{p} − 1 — appears in these sequences as F_{p+2}^{(p)} and L_{p}^{(n)} for n ≥ p.

The primary purpose of this paper is to tabulate the values of k that yield prime terms of the Fibonacci n-step and Lucas n-step sequences. Additionally, the paper describes how these primes were determined and makes conjectures about the distinct values in these sequences.

Table 1: Fibonacci n-step Sequences

k 1 2 3  4  5  6  7  8  9  10  11  12  13  14  A-number

n

2  1 1 2  3  5  8  13  21  34  55  89  144  233  377  \underline{A000045}
3  1 1 2  4  7  13  24  44  81  149  274  504  927 1705 \underline{A000073}
4  1 1 2  4  8  15  29  56  108  208  401  773  1490 2872 \underline{A000078}
5  1 1 2  4  8  16  31  61  120  236  464  912  1793 3525 \underline{A001591}
6  1 1 2  4  8  16  32  63  125  248  492  976  1936 3840 \underline{A001592}
7  1 1 2  4  8  16  32  64  127  253  504  1004  2000 3984 \underline{A066178}
8  1 1 2  4  8  16  32  64  128  255  509  1016  2028 4048 \underline{A079262}
9  1 1 2  4  8  16  32  64  128  256  511  1021  2040 4076 \underline{A105753}

Table 2: Lucas n-step Sequences

k 1 2 3 4  5  6  7  8  9  10  11  12  13  A-number

n

2  1 3 4 7  11 18  29  47  76  123  199  322  521  \underline{A000032}
3  1 3 7 11  21 39  71  131  241  443  815  1499  2757  \underline{A001644}
4  1 3 7 15  26 51  99  191  367  708  1365  2631  5071  \underline{A073817}
5  1 3 7 15  31 57 113  223  439  863  1695  3333  6553  \underline{A074048}
6  1 3 7 15  31 63 120  239  475  943  1871  3711  7359  \underline{A074584}
7  1 3 7 15  31 63 127  247  493  983  1959  3903  7775  \underline{A104621}
8  1 3 7 15  31 63 127  255  502  1003  2003  3999  7983  \underline{A105754}
9  1 3 7 15  31 63 127  255  511  1013  2025  4047  8087  \underline{A105755}

2 Tables of Primes and Probable Primes

Tables 3 and 4, at the end of this paper, list the n and k values that yield prime or probable prime (abbreviated prp) terms of the Fibonacci n-step sequences F_{k}^{(n)} for 2 ≤ n ≤ 100 and 1 ≤ k ≤ 10000. Similarly, Tables 5, 6, and 7 list the n and k values that yield prime or probable prime terms of the Lucas n-step sequences L_{k}^{(n)}.

A striking difference between the F_{k}^{(n)} and L_{k}^{(n)} tables is the small number of Fibonacci primes and the relatively large number of Lucas primes. This difference is explained by the parity of the two types of sequences. The fraction of odd numbers in the sequence F_{k}^{(n)} is 2/(n + 1) while the fraction of odd numbers in the sequence L_{k}^{(n)} is either 1 or n/(n + 1), depending on whether n is odd or even, respectively. Hence, because the F_{k}^{(n)} sequence contains many fewer odd numbers, it contains many fewer prime numbers. In fact, using a probabilistic argument, such as in Hardy and Wright [8, § 2.5], and taking into account the parity of the numbers in the sequences, we estimate the number of primes in F_{k}^{(n)} for k ≤ N:

#\{k ≤ N : F_{k}^{(n)}prime\} ≈ \frac{4}{n + 1} ∑_{i=1}^{N} \frac{1}{log F_{i}^{(n)}}

≈ \frac{4}{n + 1} ∑_{i=1}^{N} \frac{1}{log α_{n}^{i}} = \frac{4}{n + 1} \frac{H_{N}}{log α_{n}}

where α_{n} is the growth rate of the sequence (the largest real root of x^{n}(2 − x) = 1) and

H_{N} = ∑_{i=1}^{N} \frac{1}{i}

is the harmonic sum. Similarly, an estimate for the number of primes in L_{k}^{(n)} for k ≤ N is

#\{k ≤ N : L_{k}^{(n)}prime\} ≈ \begin{cases}\frac{2H_{N}}{log α_{n}} , & if n is odd; \\ \frac{n}{n+1} \frac{2H_{N}}{log α_{n}} , & if n is even. \end{cases}

These estimates are evaluated for each n and appear in the last column of the tables. In many cases, the estimates are close to the actual number of primes that we found.

3 Prime Search and Prime Proving

Each probable prime was determined using the PrimeQ function in Mathematica^{\begin{matrix}r \\ ◯ \end{matrix}}. PrimeQ, which Wagon [13] discusses at length, is based on the Miller-Rabin strong pseudoprime test base 2 and base 3, and a Lucas test. Testing F_{k}^{(n)} and L_{k}^{(n)} with PrimeQ for 2 ≤ n ≤ 100 and 1 ≤ k ≤ 10000 required approximately 32 hours on a dual-processor 1.8 GHz G5 Macintosh^{\begin{matrix}r \\ ◯ \end{matrix}} computer.

For small n, the search for probable primes has been more extensive than the limit k ≤ 10000 used here. For instance, searches by Dubner and Keller [5] and more recently by Lifchitz [10] have found probable prime values of F_{k}^{(2)} and L_{k}^{(2)} for k > 500000.

For the probable primes up to 1000 digits (and a few prps with more digits), we proved primality using an elliptic curve primality algorithm, as described by Atkin and Morain [1]. This computation required approximately 60 hours on a 2.81 GHz Pentium^{\begin{matrix}r \\ ◯ \end{matrix}} 4 processor. All of the tested probable primes proved to be prime. For the Fibonacci and Lucas numbers, F_{k}^{(2)} and L_{k}^{(2)}, Dubner and Keller [5] have proved the primality for those entries in row n = 2 of Tables 3 and 5. Probable primes in Tables 3–7 are marked by an asterisk.

4 Duplicate Primes?

Are there duplicate primes in these tables? Let us ignore the initial terms of these n-step sequences because m-step and n-step sequences with m < n have the initial m or m + 1 terms in common. For Fibonacci n-step sequences, the prime 13 is common to both the 2-step and 3-step sequences. For Lucas n-step sequences, the primes 7 and 11 are in the 2-step and 3-step sequences. This observation leads us to two conjectures:

Conjecture 1 The Diophantine equation

F_{r}^{(m)} = F_{s}^{(n)}, r > m + 1, s > n + 1

has only two solutions:

13 = F_{7}^{(2)} = F_{6}^{(3)} and 504 = F_{12}^{(3)} = F_{11}^{(7)}.

Conjecture 2 The Diophantine equation

L_{r}^{(m)} = L_{s}^{(n)}, r > m, s > n

has only three solutions:

7 = L_{4}^{(2)} = L_{3}^{(3)}, 11 = L_{5}^{(2)} = L_{4}^{(3)}, and 5071 = L_{14}^{(3)} = L_{13}^{(4)}.

We have confirmed these conjectures for all terms whose magnitude is less than 2^{2000}. Here we offer an heuristic argument showing that the expected number of solutions is small. Let t be a positive integer and consider all the Fibonacci (or Lucas) n-step numbers (for any n ≤ t+1) that are between 2^{t} and 2^{t+1}. It is easy to see that any Fibonacci (or Lucas) n-step sequence has at most two numbers in this range for each t. Assuming that these numbers are randomly distributed in the range 2^{t} to 2^{t+1}, the probability that at least two numbers are the same is

1 − ∏_{d=1}^{2t−1}(1 − d/2^{t})

Hence, an upper bound for the number of solutions is

∑_{t=1}^{∞} (1 − ∏_{d=1}^{2t−1}(1 − d/2^{t})) = 6.26505 …

5 Acknowledgment

The authors wish to acknowledge Eric Weisstein [14] for inspiring this research.

References

[1] A. O. L. Atkin and F. Morain, Elliptic Curves and Primality Proving, Math. Comp. 61 (1993), 29–68.

[2] A. T. Benjamin and J. J. Quinn, The Fibonacci numbers – exposed more discretely, Math. Mag. 76 (2003), 182–192.

[3] M. Catalani, Polymatrix and generalized polynacci numbers, published electronically at www.arXiv.org/math/0210201

[4] L. E. Dickson, History of the Theory of Numbers, Vol. 1, AMS Chelsea, 1919.

[5] H. Dubner and W. Keller, New Fibonacci and Lucas primes, Math. Comp. 68 (1999), 417–427.

[6] D. C. Fielder, Certain Lucas-like sequences and their generation by partitions of numbers, Fibonacci Quart., 5 (1967), 319

[7] I. Flores, Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quart., 5 (1967), 259–266.

[8] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, fourth ed., Oxford University Press, 1960.

[9] T. Koshy, Fibonacci and Lucas Numbers with Applications, John Wiley and Sons, NY, 2001.

[10] H. Lifchitz, Probable primes top 10000, published electronically at www.primenumbers.net/prptop/prptop.php

[11] E. P. Miles, Jr., Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly 67 (1960), 745–752.

[12] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at www.research.att.com/∼njas/sequences.

[13] S. Wagon, Mathematica^{\begin{matrix}r \\ ◯ \end{matrix}} in Action, second ed., Springer-Telos, New York, 2000.

[14] E. W. Weisstein, Fibonacci n-step number, published electronically at mathworld.wolfram.com/Fibonaccin-StepNumber.html

Table 3: Primes of the form F_{k}^{(n)}
number of est. # of

n k for which F_{k}^{(n)} is prime or prp(*) primes for primes for

k ≤ 10000 k ≤ 10000
2 {3, 4, 5, 7, 11, 13, 17, 23, 29, 43, 47, 83, 131, 137, 359, 431, 433, 449, 509, 569, \atop 571, 2971, 4723, 5387, 9311, 9677 \underline{A001605} \underline{A005478}}  26  27
3 3, 5, 6, 10, 86, 97, 214, 801, 4201 \underline{A092835} \underline{A092836}  9  16
4 3, 7, 11, 12, 36, 56, 401, 2707, 8417* \underline{A104534} \underline{A104535}  9  12
5 3, 7, 8, 25, 146, 169, 182, 751, 812, 1507, 1591, 3157, 3752 \underline{A105756} \underline{A105757}  13  10
6 3, 36, 37, 92, 660, 6091*, 8415* \underline{A105758} \underline{A105759}  7  8
7 3, 9, 17 \underline{A105760} \underline{A105761}  3  7
8 3, 11, 19, 119, 344, 1316  6  6
9 3, 12, 871  3  6
10 3, 353, 365, 2432  4  5
11 3, 14, 50, 325, 2510  5  5
12 3, 80, 1237  3  4
13 3, 15, 16, 8051*  4  4
14 3, 361, 1471  3  4
15 3, 34, 82, 657, 5361*, 7026*  6  4
16 3, 274, 4098, 4506  4  3
17 3, 19, 37, 1459  4  3
18 3, 59, 3079  3  3
19 3, 21, 22, 2982, 4382*  5  3
20 3, 233, 484  3  3
21 3, 24, 46, 4072*  4  3
22 3, 47, 232, 393  4  2
23 3, 26  2  2
24 3, 52, 451  3  2
25 3, 287  2  2
26 3, 487  2  2
27 3  1  2
28 3, 31  2  2
29 3  1  2
30 3, 1118  2  2
31 3, 33, 7233*  3  2
32 3, 167  2  2
33 3  1  2
34 3, 9942  2  2
35 3, 254, 3745, 6013*  4  2
36 3  1  2
37 3, 723  2  1
38 3  1  1
39 3  1  1
40 3, 247  2  1
41 3  1  1
42 3, 518, 1205  3  1
43 3  1  1
44 3  1  1
45 3  1  1
46 3  1  1
47 3, 194, 865, 2401  4  1
48 3, 6322*  2  1
49 3  1  1
50 3  1  1

Table 4: Primes of the form F_{k}^{(n)}, continued

number of est. # of

n k for which F_{k}^{(n)} is prime or prp(*) primes for primes for

k ≤ 10000 k ≤ 10000
51 3  1  1
52 3  1  1
53 3, 2809, 4052*, 4592*  4  1
54 3, 2366  2  1
55 3  1  1
56 3  1  1
57 3  1  1
58 3, 120, 3718  3  1
59 3  1  1
60 3, 1405  2  1
61 3, 63, 374  3  1
62 3, 8695*  2  1
63 3, 5057*  2  1
64 3  1  1
65 3, 925  2  1
66 3, 269  2  1
67 3, 341  2  1
68 3  1  1
69 3  1  1
70 3, 1564  2  1
71 3  1  1
72 3  1  1
73 3  1  1
74 3, 302, 2476  3  1
75 3  1  1
76 3  1  1
77 3, 4916*  2  1
78 3  1  1
79 3  1  1
80 3  1  1
81 3  1  1
82 3  1  1
83 3  1  1
84 3  1  1
85 3  1  1
86 3, 263, 8701*  3  1
87 3  1  1
88 3  1  1
89 3, 91, 811  3  1
90 3  1  1
91 3  1  1
92 3, 1024  2  1
93 3, 96  2  1
94 3  1  1
95 3  1  1
96 3  1  1
97 3  1  1
98 3, 299  2  1
99 3  1  1
100 3  1  1

Table 5: Primes of the form L_{k}^{(n)}
number of est. # of

n k for which L_{k}^{(n)} is prime or prp(*) primes for primes for

k ≤ 10000 k ≤ 10000
2 {2, 4, 5, 7, 8, 11, 13, 16, 17, 19, 31, 37, 41, 47, 53, 61, 71, 79, 113, 313, 353, 503, \atop 613, 617, 863, 1097, 1361, 4787, 4793, 5851, 7741, 8467 \underline{A001606} \underline{A005479}}  32  27
3 {2, 3, 4, 7, 8, 9, 10, 12, 20, 30, 33, 66, 76, 77, 82, 87, 98, 180, 205, 360, 553, 719, \atop 766, 1390, 1879, 1999, 4033*, 5620* \underline{A104576} \underline{A105762}}  28  32
4 {2, 3, 8, 9, 16, 19, 24, 27, 46, 68, 71, 78, 107, 198, 309, 377, 477, 1057, 1631, \atop 2419, 3974*, 4293*, 8247* \underline{A104577} \underline{A105763}}  23  24
5 {2, 3, 5, 7, 8, 9, 10, 13, 30, 35, 77, 98, 126, 160, 192, 810, 1086, 1999, 2021, \atop 3157, 3426*, 3471* \underline{A105764} \underline{A105765}}  22  29
6 2, 3, 5, 8, 11, 32, 37, 46, 123, 237, 332, 408, 772, 827, 1523, 5610* \underline{A105766} \underline{A105767}  16  24
7 2, 3, 5, 7, 10, 17, 24, 25, 26, 28, 38, 40, 49, 62, 79, 89, 114, 140, 145, 182, 248, 353, 437, 654, 702, 784, 921, 931, 986, 1206, 2136, 2137, 3351*, 5411* \underline{A104622} \underline{A105768}  34  28

8 {2, 3, 5, 7, 11, 16, 17, 112, 140, 159, 186, 347, 425, 565, 2643, 2931, 3314, 4767*, \atop 9015*}  19  25
9 {2, 3, 5, 7, 10, 13, 23, 27, 38, 41, 56, 84, 107, 112, 123, 203, 209, 758, 765, 895, \atop 1830, 3172, 6763*, 7709*}  24  28
10 2, 3, 5, 7, 48, 59, 75, 79, 156, 167, 245, 335, 370, 412, 970, 1358, 1479, 1652  18  26
11 {2, 3, 5, 7, 15, 31, 32, 39, 41, 47, 66, 89, 111, 173, 182, 295, 334, 350, 357, 480, \atop 548, 662, 681, 853, 1100, 1128, 1171, 1328, 2203, 2427, 2817, 2891, 6818*}  33  28
12 {2, 3, 5, 7, 15, 16, 46, 69, 112, 120, 144, 411, 574, 1009, 1140, 1191, 1257, 1358, \atop 2809, 3223, 3512*, 3759*, 4441*, 6099*, 8304*, 9673*, 9734*}  27  26
13 {2, 3, 5, 7, 13, 14, 22, 27, 53, 55, 92, 242, 299, 344, 382, 699, 767, 834, 1057, \atop 1270, 1565, 1797, 1837, 3847*, 4328*, 4911*, 5093*, 6664*, 7313*, 7470*, 9789*}  31  28
14 {2, 3, 5, 7, 13, 22, 23, 52, 76, 82, 119, 125, 243, 281, 400, 437, 659, 994, 1377, \atop 1426, 1940, 2303, 3853*, 6947*}  24  26
15 {2, 3, 5, 7, 13, 16, 31, 37, 38, 47, 48, 58, 66, 132, 167, 173, 269, 375, 542, 612, \atop 911, 1073, 2821, 3237, 3656*, 3910*, 4424*, 4432*, 6978*}  29  28
16 2, 3, 5, 7, 13, 26, 131, 145, 243, 821, 863, 1388, 1481, 4457*, 5309*, 8696*  16  27
17 2, 3, 5, 7, 13, 17, 59, 208, 325, 353, 926, 991, 1201, 1230, 1347, 1764, 8101*  17  28
18 {2, 3, 5, 7, 13, 17, 23, 33, 45, 58, 107, 134, 217, 286, 552, 985, 1193, 2455, 4202*, \atop 6176*, 8710*, 9831*}  22  27
19 {2, 3, 5, 7, 13, 17, 19, 91, 208, 219, 306, 312, 439, 494, 640, 656, 702, 872, 3346*, \atop 3874*, 7769*, 7804*}  22  28
20 {2, 3, 5, 7, 13, 17, 19, 27, 35, 47, 53, 76, 88, 243, 281, 288, 355, 406, 436, 541, \atop 761, 1055, 2343, 2585, 3705*, 4965*, 7033*}  27  27
21 {2, 3, 5, 7, 13, 17, 19, 28, 52, 61, 165, 263, 278, 284, 691, 1110, 1130, 1372, 1526, \atop 2542, 2656, 3403*, 4162*, 5645*, 6156*, 6572*, 8496*}  27  28
22 {2, 3, 5, 7, 13, 17, 19, 34, 113, 191, 288, 451, 561, 646, 867, 1842, 2368, 5369*, \atop 5827*, 5993*}  20  27
23 2, 3, 5, 7, 13, 17, 19, 28, 37, 44, 86, 133, 142, 164, 307, 700, 2250, 3255, 9785*  19  28
24 {2, 3, 5, 7, 13, 17, 19, 70, 79, 87, 99, 104, 140, 153, 214, 556, 743, 766, 905, \atop 1824, 3983*, 4807*}  22  27
25 {2, 3, 5, 7, 13, 17, 19, 26, 39, 43, 46, 49, 65, 70, 79, 98, 188, 218, 337, 452, 539, \atop 904, 3185, 5530*}  24  28
26 {2, 3, 5, 7, 13, 17, 19, 28, 35, 38, 61, 161, 263, 374, 475, 653, 668, 816, 914, \atop 1073, 1841, 2353, 2794, 3176, 4278*, 4845*, 5305*, 6803*, 7748*, 8618*}  30  27
27 {2, 3, 5, 7, 13, 17, 19, 31, 52, 58, 101, 112, 209, 244, 281, 288, 326, 449, 468, \atop 585, 718, 4814*, 5478*, 7622*}  24  28
28 {2, 3, 5, 7, 13, 17, 19, 35, 68, 86, 88, 89, 98, 102, 141, 160, 689, 785, 840, 1140, \atop 1730, 1978, 2187, 3315}  24  27
29 {2, 3, 5, 7, 13, 17, 19, 44, 73, 85, 132, 135, 214, 221, 259, 358, 411, 426, 502, \atop 740, 987, 1033, 1594, 1626, 2530, 2551, 2669, 5090*, 7568*, 9821*}  30  28
30 {2, 3, 5, 7, 13, 17, 19, 32, 41, 44, 45, 75, 82, 99, 107, 292, 338, 371, 1108, 2983, \atop 4783*, 7932*}  22  27
31 {2, 3, 5, 7, 13, 17, 19, 31, 43, 45, 50, 52, 57, 81, 137, 172, 291, 472, 497, 502, \atop 1003, 1746, 2007, 2115, 2226, 2318, 6116*, 7580*}  28  28
32 {2, 3, 5, 7, 13, 17, 19, 31, 35, 51, 57, 59, 65, 73, 85, 106, 124, 303, 318, 481, 503, \atop 507, 681, 1624, 2633, 4186*, 4945*}  27  27
33 {2, 3, 5, 7, 13, 17, 19, 31, 44, 49, 52, 70, 71, 82, 85, 129, 138, 236, 249, 327, 704, \atop 1373, 1406, 1477, 3370*, 3430*}  26  28

Table 6: Primes of the form L_{k}^{(n)}, continued

number of est. # of

n k for which L_{k}^{(n)} is prime or prp(*) primes for primes for

k ≤ 10000 k ≤ 10000
34 {2, 3, 5, 7, 13, 17, 19, 31, 73, 85, 104, 135, 244, 296, 317, 360, 366, 373, 397, \atop 470, 1238, 2118, 2125, 2594, 5870*, 8742*}  26  27
35 {2, 3, 5, 7, 13, 17, 19, 31, 38, 50, 91, 97, 109, 132, 276, 361, 535, 1281, 1720, \atop 2285, 2302, 3971*, 4322*, 5177*, 7336*}  25  28
36 2, 3, 5, 7, 13, 17, 19, 31, 53, 117, 230, 298, 367, 701, 797, 846, 1008, 2122, 2210  19  27
37 2, 3, 5, 7, 13, 17, 19, 31, 69, 101, 341, 349, 577, 1147, 1963, 4542*, 8999*  17  28
38 {2, 3, 5, 7, 13, 17, 19, 31, 44, 50, 58, 70, 77, 89, 145, 181, 197, 211, 247, 460, \atop 475, 498, 579, 625, 687, 1288, 1736, 1740, 4172*, 7810*, 9629*}  31  28
39 {2, 3, 5, 7, 13, 17, 19, 31, 52, 85, 91, 243, 867, 1106, 1167, 1633, 2684, 2917, \atop 3733*, 4593*, 5055*}  21  28
40 {2, 3, 5, 7, 13, 17, 19, 31, 47, 56, 64, 70, 154, 230, 714, 995, 2478, 3965*, 6837*, \atop 8498*}  20  28
41 {2, 3, 5, 7, 13, 17, 19, 31, 45, 81, 91, 109, 131, 236, 405, 616, 803, 2886, 3875*, \atop 5014*, 7930*, 9405*}  22  28
42 {2, 3, 5, 7, 13, 17, 19, 31, 53, 77, 95, 111, 119, 429, 463, 729, 879, 904, 1182, \atop 3467*, 5562*, 6347*}  22  28
43 {2, 3, 5, 7, 13, 17, 19, 31, 50, 75, 81, 99, 192, 315, 338, 362, 369, 499, 1202, \atop 1926, 2304, 6049*}  22  28
44 {2, 3, 5, 7, 13, 17, 19, 31, 93, 99, 179, 227, 337, 385, 550, 613, 795, 2506, 2627, \atop 3910*, 6169*}  21  28
45 {2, 3, 5, 7, 13, 17, 19, 31, 87, 127, 176, 219, 295, 331, 420, 498, 697, 814, 2174, \atop 2535, 6243*, 7158*, 8429*, 9065*}  24  28
46 {2, 3, 5, 7, 13, 17, 19, 31, 53, 65, 76, 93, 98, 154, 181, 194, 595, 644, 1829, 1994, \atop 2410, 3242, 7321*}  23  28
47 {2, 3, 5, 7, 13, 17, 19, 31, 55, 56, 97, 128, 185, 192, 304, 348, 405, 543, 631, 750, \atop 942, 1492, 1889, 2276, 4861*, 6206*, 6882*, 7001*, 7764*, 8146*}  30  28
48 {2, 3, 5, 7, 13, 17, 19, 31, 59, 69, 92, 123, 135, 283, 308, 387, 726, 897, 1325, \atop 3561*, 4130*, 5153*, 9109*}  23  28
49 {2, 3, 5, 7, 13, 17, 19, 31, 50, 52, 87, 92, 129, 131, 185, 287, 494, 706, 728, 793, \atop 1271, 1297, 1655, 1954, 2965, 3674*, 5129*, 5823*, 8847*, 9667*}  30  28
50 2, 3, 5, 7, 13, 17, 19, 31, 57, 99, 107, 116, 161, 290, 518, 685, 688, 1044, 7182*  19  28
51 {2, 3, 5, 7, 13, 17, 19, 31, 74, 97, 112, 184, 380, 382, 397, 411, 646, 3092, 6313*, \atop 7128*, 7917*}  21  28
52 {2, 3, 5, 7, 13, 17, 19, 31, 57, 62, 76, 95, 192, 223, 333, 752, 1518, 2479, 3980*, \atop 6056*, 7620*}  21  28
53 2, 3, 5, 7, 13, 17, 19, 31, 79, 115, 116, 128, 129, 141, 243, 348, 380, 503, 664, 1135, 1212, 1250, 2221, 2417, 3141, 3841*, 4322*, 5007*, 6038*, 6161*, 6521*, 7344*, 7385*  33  28

54 {2, 3, 5, 7, 13, 17, 19, 31, 59, 76, 82, 223, 285, 485, 791, 941, 1215, 1224, 1339, \atop 3649*, 3737*, 5594*, 5758*, 5907*}  24  28
55 {2, 3, 5, 7, 13, 17, 19, 31, 56, 112, 142, 309, 499, 607, 1109, 1648, 2866, 3170, \atop 4006*, 4345*, 5494*, 7059*}  22  28
56 {2, 3, 5, 7, 13, 17, 19, 31, 116, 178, 204, 303, 390, 475, 725, 1190, 2031, 5112*, \atop 5234*, 8130*, 9776*}  21  28
57 {2, 3, 5, 7, 13, 17, 19, 31, 62, 69, 70, 187, 201, 425, 596, 928, 1125, 1951, 6164*, \atop 7609*}  20  28
58 {2, 3, 5, 7, 13, 17, 19, 31, 82, 83, 92, 94, 112, 515, 793, 1117, 1385, 1471, 3503*, \atop 6102*, 8559*}  21  28
59 2, 3, 5, 7, 13, 17, 19, 31, 64, 68, 2260, 8086*, 9189*  13  28
60 2, 3, 5, 7, 13, 17, 19, 31, 99, 113, 172, 238, 576, 1877, 5904*, 8860*  16  28
61 {2, 3, 5, 7, 13, 17, 19, 31, 61, 64, 68, 165, 291, 480, 1140, 1214, 1371, 2384, 2717, \atop 3773*, 4203*, 5534*, 6924*}  23  28
62 2, 3, 5, 7, 13, 17, 19, 31, 61, 68, 74, 131, 287, 593, 798, 4705*, 4827*, 5384*  18  28
63 {2, 3, 5, 7, 13, 17, 19, 31, 61, 70, 92, 116, 135, 145, 152, 377, 387, 437, 603, 690, \atop 695, 803, 1215, 1217, 1367, 1781, 2347, 2406, 7764*, 9297*}  30  28
64 {2, 3, 5, 7, 13, 17, 19, 31, 61, 77, 113, 163, 265, 351, 369, 824, 906, 2589, 2731, \atop 3516*, 4820*, 9498*}  22  28
65 {2, 3, 5, 7, 13, 17, 19, 31, 61, 81, 93, 175, 276, 307, 382, 804, 1279, 1668, 2067, \atop 2189, 3235, 5452*}  22  28
66 {2, 3, 5, 7, 13, 17, 19, 31, 61, 76, 196, 340, 382, 391, 655, 1276, 1289, 1419, 1488, \atop 2314, 2795, 7465*, 8961*}  23  28
67 {2, 3, 5, 7, 13, 17, 19, 31, 61, 87, 116, 117, 207, 221, 226, 391, 402, 578, 733, \atop 961, 984, 1078, 1107, 2019, 3232, 6755*, 6799*, 7198*, 9892*}  29  28

Table 7: Primes of the form L_{k}^{(n)}, continued

number of est. # of

n k for which L_{k}^{(n)} is prime or prp(*) primes for primes for

k ≤ 10000 k ≤ 10000
68 {2, 3, 5, 7, 13, 17, 19, 31, 61, 107, 131, 139, 241, 369, 388, 435, 577, 782, 813, \atop 1605, 1730, 1770, 5429*, 5482*, 7001*, 7277*, 7635*, 8019*}  28  28
69 {2, 3, 5, 7, 13, 17, 19, 31, 61, 70, 81, 94, 116, 146, 167, 176, 185, 237, 463, 563, \atop 722, 1501, 1953, 3049, 5437*}  25  28
70 {2, 3, 5, 7, 13, 17, 19, 31, 61, 98, 123, 124, 187, 285, 582, 613, 761, 826, 1127, \atop 1199, 2723, 3966*, 5867*, 6575*, 7888*}  25  28
71 {2, 3, 5, 7, 13, 17, 19, 31, 61, 103, 115, 129, 187, 238, 425, 1349, 1688, 2354, \atop 2554, 5197*, 8616*}  21  28
72 {2, 3, 5, 7, 13, 17, 19, 31, 61, 113, 386, 393, 443, 811, 1045, 1229, 2032, 3721*, \atop 5478*, 5935*, 6610*, 7391*, 7406*, 7664*, 7769*, 9063*}  26  28
73 {2, 3, 5, 7, 13, 17, 19, 31, 61, 87, 93, 242, 401, 409, 495, 604, 772, 893, 1682, \atop 4864*, 5852*}  21  28
74 2, 3, 5, 7, 13, 17, 19, 31, 61, 93, 99, 101, 199, 452, 823, 1934, 2994  17  28
75 {2, 3, 5, 7, 13, 17, 19, 31, 61, 81, 123, 166, 213, 370, 515, 763, 2210, 2512, 2840, \atop 3177, 8727*, 9893*}  22  28
76 {2, 3, 5, 7, 13, 17, 19, 31, 61, 128, 146, 261, 304, 491, 1005, 1032, 1229, 1671, \atop 1887, 2835, 3723*, 3836*, 9200*}  23  28
77 {2, 3, 5, 7, 13, 17, 19, 31, 61, 133, 142, 154, 182, 187, 206, 444, 604, 796, 839, \atop 916, 1152, 1528, 1541, 2222, 3002, 3662*, 3768*, 5792*, 7384*, 9444*, 9495*}  31  28
78 {2, 3, 5, 7, 13, 17, 19, 31, 61, 88, 368, 555, 719, 1101, 1418, 1904, 4475*, 4676*, \atop 5287*, 5585*}  20  28
79 {2, 3, 5, 7, 13, 17, 19, 31, 61, 81, 91, 161, 251, 476, 535, 590, 662, 814, 841, 971, \atop 1097, 1205, 2967, 3052, 5403*, 6036*, 7671*}  27  28
80 {2, 3, 5, 7, 13, 17, 19, 31, 61, 87, 93, 249, 366, 461, 528, 535, 632, 675, 844, \atop 1157, 1894, 2068, 2241, 2849, 3617*, 6028*, 7381*, 8614*}  28  28
81 {2, 3, 5, 7, 13, 17, 19, 31, 61, 99, 141, 233, 235, 290, 425, 535, 615, 649, 1317, \atop 1722, 5129*, 5831*, 8044*, 8595*, 8681*}  25  28
82 2, 3, 5, 7, 13, 17, 19, 31, 61, 161, 286, 287, 788, 2402, 6383*, 7236*, 8738*  17  28
83 {2, 3, 5, 7, 13, 17, 19, 31, 61, 249, 422, 423, 1031, 1062, 1180, 2637, 2836, 4919*, \atop 5641*, 8043*, 8197*}  21  28
84 {2, 3, 5, 7, 13, 17, 19, 31, 61, 95, 219, 303, 736, 1120, 1447, 1590, 2076, 2788, \atop 4163*, 4490*}  20  28
85 {2, 3, 5, 7, 13, 17, 19, 31, 61, 127, 221, 740, 1607, 3139, 3800*, 5533*, 8133*, \atop 9747*}  18  28
86 2, 3, 5, 7, 13, 17, 19, 31, 61, 93, 299, 379, 416, 470, 606, 662, 1791, 2908, 3999*  19  28
87 {2, 3, 5, 7, 13, 17, 19, 31, 61, 109, 121, 269, 326, 367, 551, 593, 883, 1083, 3036, \atop 3294, 5433*, 8169*, 9523*}  23  28
88 2, 3, 5, 7, 13, 17, 19, 31, 61, 107, 112, 129, 493, 1173, 1549, 3407*, 3424*, 5895*  18  28
89 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 164, 169, 1829, 1880, 2888, 3408*, 3694*, \atop 5173*, 5567*, 7612*, 7983*}  21  28
90 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 202, 256, 262, 297, 373, 383, 485, 844, 3390*, \atop 5261*, 5533*, 6743*, 7572*}  23  28
91 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 169, 201, 250, 526, 570, 731, 807, 964, 1062, \atop 2515, 2908, 3139}  22  28
92 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 164, 170, 196, 215, 225, 284, 353, 375, 379, \atop 491, 628, 668, 1148, 1888, 2135, 4069*, 6331*, 6483*, 7904*}  29  28
93 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 112, 146, 225, 470, 568, 599, 654, 941, 993, \atop 3012, 7306*}  21  28
94 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 159, 325, 581, 708, 743, 1260, 1527, 1983, \atop 4575*, 6507*, 7747*}  21  28
95 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 176, 181, 193, 219, 283, 348, 387, 392, 527, 549, 761, 766, 848, 852, 911, 1041, 1067, 3721*, 3914*, 4304*, 5552*, 5905*, 7409*  33  28

96 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 125, 166, 184, 287, 316, 392, 822, 1252, 2095, \atop 2185, 3056, 3235, 3663*, 7381*, 8634*}  25  28
97 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 104, 213, 274, 697, 1982, 2908, 3678*, 4236*  18  28
98 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 161, 221, 478, 591, 748, 825, 860, 943, 1488, \atop 1567, 4615*, 5292*, 8338*}  23  28
99 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 129, 261, 348, 639, 1301, 1531, 4151*, 6775*  18  28
100 {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 124, 179, 211, 243, 531, 599, 814, 934, 1529, \atop 3803*, 4768*, 5496*, 6554*, 7858*, 8764*, 9083*, 9976*}  27  28

2000 Mathematics Subject Classification: Primary 11A41; Secondary 11B39. Keywords: prime numbers, generalized Fibonacci and Lucas numbers.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000073}, \underline{A000078}, \underline{A001591}, \underline{A001592}, \underline{A001605}, \underline{A001606}, \underline{A001644}, \underline{A005478}, \underline{A005479}, \underline{A066178}, \underline{A073817}, \underline{A074048}, \underline{A074584}, \underline{A079262}, \underline{A092835}, \underline{A092836}, \underline{A104534}, \underline{A104535}, \underline{A104576}, \underline{A104577}, \underline{A104621}, \underline{A104622}, \underline{A105753}, \underline{A105754}, \underline{A105755}, \underline{A105756}, \underline{A105757}, \underline{A105758}, \underline{A105759}, \underline{A105760}, \underline{A105761}, \underline{A105762}, \underline{A105763}, \underline{A105764}, \underline{A105765}, \underline{A105766}, \underline{A105767}, and \underline{A105768}.)

Received April 19 2005; revised version received September 5 2005. Published in Journal of Integer Sequences, September 20 2005.

Return to Journal of Integer Sequences home page.