Smallest ten-million-digit prime

[Heck]

Eventually we will want to find the smallest ten-million-digit prime.

mighty big number, factor

10^9999999 + 1, 7
10^9999999 + 3, 23
10^9999999 + 7, 11852969
10^9999999 + 9, 47
10^9999999 + 11, 3
10^9999999 + 13, 277
10^9999999 + 17, 3
10^9999999 + 19, 7583
10^9999999 + 21, 718453
10^9999999 + 23, 3
10^9999999 + 27, 13
10^9999999 + 29, 3
10^9999999 + 31, 821879

etc..

*Heck

[andi314]

but this will only help to tell you that the numbers are NOT PRIME because the primilty tests for such big numbers ( without a suitable form like Mersenne Numbers) will take some hundred years of computing to verify that it is prime

[ET_]

Originally Posted by andi314

but this will only help to tell you that the numbers are NOT PRIME because the primilty tests for such big numbers ( without a suitable form like Mersenne Numbers) will take some hundred years of computing to verify that it is prime

It is partially what we are doing for Mersennes at LMH > 79.2M.

Maybe it is useful to have a table of factored numbers from where someone else will start checking primality.

My hint: avoiding sums wirh numbers of the form 3n+2, as they will always have 3 as a factor will spped up search.

Luigi

[Andi47]

Originally Posted by Heck

Eventually we will want to find the smallest ten-million-digit prime.

mighty big number, factor

10^9999999 + 1, 7
10^9999999 + 3, 23
10^9999999 + 7, 11852969
10^9999999 + 9, 47
10^9999999 + 11, 3
10^9999999 + 13, 277
10^9999999 + 17, 3
10^9999999 + 19, 7583
10^9999999 + 21, 718453
10^9999999 + 23, 3
10^9999999 + 27, 13
10^9999999 + 29, 3
10^9999999 + 31, 821879

etc..

This gives us the following modulo-results, if somebody wants to start sieving:

let a be 10^9999999; let b be 1, 3, 7, ...

a+1 ≡ 2 mod 3
a+1 ≡ 1 mod 5 (obviously)
a+1 ≡ 0 mod 7
a+1 ≡ 0 mod 11 (each number of the form 1000000....00001 which has an even number of digits is divisible by 11; (a+1)/11 = 90909090.......09091; 9999998 digits)
a+1 ≡ 0 mod 13
a+1 ≡ ??? mod 17
a+1 ≡ ??? mod 19
a+1 ≡ 21 mod 23
a+1 ≡ ??? mod 29, 31, 37, 41, 43
a+1 ≡ 39 mod 47

It gives us also two more factors of 10^9999999+1, namely 11 and 13.

[Andi47]

I started some sieving, the sieve data for 10^9999999+1 to 10^9999999+200k is attatched to this posting.

I sieved out numbers divisible by the primes p = 3, 5, 7, 11 and 13.

Heck, if You can provide some more small divisors of this huge numbers, especially 17, 19, ..., I will continue sieving.

[Andi47]

I just did some trial division on 10^9999999+1 - the lowest odd 10 million digit number and found another small factor: 19 divides 10^9999999+1.

Other factors found so far (see also :this thread)

7 - found by heck
13 - can be read out of hecks table
11 - "manual" factoring using divisibility rule for p=11

[R.D. Silverman]

Originally Posted by Andreas Schinde

I just did some trial division on 10^9999999+1 - the lowest odd 10 million digit number and found another small factor: 19 divides 10^9999999+1.

Other factors found so far (see also :this thread)

7 - found by heck
13 - can be read out of hecks table
11 - "manual" factoring using divisibility rule for p=11

Some intelligent, or with an understanding of 8th grade level first year
algebra might observe that if a is odd, then 10^(ab) + 1 is divisible by
10^b+1.

What is it that compels people to blindly throw a calculator or computer
at a problem *BEFORE* doing any thinking about the mathematics involved???

[Andi47]

I did some more trial factoring on 10^9999999+1, no more divisor up to 10000.

The attatched file lists the modulo residues 10^9999999+1 == c mod p for p = 7 to 10k.

[Andi47]

Originally Posted by Bob Silverman

Some intelligent, or with an understanding of 8th grade level first year
algebra might observe that if a is odd, then 10^(ab) + 1 is divisible by
10^b+1.

What is it that compels people to blindly throw a calculator or computer
at a problem *BEFORE* doing any thinking about the mathematics involved???

I dont't know how Heck figured out the divisor 7 (maybe it's this bit of algebra you mentioned with b=1001 which gives the factors 7, 11 and 13)

I figured out 11 and 13 *without* using a calculator by looking at heck's table in this thread and by rule that 10^a+1 is divisible by 11 if a is odd.

Edit: Just to mention it: divisibility by 10^b+1 gives us the factors
10^3+1 = 7*11*13
10^9+1 = 7*11*13*19*52579

and so on for b = 239, 4649 and 239*3, 239*9, 239*4649, 239*4649*3, 4649*3, 4649*9

[smh]

Originally Posted by Andreas Schinde

Other factors found so far (see also :this thread)

Moved things to this thread. Had nothing to do with the subject of the other.