mersenneforum.org  

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

Reply
 
Thread Tools
Old 2020-02-23, 16:57   #1
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default Gaps in k-almost primes relative to 2^k, a question

Consider gaps in k-almost primes (i.e. \Omega(n)=k), relative to the size of the smallest such number, 2k.
Let k\to \infty, we have the sequence
Code:
1
1.5
2.25
2.5
3.375
3.5
3.75
5.0625
5.25
5.5
5.625
6.25
6.5
7.59375
7.875
8.25
8.4375
8.5
8.75
9.375
9.5
9.75
11.390625
11.5
11.8125
12.25
12.375
12.65625
12.75
13.125
13.75
14.0625
14.25
14.5
14.625
15.5
15.625
16.25
17.0859375
17.25
17.71875
18.375
18.5
18.5625
18.984375
19.125
19.25
19.6875
20.5
20.625
21.09375
21.25
21.375
21.5
21.75
21.875
21.9375
22.75
23.25
23.4375
23.5
23.75
24.375
25.62890625
...
OEIS only comes up with A122943, the numerators of the numbers of this sequence, with little references.

Looking for record gaps, we have successive maxima (these, when multiplied by 2k, are eventually the record gaps between k-almost primes for almost all k):
Code:
gap         after n/2^k=
0.5         1
0.75        1.5
0.875       2.5
1.3125      3.75
1.640625    9.75
1.880859375 36.5625
1.904296875 3506216.064453125
It looks like a gap of 2 or greater is as hard to find as a gap with CSG ratio greater than 1.
Question is: are those gaps bounded?
mart_r is offline   Reply With Quote
Old 2020-03-29, 20:48   #2
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

11408 Posts
Default

Update: A gap greater than 2 is possible!
Code:
gap         after n/2^k=
0.5         1
0.75        1.5
0.875       2.5
1.3125      3.75
1.640625    9.75
1.880859375 36.5625
1.904296875 3506216.064453125
1.921875    17946832.921875
1.96875     44901649.8984375
2.21875     54738288.6875
This one came in just today, and ranks # 3 in largest gaps in my search up to 2^27, which will conclude tomorrow. I don't think I find another large gap in the time remaining.
Code:
1.9609375  105154231.0078125
Also, here's a list of successive minima. I used fractions in the left column, for reasons.
Code:
gap         after n/2^k=
1/2         1
1/4         2.25
1/8         3.375
1/16        8.4375
1/32        29.5
1/64        82.25
5/2048      86.49755859375
1/512       397.248046875
1/2048      2969.74951171875
1/4096      7943.359130859375
1/8192      39853.75
43/524288   155214.1249179840087890625
1/16384     199841.796875
1/32768     211470.312469482421875
1/131072    287586.8125
1/262144    1799287.749996185302734375
1/524288    22043660.546875
1/2097152   24139755.968749523162841796875
1/4194304   65777924.75
1/33554432  67956505.2499999701976776123046875
Meanwhile, I found A052130, in which it says, "m is sufficiently large precisely when 2^m > 3^(m-n), i.e., when m >= floor(n*log(3)/log(1.5)) = A117630(n+1) = A126281(n) for n > 1. (Robert G. Wilson v asks if this conjecture holds in a comment to A126281.)" - I don't see any reasons why this should not be true, as the formula is a direct consequence of the definition.

A126279 provides enough data to add a few more terms to the former sequence after we calculate how many odd numbers with 50-n+k factors there are up to 2^(50+k), for k=1...n*log(3)/log(1.5)-50. I think I could do it, but not before mid April, so if anyone is interested...
mart_r is offline   Reply With Quote
Old 2020-04-01, 22:50   #3
Bobby Jacobs
 
Bobby Jacobs's Avatar
 
May 2018

2×32×11 Posts
Default

Interesting. I wonder why the gap of 1.880859375 from 36.5625 to 38.443359375 stays as a record for so long.
Bobby Jacobs is offline   Reply With Quote
Old 2020-04-02, 19:36   #4
mart_r
 
mart_r's Avatar
 
Dec 2008
you know...around...

25·19 Posts
Default

Quote:
Originally Posted by Bobby Jacobs View Post
Interesting. I wonder why the gap of 1.880859375 from 36.5625 to 38.443359375 stays as a record for so long.
The density of the numbers in the sequence as given in my first post is increasing. There are roughly 0.5*x*log(x) numbers up to x, an estimate that's good to ± 5% for ~ 2^18 < x < 2^30. The 0.5 in this formula is actually decreasing as x gets larger, but I haven't yet worked out how exactly. Up to 2^23; 2^24; 2^25; 2^26; 2^27 there are, respectively, 10696; 16280; 24624; 37476; 56869 gaps >= 1. So it wouldn't surprise me if it takes exponentially longer to find the next maximum.

But it's quite a large gap in those gaps indeed.


BTW, there was another gap > 2 shortly after my last post. These are the 11 largest gaps for x < 2^27:
Code:
decimal     or         between           and
2.21875     71b-5      875812619b-4      1751625309b-5
2.0078125   257b-7     973065703b-3      15569051505b-7
1.96875     63b-5      5747411187b-7     5747411439b-7
1.9609375   251b-7     13459741569b-7    3364935455b-5
1.921875    123b-6     1148597307b-6     574298715b-5
1.904296875 975b-9     1569390625b-9     98086975b-5
1.880859375 963b-9     585b-4            19683b-9
1.875       15b-3      459355401b-4      459355431b-4
1.875       15b-3      328429733b-2      656859481b-3
1.863212... 244215b-17 1852276489785b-17 115767295875b-13
1.84765625  473b-8     180278711b-3      5768919225b-8
I hope nobody gets too confused about those negative binary exponentials I used here, I just tried to keep the numbers as compact as possible.


If anyone wants to continue the search for [2^27, 2^28], I've attached my Pari program. On my mediocre laptop, it took a little less than six days to search [2^26, 2^27], I expect a fast PC to need about the same time for the larger interval. The program searches in intervals of 2^20, each of them takes about 3+ hours (maybe 1+ hour on a fast PC; the time increases as the numbers get larger), so you'll have to be patient until you see the first output...
Attached Files
File Type: txt gaps_kap_28.txt (1.3 KB, 58 views)

Last fiddled with by mart_r on 2020-04-02 at 19:52
mart_r is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Patterns in primes that are primitive roots / Gaps in full-reptend primes mart_r Prime Gap Searches 14 2020-06-30 12:42
Can someone explain these P-1 Relative Primes variances? petrw1 PrimeNet 12 2020-01-12 23:34
Number of relative primes for P-1 petrw1 Factoring 4 2018-11-07 20:20
unexpected number of relative primes tha Software 14 2015-10-30 01:23
P-1 factoring, relative primes timbit Information & Answers 0 2009-03-13 18:45

All times are UTC. The time now is 11:55.

Fri Nov 27 11:55:36 UTC 2020 up 78 days, 9:06, 4 users, load averages: 1.08, 1.22, 1.24

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.