Gaps in k-almost primes relative to 2^k, a question

[mart_r]

Consider gaps in k-almost primes (i.e. (n)=k), relative to the size of the smallest such number, 2^k.
Let k, we have the sequence

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 2^k, are eventually the record gaps between k-almost primes for almost all k):

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]

Update: A gap greater than 2 is possible!

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.

1.9609375  105154231.0078125

Also, here's a list of successive minima. I used fractions in the left column, for reasons.

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

[Bobby Jacobs]

Interesting. I wonder why the gap of 1.880859375 from 36.5625 to 38.443359375 stays as a record for so long.

[mart_r]

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:

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