|
| |
|
|
A307211
|
|
a(n) = the "maximum first open number" for prime(n).
|
|
0
|
|
|
|
2, 6, 12, 24, 42, 75, 90, 150, 180, 216, 312, 339, 447, 519, 615, 660, 783
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
This sequence is related to Goldbach's Conjecture.
Definition. Let P = prime(n). Choose one remainder and its negative for each prime up to and including P. Sieve the numbers 1, 2, 3, 4, ... to remove numbers congruent to either chosen remainder modulo the respective prime. Call the numbers left "open", and the smallest open number the "first open number" for that P and that choice of remainders. The maximum first open number for P is the largest first open number for any such choice of remainders.
Equivalently, let P = prime(n). Any positive integer c has a set of remainders modulo each prime up to and including P. Call a positive integer d "open" for c and P, if d has no remainder which is the same as, or is the negative of, any remainder of c modulo any prime up to and including P. There is a smallest, or first, open number d for any c. The maximum first open number for P is the largest first open number d for any positive integer c. (Only numbers c from 1 to P#, the product of the primes up to and including P, have to be considered.)
A problem is to find an upper limit for a(n) in terms of prime(n).
The ratios a(n)/prime(n), n = 1 to 14, are 1, 2, 2.4, 3.4, 3.8, 5.8, 5.3, 7.9, 7.8, 7.4, 10.1, 9.2, 10.9, 12.1, so a(n) appears to grow faster than prime(n).
The ratios log(a(n))/log(prime(n)), n = 1 to 14, are 1, 1.63, 1.54, 1.63, 1.56, 1.68, 1.59, 1.70, 1.66, 1.60, 1.67, 1.61, 1.64, 1.66, which appear to be bounded.
Conjecture 1: a(n) <= prime(n)^1.75.
Conjecture 2: a(n) <= prime(n) * (prime(n) - 1) / 2, n >= 5.
More terms are needed to check whether these conjectures are true for larger n.
Either conjecture implies that Goldbach's conjecture is true. (Stated as every even number greater than 6 is the sum of two different primes where 1 is not prime.)
Consider the sum (c - d) + (c + d) = 2c, where d is open for c and prime P, the smallest prime such that the primes up to and including P are sufficient to test whether two numbers that add to 2c are prime. If d were small enough, c - d is positive and both c - d and c + d would be prime, because c and d and also -c and d have no common remainders modulo every prime up to and including P.
Either conjecture would assure the existence of an open number d which is small enough, for every sufficiently large c.
For example, for P large enough, P^1.75 <= (P^2 - 3)/2. For a particular c, choose P so it is the largest prime with P <= sqrt(2c - 3). Rearranged, this gives (P^2 - 3)/2 <= c - 3. Thus d <= P^1.75 <= (P^2 - 3)/2 <= c - 3, so that c - d >= 3 is positive. Therefore Goldbach's Conjecture follows from Conjecture 1.
I think that conjectures 1 and 2 would imply that, for every gap 2n, there are an infinite number of prime pairs with that gap. I think they would also give an upper bound for the gap between pairs of primes with gap 2n.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(n) = max for all {r(1), ..., r(n)} min d = d({r}) where d >= 1, d !== r(i) (mod prime(i)), d !== -r(i) (mod prime(i)), i = 1, ..., n.
a(n) = max for all c >= 1, min d = d(c) where d >= 1, d !== c (mod p) and d !== -c (mod p) for all p, p prime, p <= prime(n).
|
|
|
EXAMPLE
|
Let n = 4, so P = 7.
Choose, for example, remainders 1 (mod 2), 0 (mod 3), +-1 (mod 5), +-2 (mod 7).
Remove odd numbers and numbers divisible by 3 from 1, 2, 3,..., 49 (which should be enough numbers to sieve according to the conjectures) leaving 2, 4, 8, 10, 14, 16, 20, 22, 26, 28, 32, 34, 38, 40, 44, 46.
Then remove numbers congruent to +-1 (mod 5), which leaves 2, 8, 10, 20, 22, 28, 32, 38, 40.
Finally remove numbers congruent to +-2 (mod 7), which leaves the "open" numbers 8, 10, 20, 22, 28, 32, 38, 46. The "first open number" is 8.
There are 2 * 2 * 3 * 4 = 48 ways of choosing remainders for P = 7 (0 or 1 for 2, 0 or +-1 for 3, 0, +-1 or +-2 for 5, 0, +-1, +-2 or +-3 for 7).
The maximum first open number for 7 is 24, for remainders 1 (mod 2), +-1 (mod 3), +-2 (mod 5) and +-1 (mod 7).
For another example, let n = 3, so P = 5. For numbers c, one need only consider the numbers 1 to 30 to account for all possible combinations of remainders mod 2, 3, and 5. The first open numbers for each of these numbers, for P = 5, are 12, 9, 4, 3, 6, 5, 6, 9, 2, 3, 12, 1, 6, 3, 2, 3, 6, 1, 12, 3, 2, 9, 6, 5, 6, 3, 4, 9, 12, 1 respectively. Therefore, for n = 3, the "maximum first open number" a(3) is 12.
|
|
|
PROG
|
(Outline)
a(n)=1
P=prime(n)
For each permutation m(n) of 1 to n
i()={1, 2, 3, ..., P^2}
for j=1, n
r=i(1) mod p=prime(m(j))
eliminate numbers congruent to r or -r mod p from i()
next j
if i(1) > a(n)
a(n)=i(1)
next permutation
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
