7 primes in intervals [k*30,(k+1)*30]
Hugo Pfoertner
wrote a program to test primality using a stored bitmap of the 8
possible prime candidates in the intervals [k*30,(k+1)*30], k>=1. For my
purpose of checking small numbers <2^31 the program is sufficiently
fast. The overhead to read the 70MByte table is negligible - 2 seconds
on my 4 years old 800MHz Athlon.
For those interested in the program, see links in
http://www.research.att.com/projects/OEIS?Anum=A098591
The intervals [k*30,(k+1)*30], k>=1 can contain up to 7 primes, the
first containing 7 primes occur for
k=
1 2 49 62 79 89 188 6627 9491 18674 22621 31982 34083 38226 38520
41545 48713 53887 89459 103205 114731 123306 139742 140609 149125
168237 175125 210554 223949 229269 237794 240007 267356 288467 321451
364921 368248 373370 391701 404002 471078 471745 480859 505017 524027
606681 616812 619039 630862 634892
In the range I checked only 6 of the 8 possible ways to arrange the 7
primes at the candidate locations 30*k+{1,7,11,13,17,19,23,29} occur:
Composite First occurrence
at offset for k =
7 49
11 89
13 22621
17 2
19 1
23 62
The observation I found interesting, was
that an interval [k*30,(k+1)*30] can only contain 7 primes if both
30*k+1 and 30*k+29 are prime.
Is there an easy way to prove this?
Hugo Pfoertner
Mensanator
>From: Hugo Pfoertner not...@abouthugo.de
>Date: 9/18/2004 2:40 PM Central Standard Time
>Message-id: <414C8F2B...@abouthugo.de>
For your 8 candidate locations to have 7 primes and a composite end (1 or 29),
the 6 interior candidates must all be prime. Looking at the candidates mod 7
shows there is only one case where all 6 are not divisible by 7:
3 2 6 1 5 0 4 3
5 4 1 3 0 2 6 5
0 6 3 5 2 4 1 0 <---
2 1 5 0 4 6 3 2
4 3 0 2 6 1 5 4
6 5 2 4 1 3 0 6
1 0 4 6 3 5 2 1
But in that case, BOTH candidate locations 1 and 29 are divisible by 7.
So the only way to have 7 out of 8 is to have a composite in the interior.
>
>Hugo Pfoertner
--
Mensanator
Ace of Clubs
Phil Carmody
7 must divide at least one of the terms. That's why (apart from the
excluded k=0 range) only <=7 of the 8 terms can be prime.
If 7 divides 30*k+1, it also divides 30*k+1+4*7.
Phil
--
They no longer do my traditional winks tournament lunch - liver and bacon.
It's just what you need during a winks tournament lunchtime to replace lost
... liver. -- Anthony Horton, 2004/08/27 at the Cambridge 'Long Vac.'
Edwin Clark
> The intervals [k*30,(k+1)*30], k>=1 can contain up to 7 primes,
Could there be a k for which the interval contains 8 primes?
>
> The observation I found interesting, was
> that an interval [k*30,(k+1)*30] can only contain 7 primes if both
> 30*k+1 and 30*k+29 are prime.
>
> Is there an easy way to prove this?
Or, perhaps it is not true?
--Edwin
Phil Carmody
> Hugo Pfoertner wrote:
>
>
> > The intervals [k*30,(k+1)*30], k>=1 can contain up to 7 primes,
>
> Could there be a k for which the interval contains 8 primes?
Look at the residues mod 7.
The only way a natural number that is divisible by seven can be
prime is if that number is 7.
Therefore your only success could be at k=0, but there you've
got the issue of 1 not being prime to modern mathematicians.
Hugo Pfoertner
Mensanator and Phil, many thanks for showing me this simple explanation.
In the meantime I've created a table of the counts how often one of the
256 patterns (actually only 253, as pointed out above) occurs in the
range 30 .. 2^31 (omitting the last interval containing 2^31-1). I hope
I didn't make mistakes, but at a first glance it looks plausible. People
speculating about prime patterns may find it useful.
http://www.randomwalk.de/scimath/primes30.pdf
Hugo