Erastothenovo síto

Úloha číslo: 3470

Kolik čísel zbyde z \(1,…,n\) po vyškrtání násobků 2, 3, 5 a 7?

Vyřešte nejprve obecně a pak určete přesný výsledek pro \(n=999\).

  • Řešení

    Pro \(i\in\{2{,}3,5{,}7\}\) označme \(A_i\) násobky \(i\) v množině \(\{1,…,n\}\) a podobně \(A_I=\bigcap\limits_{i\in I} A_i\) pro \(I\subseteq\{1,…,n\}\). Tedy \(A_2\) jsou sudá čísla, \(A_{\{2{,}5,7\}}\) násobky 70 apod.

    Máme \(|A_I|=\left\lfloor\frac{n}{\prod I}\right\rfloor\). Podle principu inkluze a exkluze zůstane po vyškrtání \(n-\left|\bigcup\limits_{i\in\{2{,}3,5{,}7\}} A_i\right|= n+\sum_\limits{I\subseteq\{2{,}3,5{,}7\},I\ne\emptyset}(-1)^{|I|} |A_I|= n+\sum_\limits{I\subseteq\{2{,}3,5{,}7\},I\ne\emptyset}(-1)^{|I|} \left\lfloor\frac{n}{\prod I}\right\rfloor \).

    Konkrétně pro \(n=999\) máme \(A_2=499\), \(A_3=333\), \(A_5=199\), \(A_7=142\), \(A_{\{2{,}3\}}=166\), \(A_{\{2{,}5\}}=99\), \(A_{\{2{,}7\}}=71\), \(A_{\{3{,}5\}}=66\), \(A_{\{3{,}7\}}=47\), \(A_{\{5{,}7\}}=28\), \(A_{\{2{,}3,5\}}=33\), \(A_{\{2{,}3,7\}}=23\), \(A_{\{2{,}5,7\}}=14\), \(A_{\{3{,}5,7\}}=9\) a \(A_{\{2{,}3,5{,}7\}}=4\).

    Zbývá dopočítat \(999-499-333-199-142+166+99+71+66+47+28-33-23-14-9+4=228\).

  • Odpověď

    Po vyškrtání zůstane 228 čísel.

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na trénování výpočtu
En translation
	Zaslat komentář k úloze