mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Prime Gap Searches

Reply
 
Thread Tools
Old 2019-12-17, 22:39   #12
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·7·137 Posts
Default

Hi storm5510.

It appears you are looking at gaps between prime numbers which occur between what we would refer to as small numbers. At 160,711, the largest number you quote, there are many, many prime numbers, so gaps will remain small.

If you are looking for a filter, then either small or large gaps are interesting. The smallest being a gap of 2 (the gap between the primes 2 and 3 has already been discovered, and there is no other example of a gap of length 1). Small gaps of just 2 are quite common. These gaps constitute the gap between twin primes, and this is an area of intense interest to mathematicians right now.

The larger gaps in your search region are really not large at all. For numbers smaller than 160,711, the largest gap is 86, found between 155,921 and 156,007. You have to wait until you get to 360,653 to find a larger one.

At this Mersenneforum site we have extended work carried out over the years (we stand on the shoulders of giants) so that now we have found all the larger gaps which exist following primes smaller than 2^64, or 18,446,744,073,709,551,616

The smallest gap where we do not know the first instance is 1,432. The smallest prime we know that this gap exists is 84,218,359,021,503,505,748,941 but there are likely to be many smaller instances with this gap size. My best guess is that the smaller of the two primes that make up the first instance gap of length exactly 1,432 is less than 100,000,000,000,000,000,000.

Right now I am looking at gaps of a given length. For example I would like to find a gap of exactly 112,738. This is the smallest gap size which has not been found.

Also the largest proven gap is always interesting - at the moment this is 6,582,144. To find a larger gap would take a top-range desktop computer a year to find.

Finally we are looking at gaps which are much larger than expected - a gap of 8,350 follows the prime 293,703,234,068,022,590,158,723,766,104,419,463,425,709,075,574,811,762,098,588,798,217,895,728,858,676,728,143,227 and this gap is hugely larger than expected, over 41 times longer than we might expect. Beating this will require many computer cpu's

A problem you will face is making your code efficient. We had the benefit of fabulously efficient code to look at all gaps < 2^64, but that code code does not work above that level.

Last fiddled with by robert44444uk on 2019-12-17 at 22:42
robert44444uk is offline   Reply With Quote
Old 2019-12-18, 01:22   #13
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22·11·41 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
Hi storm5510.

It appears you are looking at gaps between prime numbers which occur between what we would refer to as small numbers. At 160,711, the largest number you quote, there are many, many prime numbers, so gaps will remain small.

If you are looking for a filter, then either small or large gaps are interesting. The smallest being a gap of 2 (the gap between the primes 2 and 3 has already been discovered, and there is no other example of a gap of length 1). Small gaps of just 2 are quite common. These gaps constitute the gap between twin primes, and this is an area of intense interest to mathematicians right now.

The larger gaps in your search region are really not large at all. For numbers smaller than 160,711, the largest gap is 86, found between 155,921 and 156,007. You have to wait until you get to 360,653 to find a larger one.

At this Mersenneforum site we have extended work carried out over the years (we stand on the shoulders of giants) so that now we have found all the larger gaps which exist following primes smaller than 2^64, or 18,446,744,073,709,551,616

The smallest gap where we do not know the first instance is 1,432. The smallest prime we know that this gap exists is 84,218,359,021,503,505,748,941 but there are likely to be many smaller instances with this gap size. My best guess is that the smaller of the two primes that make up the first instance gap of length exactly 1,432 is less than 100,000,000,000,000,000,000.

Right now I am looking at gaps of a given length. For example I would like to find a gap of exactly 112,738. This is the smallest gap size which has not been found.

Also the largest proven gap is always interesting - at the moment this is 6,582,144. To find a larger gap would take a top-range desktop computer a year to find.

Finally we are looking at gaps which are much larger than expected - a gap of 8,350 follows the prime 293,703,234,068,022,590,158,723,766,104,419,463,425,709,075,574,811,762,098,588,798,217,895,728,858,676,728,143,227 and this gap is hugely larger than expected, over 41 times longer than we might expect. Beating this will require many computer cpu's

A problem you will face is making your code efficient. We had the benefit of fabulously efficient code to look at all gaps < 2^64, but that code code does not work above that level.

Thank you for your reply. I know this took some effort to write and i appreciate it greatly.

When I first saw this category a decade ago, after joining the forum, I thought this was dedicated to finding gaps of two, only. It was not until I read further, that I saw the advancement.

