Minimum Cardinality Set

Number Theory Level 4

Given the set $A(N)=\{1,2,\dots,N\}$ , when $N \in \mathbb{N}$ , $f(A(N))$ is a function that takes set $A(N)$ and find all the primes (ignoring the multiplicity) that are found in the factorisation of members of $A(N)$ . Mathematically

$f(A(N))=\{p \ prime|\exists x \in A(N): p|x\}$

If $S\subset A(N)$ , what is the least cardinality that $S$ can achieve, when $f(S)=f(A(N))$ ?

So, this is a general question, for which any answer is appreciated. However, one may approximate the the solution for case $N=10^4$ . Find the cardinality of a set $S \subset A(10^4)$ such that $f(A(10^4))=f(S)$ and $S$ has the minimum cardinality. Which one of the options is the closest to the solution?

200 1000 500 2050

1 solution

Henry U
Nov 19, 2018

By the prime number theorem , there are about $\frac N {\ln N}$ primes less than $N$ . Picking $S$ as the set that contains all of these prime numbers will make $f(S)$ simply $|S|$ (its cardinality) while $f(A(N))$ will also be $f(S) = |S|$ since every composite $n$ number in $A(N)$ won't be counted. This is because all prime factors of $n$ have already been counted in their pure form as a prime.

So, knowing $|S| \approx \frac N {\ln N}$ , we can plug $N=10^4$ in and get $|S| \approx \frac {10000}{\ln 10000} \approx 1085.7 \approx \boxed{1000}$ .

although you have chosen the right answer, you can have a much better approximation. There would be some composite numbers that contain more than one prime number and taking such composite numbers would reduce the cardinality of the set. a better approximation would be pi(N)-pi((N)^0.5), where pi(N) is the number of primes less than or equal to N.

A Former Brilliant Member - 2 years, 6 months ago

Ahh, that's very clever!

Henry U - 2 years, 6 months ago

Minimum Cardinality Set

1 solution

0 pending reports