1) is equivalent to asking if it is true that property $J(n)$,
which is the assertion $j(P_N/P_n) \leq P_n$, holds
for all integers $n$, where $P_n$ is the product of the first $n$
primes, $P_N$ is the product of the first $N$ primes where $N$ is
the largest index such that $p_N < P_n$, and $j()$ is Jacobsthal's
function $j(m)$ which gives the smallest integer $j$ such that any
interval of $j$ or more consecutive integers contains at least one
integer which is coprime to $m$. The original formulation involving
covering an interval with residue classes, one for each prime $p_i$
with $n < i \leq N$, can be translated by the Chinese Remainder Theorem
into one where the residues are 0, i.e. the classes are multiples of
the prime instead of being an arithemtic sequence with common difference
p_i. Aaron Meyerowitz showed that $J(n)$ was true for $n=3$ and claimed
it was for $n=4$,
Will Jagy observed that $J(n)$ was true and easy for $n=2$, and I showed
that $j(P_N/P_n) = 9$ for $n = 3$
by a method similar to one outlined by Aaron
in one comment, and that $74 < j(P_N/P_n)<=85$ for $n=4$
by an undisclosed but elementary method. I also
suggested that $J(n)$ is false for all $n > 4$.
A method of showing for $n < 5$ that $j(P_N/P_n) < P_n$ comes
from the fact that $\sum_{n < i \leq N} 1/p_i < 1$, and some
simple estimates on $j(m)$ which are applicable to any $m$ such
that the sum of the inverses of $m$'s distinct prime factors
add up to less than 1. This method is no longer applicable
for $n \geq 5$, as the indicated sum grows roughly as
$\log(\log(p_N)/\log(p_n))$, but it does grow, suggesting that
$J(n)$ is eventually false for sufficiently large $n$.
I had hoped to show upper or lower bounds to resolve the matter,
but the upper bounds I have at my disposal, while explicit, are
too weak to show $J(n)$ is true, and the best asymptotic bounds
are also too weak, even making favorable assumptions on the
(as yet unknown) multiplicative constants, while the best known
lower bounds in the literature can probably be used to show
$j(P_N/P_n) > c P_N$ for $c$ some constant less than 1, so the
lower bounds are tantalizingly close to showing that $J(n)$ is false,
that is that the interval $[0, P_N -1]$ can be covered by $N-n$-many
residue classes, one for each prime $p_i$.
If one were to tweak things slightly, say allowing a couple smaller
primes less than $p_n$ to help cover, or allowing not very many
primes larger than $p_N$ to help (probably less than $n^6$ primes),
then the
answer to the modified question $J'(n)$ would be no, there would
always be enough primes to cover.
One cover which shows how near a miss this is uses a midpoint sieve.
Choose $L$ odd less than $P_n$ and forget even numbers for a while,
and pretend you are covering the odd numbers in $[-L,L]$ with the
classes centered about the missing point 0. For $n=4$ I used $L =73$
and covered both endpoints with the class belonging to 73, the next
with the class belonging to 71, the next with the class belonging
to 23 ( = 69/3) all the way down to 11, then I filled in the holes
(odd numbers less than 74 which were 7-smooth) with 26 primes.
For $n=5$ one can use a midpoint sieve to cover something like 1700
number with the primes from 13 to 2309, and for $n=6$ something like
25000 for the primes from 17 up to 30030. (I have yet to double
check the figures, so I am being purposely vague.) In particular,
it seems that the coverage ratio for the set using the midpoint
sieve is increasing, and this suggests one can do better by
tweaking the midpoint sieve to show $J(n)$ true. Such tweaking
is either random, so hit-or-miss, or computationally expensive,
and I have no good heuristics at present for making substantial
improvements on the midpoint sieve. The fact that the midpoint
sieve does far better than 50% coverage for $n>4$ is one of my
reasons for believing $J(n)$ is false.
I am trying to develop a technique to refine upper bounds, especially
in the cases that the sum of the reciprocals of the distinct prime
divisors is larger than 1 but still close to one. It is related to
the following problem, which perhaps someone here can shed light
upon. For $M$ small, I was able to use a relative of this problem
to show $j(P_{46}/P_4) < 83$.
I want to see how poorly I can cover small portions of the number
line according to the following constraints: 1) I only need to
cover some subset around 0 of the number line $[-M, M]$, so
I can set my boundaries for computation to numbers not exceeding
$2M$; 2) I have 0 already covered by something other than a tile,
so no need to worry about that;
3) I have $k$ tiles of distinct lengths, the lengths ranging from
2 to $l$ where $l$ is larger than $k$ but not by much, and $l < 2M$;
4) each tile has to cover exactly one positive integer $p$ and
exactly one negative integer $n$, and only a tile of length
$p - n$ can cover both $p$ and $n$; and 5) I want to
minimize simultaneously the amount of overlap and maximize the number of tiles I
use. For an example cost function this could be maximizing $j - o$,
where $j$ is the number of tiles I use and $o$ represents overlap;
$o$ itself could be $(2j-u)$ where $u$ is the number of integers in
$[-M,M]$ that are covered by at least one tile in the arrangement
of $j$ tiles.
In this problem, if I could prove that if I used $j$ tiles all of
distinct lengths less than $3j/2$, that the overlap would be (say)
at least $j/4$, I could use that in improving upper bounds on $j(m)$
(different from but related to $j$) for
some useful class of numbers $m$. Part of the challenge is that I
can use all odd
or all even tiles to create a partial cover with no overlap, and
there are some mixes of odd and even length tiles I could use with
no overlap, so using less than $k/2$ tiles is useless to me unless
most of their lengths are sufficiently small.
To summarize: the tile problem might help in showing that $J(n)$
is true for more $n$. My guess is still that $J(n)$ is false for
$n > 4$.
So much for my latest attempt at 1). For 2), I am guided by
the following scenario: let us suppose
I am right and that for $n=6$, say, one needs only the primes from
$p_7$ to $p_{N-8}$ to use in a cover. Based on my studies of
near-prime gaps, I
expect (but cannot prove) that there would be 2 gaps of size
larger than $P_n$ in the sequence of integers relatively prime
to all the primes from $p_7$ to $p_{N-8}$ inclusive. Suppose
these gaps were each of size $P_n +d$; that would give $2d+2$ ways
(including reflections) of covering the interval $[0, P_n-1]$
with residue classes using the primes from $p_7$ to $p_{N-8}$.
Now multiplying the whole set by $r=p_{N-7}$, this gives at
least $r(2d+2)$ ways to cover the interval by residue classes
which now allow the use of the prime p_{N-7}, plus at least
$2r$ more ways, since each of the 2 gaps before corresponds
to r different gaps in the sequence of number relatively prime
to all the primes from $p_7$ to $p_{N-7}$ inclusive, and each
of the new gaps would be larger by some amount d', whose average
is most likely related to the average gap size in the sequence
($M/\phi(M)$, where $M$ is a product of the primes involved).
Continuing up this way, we get at least $(2d+4)R$, where $R$
is the product of the last 8 primes before and including $p_N$.
This scenario ignores distribution of gaps in general, and
assumes the largest gap is rare and (for sufficiently large N)
the next largest is much smaller and far removed from the
largest, which is what is commonly seen. So I would expect
(but cannot yet prove) that a good upper bound on the number of
ways to cover would be something like $\prod_{0 \leq d < s} p_{N-d}$
where $s$ is small, conjecturally $s \in O(\log(\log(\log(N))))$.
Gerhard "Will Guess For Bounty Points" Paseman, 2011.03.16