You mention 2^64. I did a test with my program and it handles values above this with no problem. I will place a sample at the bottom. However, it does not seem to run quite as fast. As for the "choke," it pauses for program for 10 milliseconds between iterations. I removed it for the test. What a difference.

Efficiency: I imagine you are familiar with the term "library-stripping." The compiler only pulls in from the library the routines in the code. What I have does not do this, I do not believe. Without the white-space for readability, I have 45 lines of code. The compiler produces a 118K byte executable. There are no external dependencies. I looked at the compiled program with a hex editor to see if there is anything in there it does not use. The majority is binary gibberish, to me. Some references about MinGW-W64 near the end. After that, all zero's.

Looking for specific gap sizes is possible. This uses a configuration file. Starting values are read from there, then updated every 30 seconds while running, then updated again when stopped. I can add operator types indicators to this. A specific range to test is also possible by adding it to the configuration and adjusting the programs code.

I sometimes refer to myself as an "antique programmer." I started in 1988. This, and the fact that I am 64 years old. I am retired and I must do something to keep the brain cells going. It is use it, or lose it.


Code:
12-17-2019 19:31:28:  18446744073709791041 - 18446744073709790921 = 120
12-17-2019 19:31:28:  18446744073709791233 - 18446744073709791131 = 102
12-17-2019 19:31:29:  18446744073709791647 - 18446744073709791473 = 174
12-17-2019 19:31:29:  18446744073709792303 - 18446744073709792133 = 170
12-17-2019 19:31:29:  18446744073709792579 - 18446744073709792411 = 168
12-17-2019 19:31:29:  18446744073709792969 - 18446744073709792837 = 132
storm5510 is offline   Reply With Quote
Old 2019-12-18, 10:16   #14
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

35768 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Thank you for your reply. I know this took some effort to write and i appreciate it greatly.

When I first saw this category a decade ago, after joining the forum, I thought this was dedicated to finding gaps of two, only. It was not until I read further, that I saw the advancement.

You mention 2^64. I did a test with my program and it handles values above this with no problem. I will place a sample at the bottom. However, it does not seem to run quite as fast. As for the "choke," it pauses for program for 10 milliseconds between iterations. I removed it for the test. What a difference.

Efficiency: I imagine you are familiar with the term "library-stripping." The compiler only pulls in from the library the routines in the code. What I have does not do this, I do not believe. Without the white-space for readability, I have 45 lines of code. The compiler produces a 118K byte executable. There are no external dependencies. I looked at the compiled program with a hex editor to see if there is anything in there it does not use. The majority is binary gibberish, to me. Some references about MinGW-W64 near the end. After that, all zero's.

Looking for specific gap sizes is possible. This uses a configuration file. Starting values are read from there, then updated every 30 seconds while running, then updated again when stopped. I can add operator types indicators to this. A specific range to test is also possible by adding it to the configuration and adjusting the programs code.

I sometimes refer to myself as an "antique programmer." I started in 1988. This, and the fact that I am 64 years old. I am retired and I must do something to keep the brain cells going. It is use it, or lose it.


Code:
12-17-2019 19:31:28:  18446744073709791041 - 18446744073709790921 = 120
12-17-2019 19:31:28:  18446744073709791233 - 18446744073709791131 = 102
12-17-2019 19:31:29:  18446744073709791647 - 18446744073709791473 = 174
12-17-2019 19:31:29:  18446744073709792303 - 18446744073709792133 = 170
12-17-2019 19:31:29:  18446744073709792579 - 18446744073709792411 = 168
12-17-2019 19:31:29:  18446744073709792969 - 18446744073709792837 = 132
As one retired 60-something to another, I agree "use those brain cells!"

The main trick we adopted to find records gaps in the 4e18- to 2^64 range was to limit our searching to areas where a gap of 1000 might occur. (The smallest gap for which a first instance gap was not known was 1366) To make this efficient, instead of checking every gap, a counter jumped 850 at each iteration and search forward for gaps of 150 or more. If it found one, the code checked back to find the previous prime.

The c code we used for the search can be found in this thread, post 207:

https://www.mersenneforum.org/showthread.php?t=22187

And here:

https://github.com/primegap-list-pro...2f79bc2f6ab235

There is one member of this group looking beyond 2^64 - ATH - you might want to PM him to find out what he is up to

Here is some really simple code for checking gaps >2^64 - this code checks the first 100,000 gaps above 2^64, and reports those >= 400. For benchmarking purposes this took 9.7 seconds on my desktop, working in the background. Effective code would be many times faster than this - about 100x.

