OFFSET
1,9
COMMENTS
Grimm's conjecture states that for k consecutive composite numbers there are k distinct prime numbers such that each prime divides one of the composite numbers. As pointed out by Grimm, for a composite number c having a prime factor p>=k, we associate p with c. Hence there are only a(n) numbers remaining between prime(n) and prime(n+1) for which we need to associate a distinct prime. Puzzle 430 gives a heuristic algorithm for finding those a(n) primes. According to Puzzle 430, the largest known value of a(n) is 10, which occurs between the primes 31397 and 31469.
LINKS
T. D. Noe, Table of n, a(n) for n=1..10000
C. A. Grimm, A conjecture on consecutive composite numbers, Amer. Math. Monthly, 76 (1969), 1126-1128.
Carlos Rivera, Puzzle 430: Grimm's Conjecture
EXAMPLE
a(4)=1 because of the 3 numbers between 7 and 11 (8=2^3, 9=3^2, 10=2*5), only 8 has all of its prime factors less than 3. Similarly, a(9)=2 because of the 5 numbers between 23 and 29, only 24 and 27 have all prime factors less than 5.
MATHEMATICA
Table[p1=Prime[i]; p2=Prime[i+1]; cnt=0; k=p2-p1-1; Do[If[FactorInteger[n][[ -1, 1]]<k, cnt++ ], {n, p1+1, p2-1}]; cnt, {i, 150}]
PROG
(PARI) a(n) = my(p = prime(n), q = nextprime(p+1)); sum(c=p+1, q-1, vecmax(factor(c)[, 1]) < q-p-1); \\ Michel Marcus, Sep 30 2017
CROSSREFS
KEYWORD
nonn
AUTHOR
T. D. Noe, Feb 04 2008
STATUS
approved