Problem 4

A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let

P(n)=n^2+n+1

. What is the smallest possible value of a positive integer

b

such that there exists a non-negative integer

a

for which the set

\{P(a+1),P(a+2),\dots,P(a+b)\}

is fragrant?

Step 2 of 5: A graph with too few possible edges

Previous step Next step

In plain words

Model the potential shared factors among $b$ consecutive values as a graph; the previous step says only three specific "gap" edges are even possible, and only one of each.

b\le5\ \Rightarrow\ \text{at most one edge of gap }2,\,3,\,4,\text{ and none of gap }1

Detailed analysis

For a gap $2$ , divisibility by $7$ requires the two indices to be the two roots $2,4\pmod7$ ; within five consecutive indices there is at most one such pair. For a gap $3$ , divisibility by $3$ requires both indices to be $1\pmod3$ , again giving at most one pair in a run of five. For a gap $4$ , divisibility by $19$ requires the roots $7,11\pmod{19}$ , also at most one pair. Gap $1$ is impossible because the gcd is $1$ . Thus among five consecutive indices there are at most three possible shared-factor edges, one of each gap, so they cannot cover all five vertices.