Code:
#!/usr/bin/env perl
use warnings;
use strict;
use Timer::Runtime;
use Math::GMPz;
use Math::BigFloat lib=>"GMP";
use Math::Prime::Util qw/:all/;
use File::Slurp;
use v5.10;
use bignum;

$|=1;

my $n = 18_446_744_073_709_551_616; 
my $iterations = 100_000;
my $smallgap = 400;

for (my $k=0; $k <=$iterations ; $k++){ 
my $nextprime = next_prime($n);
my $gap = $nextprime-$n;
if ($gap >= $smallgap) {say $n," ",$nextprime," ", $gap;
}
$n = $nextprime; 
}
robert44444uk is offline   Reply With Quote
Old 2019-12-18, 16:15   #15
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

111000011002 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
As one retired 60-something to another, I agree "use those brain cells!"

The c code we used for the search can be found in this thread, post 207:

https://www.mersenneforum.org/showthread.php?t=22187

And here:

https://github.com/primegap-list-pro...2f79bc2f6ab235

There is one member of this group looking beyond 2^64 - ATH - you might want to PM him to find out what he is up to

Here is some really simple code for checking gaps >2^64 - this code checks the first 100,000 gaps above 2^64, and reports those >= 400. For benchmarking purposes this took 9.7 seconds on my desktop, working in the background. Effective code would be many times faster than this - about 100x.
Your sample looks like a C variant. As much as I hate to say this, I know nearly nothing about C. I have tried over the years. It loses me in a hurry. C is something which was not taught, locally, when I was younger. All this started after I graduated from trade-school.

What I used to write this with is a greatly modified variation of an old language I learned back in the late 1980's. I imagine you could figure out what this is fairly fast. Many programmers spent a lot of time writing a huge collection of libraries. Nearly 1,300 in all. Something so simple to me, back then, is now quite complex. At times, I struggle with it. I am reluctant to name it out of fear of being "chastised" because of it.

It is running at this time. I gave it a simple task. Search for anything with a gap of two. It found a half-million in roughly 90 minutes. Sometimes, programs can have problems after many hours of running, not just in the first few seconds. This is the purpose of my rather intense testing.

About using the brain cells, my father did continuously. He lived to be nearly 88 years old.
storm5510 is offline   Reply With Quote
Old 2019-12-19, 09:43   #16
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

111011111102 Posts
Default

Quote:
Originally Posted by storm5510 View Post
Your sample looks like a C variant. As much as I hate to say this, I know nearly nothing about C. I have tried over the years. It loses me in a hurry. C is something which was not taught, locally, when I was younger. All this started after I graduated from trade-school.

What I used to write this with is a greatly modified variation of an old language I learned back in the late 1980's. I imagine you could figure out what this is fairly fast. Many programmers spent a lot of time writing a huge collection of libraries. Nearly 1,300 in all. Something so simple to me, back then, is now quite complex. At times, I struggle with it. I am reluctant to name it out of fear of being "chastised" because of it.

It is running at this time. I gave it a simple task. Search for anything with a gap of two. It found a half-million in roughly 90 minutes. Sometimes, programs can have problems after many hours of running, not just in the first few seconds. This is the purpose of my rather intense testing.

About using the brain cells, my father did continuously. He lived to be nearly 88 years old.
It would be interesting to test your code against what we have been using for finding gaps between twin primes

https://www.mersenneforum.org/showthread.php?t=24303

So I set you a challenge to time your code to find the initial 10,000 twin primes in the range 1e23 and 1.1e23

I'll program this using Perl's big prime number crunching applications, in its suite https://metacpan.org/pod/Math::Prime::Util

If anyone wants to take on this challenge in another way, then please do!
robert44444uk is offline   Reply With Quote
Old 2019-12-19, 11:01   #17
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

35768 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
It would be interesting to test your code against what we have been using for finding gaps between twin primes

https://www.mersenneforum.org/showthread.php?t=24303

So I set you a challenge to time your code to find the initial 10,000 twin primes in the range 1e23 and 1.1e23

I'll program this using Perl's big prime number crunching applications, in its suite https://metacpan.org/pod/Math::Prime::Util

If anyone wants to take on this challenge in another way, then please do!
The following code produces 10000 twins in 1.05 seconds

Code:
#!/usr/bin/env perl
use warnings;
use strict;
use Math::Prime::Util qw/:all/;
use Math::BigInt lib => 'GMP';
use bignum;
use v5.10;
use Time::HiRes qw(gettimeofday time tv_interval);

$|=1;

