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 5 of 5: Every vertex is covered, so

b=6

works and is optimal

Previous step Next step

In plain words

The three pairs from CRT exactly partition the six indices into three matched pairs, so every one of the six values has a partner sharing a prime factor.

b=6\ \text{is the smallest value for which a fragrant set }\{P(a{+}1),\dots,P(a{+}b)\}\text{ exists}

Detailed analysis

With $a$ chosen as in the previous step, the three pairs $\{a+1,a+5\}$ (sharing factor $19$ ), $\{a+2,a+4\}$ (sharing factor $7$ ), and $\{a+3,a+6\}$ (sharing factor $3$ ) partition all six indices $a+1,\dots,a+6$ into matched pairs, so every element of $\{P(a+1),\dots,P(a+6)\}$ shares a prime factor with at least one other element: the set is fragrant. Combined with Step 3's proof that $b\le5$ is impossible, the smallest possible value of $b$ is $6$ .