pi(n) < n/3 + 2

[Haile]

Si dimostri che

$ $\pi (n) < \frac{n}{3} + 2, ~ \forall n \in \mathbb{N}$ $

Dove $ $\pi(n)$ $ è la nota Funzione Enumerativa dei Primi

[Sonner]

Cavolata

[jordan]

[...]$ $n > 3(n - 3) $, quindi $ $n >9/2 $[...]

[...]


Edit@Sonner:non devi cancellare i post, anche se contengono dimostrazioni sbagliate. Può essere utile a altri per iniziare a vedere cosa già cosa fare o meno..a prescindere dal problema. Inoltre lo dico a te, ma vale anche per Rosinaldo e molti altri qui del forum, la funzione "quote" serve solo ed esclusivamente ad aiutare a fare chiarezza e riprendere il filo del discorso su precise parti dei post precedenti. Detto questo, quotare interi post altrui per scrivere una riga di commento, o, ancora peggio quando c'è una sola altra risposta, è completamente inutile.

[Sonner]

[...]$ $n > 3(n - 3) $, quindi $ $n >9/2 $[...]

[...]

già ho perso un giro di disuguaglianza... mi nascondo in silenzio

[Thebear]

Per il principio di Inclusione-Esclusione abbiamo che il numero dei multipli di 2 o di 3 è $ \frac{1}{2} \cdot n + \frac{1}{3} \cdot n - \frac{1}{6} \cdot n= \frac{2}{3} \cdot n $ quindi almeno $ \frac{2}{3} n -2 $ numeri minori o uguali a n non sono primi (ho detto "meno 2" perchè 2 e 3 invece lo sono). Allora $ \pi(n) $ varrà al più $ \frac{1}{3} \cdot n+2 $. La disuguaglianza è stretta per tutti gli n maggiori o uguali a 14. Infatti se n<14 si ha $ \pi(n)= \frac{n}{3} +2 $. Giusto?

EDIT: tutte le frazioni di n sono intese come parti intere del quoziente, ossia il più grande intero minore di n. (come si scrive quella notazione in TeX??? )

EDIT2: alla prima riga intendevo il numero dei multipli di 2 o di 3 minori o uguali di n

EDIT3: mi rimangio la parte sulla disuguaglianza stretta: avevo malinterpretato $ \frac{n}{3} $ nell'ipotesi. Supponendo che si possa anche andare nei decimali la disuguaglianza è stretta sempre

[pak-man]

EDIT: tutte le frazioni di n sono intese come parti intere del quoziente, ossia il più grande intero minore di n. (come si scrive quella notazione in TeX??? )

$ \left\lfloor x\right\rfloor $

[Thebear]

$ \left\lfloor x\right\rfloor $

Thanks! Comunque la soluzione è corretta, no?

[Haile]

Quando parli della funzione floor, mi pare che tu dia per scontato che

$ $\lfloor a\rfloor + \lfloor b\rfloor - \lfloor c \rfloor = \lfloor a+b - c\rfloor $ $

Cosa che non è sempre vera (basta provare a = 1.6, b = 1.7, c=1.1)

(Comunque non è difficile rimediare)

[jordan]

Addirittura anche questo lasciato a morire. Allora, se un primo è maggiore di 3 allora è della forma 6k+1 o 6k-1 per qualche k in N, da cui la tesi.

E comunque esiste questo

[Haile]

E comunque esiste questo

Esiste anche questo, eppure la TdN olimpica non è ancora stata dichiarata morta...

[jordan]

E che avrebbe a che fare con questo problema?

[EvaristeG]

smettetela... siete quasi fastidiosi.
Ovviamente Haile vuol dire che ci sono risultati molto potenti in teoria dei numeri che però, non essendo elementari, di solito non vengono usati (e spesso nemmeno considerati) nel risolvere problemi olimpici.
D'altra parte, il teorema dei numeri primi, nella sua forma più semplice, dice solo che, prima o poi, il numero di numeri primi si comporta (più o meno) come una certa funzione. Qui si chiede una stima per ogni n naturale, non da un certo punto in poi.