mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2004-10-23, 06:39   #1
Heck
 
Heck's Avatar
 
Oct 2004

112 Posts
Default 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
Heck is offline   Reply With Quote
Old 2004-10-23, 07:50   #2
andi314
 
andi314's Avatar
 
Nov 2002

10010102 Posts
Default

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
andi314 is offline   Reply With Quote
Old 2004-10-23, 11:42   #3
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

10010101001002 Posts
Default

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
ET_ is offline   Reply With Quote
Old 2004-10-25, 13:15   #4
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

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.
Andi47 is offline   Reply With Quote
Old 2004-10-27, 19:52   #5
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

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
File Type: zip sieve_1to200k.zip (86.0 KB, 163 views)
Andi47 is offline   Reply With Quote
Old 2004-10-28, 10:54   #6
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

9B216 Posts
Default

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
Andi47 is offline   Reply With Quote
Old 2004-10-28, 11:18   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Thumbs down

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???
R.D. Silverman is offline   Reply With Quote
Old 2004-10-28, 11:18   #8
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

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
File Type: zip 10^9999999+1_p=7_to_10k.zip (6.4 KB, 164 views)
Andi47 is offline   Reply With Quote
Old 2004-10-28, 11:32   #9
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2×17×73 Posts
Default

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
Andi47 is offline   Reply With Quote
Old 2004-10-28, 11:34   #10
smh
 
smh's Avatar
 
"Sander"
Oct 2002
52.345322,5.52471

29×41 Posts
Thumbs down

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
smh is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Smallest prime with a digit sum of 911 Stargate38 Puzzles 6 2014-09-29 14:18
Odditities in the 100 Million Digit Prime Award joblack Information & Answers 20 2009-11-11 10:27
When will the first 10 million digit prime be reported? Uncwilly Lounge 13 2009-07-22 13:56
100 MILLION DIGIT NUMBER lpmurray Software 8 2004-05-31 19:22
The first (non-merseinne) 10 million-digit prime number!!! ron29730 Miscellaneous Math 17 2004-05-15 20:23

All times are UTC. The time now is 10:24.

Wed Dec 2 10:24:20 UTC 2020 up 83 days, 7:35, 1 user, load averages: 1.76, 2.12, 1.99

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.