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