gaps between square-free numbers (multiple berths)

[Hans Havermann]

> there's an old sequence of David Wilson's that needs a few more
> terms - any volunteers?

> %S A020753 1,2,3,4,5,6,7,8,9,10,12
> %N A020753 Sizes of successive increasing gaps between square-free numbers.

> %S A020754 1,3,7,47,241,843,22019,217069,1092746,8870023,221167421
> %N A020754 Increasing gaps between square-free numbers (lower end).

> %S A020755 2,5,10,51,246,849,22026,217077,1092755,8870033,221167433
> %N A020755 Increasing gaps between square-free numbers (upper end).

and, to clarify:

> %S A005117  1,2,3,5,6,7,10,11,13,14,15,17,19,21,22,23,26,29,30,31,33,...

> ...

> The zeroth gap occurs between 1 and 2 and has length 0.
> The first gap occurs between 3 and 5 and has
> length 1. The next gap is between 7 and 10 and has length 2. Etc.
> We are only interested in gaps that set new records.


To help others visualize what is happening here, let me use the designation
SFF to indicate positive integers for which the Mathematica extended
function *SquareFreeQ* yields False.

Table[SquareFreeQ[i], {i, 2, 100}]

{True, True, False, True, True, True, False, False, True, True, False, True,
True, True, False, True, False, True, False, True, True, True, False, False,
True, False, False, True, True, True, False, True, True, True, False, True,
True, True, False, True, True, True, False, False, True, True, False, False,
False, True, False, True, False, True, False, True, True, True, False, True,
True, False, False, True, True, True, False, True, True, True, False, True,
True, False, False, True, True, True, False, False, True, True, False, True,
True, True, False, True, False, True, False, True, True, True, False, True,
False, False, False}

By the way, SquareFreeQ[0] == False and SquareFreeQ[1] == True. Go figure.
We're looking for *consecutive* False's in this list, specifically the first
occurrences of a single False (3), two consecutive False's (7), three
consecutive False's (47), and so on. With the exception of the first term
(SFF0), this *might* well be A020754. It is *not* because, in the interest
of record-breaking, SFF10 has been omitted.


I first dealt with the concept of *multiple berths* (consecutive numbers
with a given property) in the early eighties with the idea of 'modest'
numbers (A054986). There is a listing of modest 'twins' at A055018. A
sequence of smallest modest number by berth-size (if ever submitted) would
eventually run into the problem of a larger berth-size appearing before a
smaller one.

I was re-aquainted with the dilemma when I worked on extending Mike Keith's
A045760 recently. Mike had already determined that a 7-tuple appeared before
a *pure* 6-tuple. Likewise, I found that a 9-tuple appears prior to a *pure*
8-tuple. There is a temptation here to either *repeat* a sequence entry
(after all, a 9-tuple is just two consecutive 8-tuples) or perhaps to *omit*
the smaller berth entirely (i.e., record-breaking entries only).

The latter is of course what has happened with A020754. I argue that this is
*not* desirable for the simple reason that it is inelegant. If we insert
SFF10 (if and when it is discovered) back into the sequence, both A020755
and A020753 become superfluous. If A020754 = {1, 3, 7, 47, 241, 843, 22019,
217069, 1092746, 8870023, SFF10, 221167421} then A020755 = a(n)[A020754] + n
and (almost trivially) A020753 = n, where a(n)[A020754] < a(n+1)[A020754].
The reason that 11 does not appear in A020753 is because, presumably, SFF10
> 221167421.

By the way, I've attempted a Mathematica search for SFF 10-tuples but I'm
only advancing about 12 million numbers per day, so (from scratch) I
wouldn't even re-discover SFF11 for three weeks!