MathDB

Let us consider a set

S = \{ a_1 < a_2 < \ldots < a_{2004}\}

, satisfying the following properties:

f(a_i) < 2003

and f(a_i) = f(a_j) \forall i, j from

\{1, 2,\ldots , 2004\}

, where

f(a_i)

denotes number of elements which are relatively prime with

a_i

. Find the least positive integer

k

for which in every

k

-subset of

S

, having the above mentioned properties there are two distinct elements with greatest common divisor greater than 1.

Problem Statement