From tonyforbes@ltkz.demon.co.ukTue May 14 20:09:25 1996
Date: Tue, 14 May 1996 10:32:40 EDT
From: Tony Forbes
To: Multiple recipients of list NMBRTHRY
Subject: Primes 2^n + m
Primes 2^n + m
--------------
Tony Forbes
Following on from [1], I report some more primes of the form 2^n + m
(with large n and small |m| > 1), none of which currently appear in
Chris Caldwell's "Titanic" database. The largest is the 4249-digit
number 2^14114 - 3.
In the table I give the percentage of either N - 1 or N + 1 that can be
factorized. Most of the factors come from the Cunningham files of prime
divisors of 2^k + 1 and 2^k - 1. A few additional primes (also included
in the percentages) are shown in columns 4 and 5, but only in the cases
2^5112 - 5, 2^3510 + 7 and 2^8451 - 9 were some of them necessary to
increase the factorized proportion of N +/- 1 beyond 1/3.
In all cases sufficient of N +/- 1 has been factorized into primes to
complete the primality proofs using, for example, Theorems 5 and 17 of
[4]. The method is the same as in [1, 2, 3]. To perform the computations
I was helped considerably by a Dubner Cruncher (attached to a 486), and
programs for the Cruncher written by Harvey Dubner, Robert Dubner and
Chris Caldwell.
The d'th cyclotomic polynomial evaluated at 2 is denoted by Td.
N | N+/-1 | percent | d | Factors of Td
-------------+-------+----------+--------+---------------
2^3954 - 3 | N-1 | 39.24% | 3952 | 418066273
2^14114 - 3 | N-1 | 33.35% | |
2^4552 + 3 | N+1 | 38.13% | 9100 | 5305301
| | | | 2892634981601
2^4532 - 5 | N+1 | 47.50% | |
2^5112 - 5 | N+1 | 33.47% | 2555 | 1783391
| | | 5110 | 35771 * 756281
2^3775 - 7 | N-1 | 39.21% | |
2^3510 + 7 | N+1 | 77.88% | 7014 | See below
2^8451 - 9 | N+1 | 41.25% | 4224 | See below
2^4557 + 9 | N-1 | 42.07% | |
2^5194 - 15 | N-1 | 36.68% | 2595 | 25306441
| | | 5190 | 174980851
2^8824 - 15 | N-1 | 54.73% | 4410 | 15562891
2^8628 - 17 | N+1 | 41.59% | |
-------------+-------+----------+--------+---------------
The divisors T7014 of 2^3507 + 1 and T4224 of 2^2112 + 1 are completely
factorized into primes. We have
T7014 = 385771 * 2684783851 * 35756859979 * 119788760323 * P563
and
T4224 = 1951050013441 * P374,
where
P563 = 76414858207866155709785880100873870857964287055637
37202884327372655748003049334063102194428055652514
44624467721476250175549819333863874108236326125494
48994224571466694823940005106890511366355552799328
08738919321502987399106187425016161444961419933589
31595859739197526588045034852693755224828111602990
73295307202835454119067349550590917530418669215152
14628784274371463682881226017445424175799327508904
23830255669853903382542681903035177154211253624861
91861498109321947022138862109143731755082446448106
47212168512876800078718896135051798329273723692844
5283338680443
and
P374 = 10669057300390045867833374036971624099228922191376
93649849537378033901514740752946087767374951927509
63021376172846985379248841265587498703218721874883
77748723377107100510236943900243886843671791321613
86071197648405889845776289936643742996332354148231
56962261076949880893414329037398105558169481751998
59279584577238288746485705222083221221189507009478
732645996997984581346561
The factors were found using Pollard p-1. The primes P563 and P374 were
verified by the Adleman-Pomerance-Rumely-Cohen-Lenstra test in the
UBASIC program APRT-CLE.
Although I am unwilling to guarantee its completeness (this is an area
which is particularly sensitive to computer errors), it is perhaps worth
making a list of 1000+ digit probable primes 2^n + m that remain to be
verified.
m | n [Search limit 13520]
----+-----------------------------------------------------------
-3 | 6756, 8770, 10572
3 | 4002, 4060, 4062, 5547, 8739
-5 | 8492
5 | [none]
-7 | 12819
7 | 3454, 3864, 3870, 8970, 12330, 13330
-9 | 3365, 8451, 8577, 9699, 9725
9 | 3749, 4375, 4494, 5278, 5567, 9327, 10129, 12727
-15 | 3833, 4394, 6017, 6070, 9955, 11399, 12250
15 | 3882, 3940, 4840, 7518, 11118, 11552, 11733, 12738, 12858
-17 | 3632, 4062, 5586, 5904, 6348, 9224, 13136
17 | 3381, 4441, 7065
References
----------
[1] A. D. Forbes, "2^5630 - 3 is prime", NMBRTHRY, April 1996.
[2] F. Morain, "(2^10501+1)/3 is prime", NMBRTHRY, April 1996.
[3] F. Morain, "(2^12391+1)/3 is prime", NMBRTHRY, April 1996.
[4] John Brillhart, D. H. Lehmer and J. L. Selfridge, "New primality
criteria and factorizations of 2^m +/- 1", Math. Comp, 29 (1975), 620-
647.
--
Tony