my $low = 1e23;
my $high = 1e23+2.1391e7;
my $t0 = [gettimeofday];

my @twins = @{twin_primes($low, $high)};
say $low," ", $high, " ", scalar @twins;

my $duration = tv_interval($t0);
printf ("\nExecution time: %.2fs\n", $duration);
robert44444uk is offline   Reply With Quote
Old 2019-12-19, 14:38   #18
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

22×11×41 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
...So I set you a challenge to time your code to find the initial 10,000 twin primes in the range 1e23 and 1.1e23
I am glad you sent this. It revealed a problem in my code. My library does not seem to be working.

I ran a sample program which uses the same library and it produced what is in the screenshot. I do not believe I am using the library properly, based on what was in the sample that created this. I have much to do...
Attached Thumbnails
Click image for larger version

Name:	bigint.JPG
Views:	94
Size:	482.0 KB
ID:	21452  
storm5510 is offline   Reply With Quote
Old 2019-12-19, 15:28   #19
robert44444uk
 
robert44444uk's Avatar
 
Jun 2003
Oxford, UK

2·7·137 Posts
Default

Quote:
Originally Posted by storm5510 View Post
I am glad you sent this. It revealed a problem in my code. My library does not seem to be working.

I ran a sample program which uses the same library and it produced what is in the screenshot. I do not believe I am using the library properly, based on what was in the sample that created this. I have much to do...
I ran the two calculations in your screenshot and I got the same results i.e. for next prime after 2=^1024 and the value of 17^3000.

So I wondering why you are worried
robert44444uk is offline   Reply With Quote
Old 2019-12-20, 04:03   #20
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

111000011002 Posts
Default

Quote:
Originally Posted by robert44444uk View Post
I ran the two calculations in your screenshot and I got the same results i.e. for next prime after 2=^1024 and the value of 17^3000.

So I wondering why you are worried
Something went haywire in that program. I was not able to determine a cause. I remembered writing something far simpler just as a test. I found it, ran it, and it works. The sample below is greater than 2^64.

Code:
12-19-2019 22:28:16: 18446744073709552423 - 18446744073709552421 = 2
12-19-2019 22:28:16: 18446744073709554151 - 18446744073709554149 = 2
12-19-2019 22:28:16: 18446744073709558603 - 18446744073709558601 = 2
12-19-2019 22:28:16: 18446744073709558729 - 18446744073709558727 = 2
12-19-2019 22:28:17: 18446744073709563193 - 18446744073709563191 = 2
12-19-2019 22:28:17: 18446744073709563841 - 18446744073709563839 = 2
At present, it is hard-coded for a gap of two. I use a small config file so the last number is not lost when I stop it. It also updates this every 30 seconds. I intend to modify it in small steps, and place comments in the code as I go along. This small program can be made more flexible, using the config file, to set a gap size and a comparison operator such as =, >=, and so on.

I will give your timing test a go in the next few days. You say "twins" in your posting. Not knowing the gap, I will use two. I know what i have will take far longer than your snippet.
storm5510 is offline   Reply With Quote
Old 2019-12-20, 12:49   #21
sweety439
 
Nov 2016

1010110011002 Posts
Default

Well....
Attached Files
File Type: txt increasing prime gaps.txt (2.2 KB, 87 views)
sweety439 is offline   Reply With Quote
Old 2019-12-20, 13:30   #22
storm5510
Random Account
 
storm5510's Avatar
 
Aug 2009
U.S.A.

34148 Posts
Default

I did the code test earlier. I stripped the code down to what was necessary, compiled it and ran the test. It did far better than I was expecting. Check out the screen capture. The floating-point numbers and the ends are start time and end time. Take away some digits at both ends and use what is near the decimal point. 25.44 seconds.
Attached Thumbnails
Click image for larger version

Name:	gimps_test.JPG
Views:	107
Size:	27.7 KB
ID:	21456  
storm5510 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
If you find a prime... paulunderwood NeRDs 0 2014-02-03 05:09
Wanted Lists R.D. Silverman Cunningham Tables 1 2010-09-21 16:16
If you find a twin prime... MooooMoo Twin Prime Search 2 2006-05-11 23:38
True ignore lists? xilman Forum Feedback 1 2006-04-23 18:14
Will we find a new prime below M42? ATH Lounge 20 2006-03-27 18:36

All times are UTC. The time now is 14:47.

Mon Jan 25 14:47:23 UTC 2021 up 53 days, 10:58, 0 users, load averages: 2.71, 2.54, 2.46

Powered by vBulletin® Version 3.8.11
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.