Elements of a Subset, Pairwise Relatively Prime!

Number Theory Level 5

For every integer $n > 3$ , let $f(n)$ be the minimum positive integer, such that every subset of the set $A =\{ 1,2,3,\ldots,n\}$ , which contains $f(n)$ elements, has three elements $x,y,z$ belonging to $A$ , which are pairwise relatively prime.

Find the value of $f(1250)$ .

Bonus : Generalize for $f(n)$ .

The answer is 834.

1 solution

Satyajit Mohanty
Jul 26, 2015

For the present moment, I'll just mention that the generalized value of $f(n)$ is: $f(n) = \left \lfloor \dfrac{n}{2} \right \rfloor + \left \lfloor \dfrac{n}{3} \right \rfloor - \left \lfloor \dfrac{n}{6} \right \rfloor + 1$

But how? $\quad \quad$

Pi Han Goh - 5 years, 4 months ago

Elements of a Subset, Pairwise Relatively Prime!

The answer is 834.

1 solution

0 pending reports