mersenneforum.org Smallest ten-million-digit prime
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2004-10-23, 06:39 #1 Heck     Oct 2004 3 Posts Smallest ten-million-digit prime 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
 2004-10-23, 07:50 #2 andi314     Nov 2002 10010102 Posts 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
2004-10-23, 11:42   #3
ET_
Banned

"Luigi"
Aug 2002
Team Italia

17×283 Posts

Quote:
 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

2004-10-25, 13:15   #4
Andi47

Oct 2004
Austria

2×17×73 Posts

Quote:
 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.

2004-10-27, 19:52   #5
Andi47

Oct 2004
Austria

2×17×73 Posts

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.
Attached Files
 sieve_1to200k.zip (86.0 KB, 195 views)

 2004-10-28, 10:54 #6 Andi47     Oct 2004 Austria 2×17×73 Posts 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
2004-10-28, 11:18   #7
R.D. Silverman

Nov 2003

11101001001002 Posts

Quote:
 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???

2004-10-28, 11:18   #8
Andi47

Oct 2004
Austria

2×17×73 Posts

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.
Attached Files
 10^9999999+1_p=7_to_10k.zip (6.4 KB, 194 views)

2004-10-28, 11:32   #9
Andi47

Oct 2004
Austria

2·17·73 Posts

Quote:
 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

Last fiddled with by Andi47 on 2004-10-28 at 11:39 Reason: Just another bit of information

2004-10-28, 11:34   #10
smh

"Sander"
Oct 2002
52.345322,5.52471

100101001012 Posts

Quote:
 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.

Last fiddled with by smh on 2004-10-28 at 11:40

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Puzzles 6 2014-09-29 14:18 joblack Information & Answers 20 2009-11-11 10:27 Uncwilly Lounge 13 2009-07-22 13:56 lpmurray Software 8 2004-05-31 19:22 ron29730 Miscellaneous Math 17 2004-05-15 20:23

All times are UTC. The time now is 12:18.

Sat Apr 10 12:18:53 UTC 2021 up 2 days, 6:59, 1 user, load averages: 1.81, 2.10, 2.00

Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.