Calculating minimal m for #962

[davidspencer6174]

Took a look at a sequence associated with #962: given an integer $k>0$, what is the smallest $m$ such that

$m+1,...,m+k$

are all divisible by at least one prime $>k$?

For this problem, a basically brute-force program is efficient enough to get 400 terms.

Here's a look at $log_k(m)$. The little peaks are because often many $k$ in a row have the same $m$. For example, $1697892$ is the $m$ for each $k$ from $129$ to $148$ inclusive.

[teorth]

Interesting. The "trivial bound" is that $\log_k(m) \geq 2-o(1)$, so this is hinting that the truth is only moderately far off from that (contrary to Erdos's expectation), although it's hard to tell without more data.

[teorth]

It looks like this is https://oeis.org/A327909 shifted by one.

Notes on AI tools: Gemini Deepthink reproduced the first 50 values (correctly, as far as I can tell) and noted the OEIS connection. ChatGPT Pro also reproduced the first 50 values (also apparently correctly). On the other hand, regular Gemini hallucinated incorrect values, even after the error was pointed out.

[davidspencer6174]

Ah! Good spot on the existing OEIS sequence. I should remember to check for things like that on any sequences I look at in the future.

I made an improvement to the algorithm and then had Claude translate to a C++ program. It ran up to 999 terms in an hour or so; below is the updated plot.

I'll look into whether it makes sense to submit an extension to the existing OEIS sequence (shifting the program's output by 1, of course).

[teorth]

It might be interesting to do a plot of log_k(m) versus log k. Erdos's bound of $$k \gg \exp(\log^{1/2-o(1)} m)$$ corresponds to a nearly linear upper bound $$\log_k(m) \ll (\log k)^{1+o(1)}$$ I think.

[davidspencer6174]

Interesting! Here's such a plot. After the first couple dozen terms it indeed looks pretty linear (drew a straight line through the rest in Paint).

[teorth]

Interesting! Lends some heuristic support to Erdos's bound being close to sharp (contrary to my initial impression based on the initial data).

[bitRAKE]

A threaded strided tiling sieve to ~4000 terms. Not much time has been spent tuning, but I'm happy with the x16 times speed up with 32 threads.