[seqfan] Short intervals without easy-to-factor numbers

[Charles Greathouse]

I've been thinking about a sequence this morning that would look at
logarithmic intervals that don't have any easily-factored numbers.  A
prime is quite easy to factor, but so is a prime times a small
(polylogarithmic) factor: just trial divide.

My first thought was defining f(n) = n / p, where p is the greatest
prime factor of n, and taking a(n) = g(n) = max_{n <= k < n + log n}
f(k).  But this gives mostly 1s -- not surprising, since 1 - 1/e of
the intervals should contain a prime.

My next thought was taking the high-water marks of g(n), something like

1, 8, 48, 184, 285, 340, 527, 1269, 2622, 3471, 5246, 20819, 30170,
48503, 416318, 780357, 1121475, 1845847, 3177027, 4309595, 10435590,
15875985, 15875986, ...

This is nice because it shows not-too-small intervals with the desired
behavior, but depends pretty heavily on the particulars of the
definition.  Another issue is evident from the last two elements
listed above: a sufficiently large gap in hardness results in
consecutive integers, but conceptually I'm working with the gaps, not
the numbers, and that doesn't seem quite right.

Maybe I should look at the first time f(m) >= prime(n) for all m in
[k, k + log k]?  That also gives duplicate numbers, but in a more
natural way perhaps.

Another possibility would be keeping the 'badness' fixed and varying
the width, though I'm not sure what sort of function appropriately
captures the desired hardness.  Any fixed power of a logarithm is
'easy', but a fixed power of n is 'hard'.  Maybe exp((log n)^0.5) or
the like?

Any thoughts on what the most natural way to define this might be?

Charles Greathouse
Analyst/Programmer
Case Western Reserve University