Hamilton 2020 Q4

First, note that \(31^2 = 961\) and \(37^2 = 1369\), so the largest prime less than \(\sqrt{1000}\) is 31.

So any non-prime number less than 1000 (excepting 1) must have at least one prime factor which is less than or equal to 31 (otherwise the number would be at least \(37^2\), which is larger than 1000).

We are told that all pairs of Piercarlo’s share no factors greater than one; this clearly must include prime factors, and in particular the primes from 2 to 31 inclusive. Hence each of the primes up to 31 can only appear in the factorisation of one of his numbers.

So to maximise \(n\), he will need to choose numbers with as few of these prime factors in their prime factorisation as possible. Indeed, he should aim to choose a set of numbers where each number he chooses has no more than one prime factor less than or equal to 31. Since there are 11 of these primes, the maximum value of \(n\) is 12 (since he can also pick 1).

It is easy to check that he can indeed pick 12 non-prime numbers less than 1000 – for example by picking 1 together with the squares of all the primes up to 31: