mersenneforum.org Gaps in k-almost primes relative to 2^k, a question
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2020-02-23, 16:57 #1 mart_r     Dec 2008 you know...around... 2·32·31 Posts 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?
 2020-03-29, 20:48 #2 mart_r     Dec 2008 you know...around... 2·32·31 Posts 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...
 2020-04-01, 22:50 #3 Bobby Jacobs     May 2018 22×47 Posts Interesting. I wonder why the gap of 1.880859375 from 36.5625 to 38.443359375 stays as a record for so long.
2020-04-02, 19:36   #4
mart_r

Dec 2008
you know...around...

2×32×31 Posts

Quote:
 Originally Posted by Bobby Jacobs 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
 gaps_kap_28.txt (1.3 KB, 23 views)

Last fiddled with by mart_r on 2020-04-02 at 19:52

 Similar Threads Thread Thread Starter Forum Replies Last Post mart_r Prime Gap Searches 14 2020-06-30 12:42 petrw1 PrimeNet 12 2020-01-12 23:34 petrw1 Factoring 4 2018-11-07 20:20 tha Software 14 2015-10-30 01:23 timbit Information & Answers 0 2009-03-13 18:45

All times are UTC. The time now is 19:44.

Thu Aug 6 19:44:05 UTC 2020 up 20 days, 15:30, 3 users, load averages: 1.39, 1.67, 1.70