[N] Contando i primi...

[HiTLeuLeR]

Nella speranza che DB85 possa perdonarmi per avergli negato la possibilità di sollazzarsi con le sommatorie di Boll, tento qui di rimediare al danno reso, proponendovi il seguente:
<BR>
<BR><!-- BBCode Start --><B><font color=green>Problema 1:</font></B><!-- BBCode End --> per ogni x reale > 0, sia pi(x) := |{p \\in N: p è primo & p <= x}|. Se {p_n: n \\in N₀} è la successione ordinatamente crescente di tutti e soli i primi naturali, si dimostri allora che, qualunque sia n intero >= 6:
<BR>
<BR><center>pi((prod_k=1...n p_k)^1/2) > 2n.</center>
<BR>
<BR>EDIT: errata corrige!
<BR>
<BR>
<BR>\"Contiones saepe exclamare vidi, cum apte verba cecidissent.\" - Cicerone <font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 09-10-2004 18:26 ]

[Boll]

Dimostriamo la tesi per induzione su n.
<BR>Il caso di n=6 risulta
<BR>pi(sqrt(2*3*5*7*11*13))>12
<BR>pi(173)>12
<BR>verificato per calcolo diretto essendo 41 il tredicesimo primo.
<BR>
<BR>ora, dimostriamo che, se vale per n, vale anche per n+1
<BR>abbiamo che
<BR>pi(sqrt(p₁p₂p₃...p_n))>2n
<BR>
<BR>quindi la tesi diviene pi((sqrt(p₁p₂p₃...p_n)*sqrt(p_n+1))>2n+2
<BR>
<BR>dobbiamo in pratica dimostrare che, moltiplicando per p_n+1 la produttoria di tutti i primi n primi, si trovano nell\'intervallo fra sqrt(p₁p₂p₃...p_n) e sqrt(p₁p₂p₃...p_n+1) più di due primi, ciò è vero per il postulato di Bertrand, poichè il settimo primo è 17 e sqrt(17)>4, quindi abbiamo almeno un primo fra n e 2n e uno fra 2n e 4n.
<BR>c.v.d.<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 10-10-2004 17:51 ]

[HiTLeuLeR]

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-09 17:10, Boll wrote:
<BR>[...] verificato per calcolo diretto essendo 37 il tredicesimo primo.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Davvero un buon lavoro, Boll! A dispetto della tua pur giovanissima età, devo riconoscere - uffa... - che ti difendi niente male!!! In ogni caso, volevo farti notare che il tredicesimo numero primo è 41, non 37... Sei proprio sicuro di saper contare oltre la decina?
<BR>
<BR>Bene, rilancio subitissimo con un paio di problemi, o presunti tali, di cui il primo - niente poco di meno - porta la firma di mrs Elvira Raraport ( <IMG SRC="images/forum/icons/icon_eek.gif"> ):
<BR>
<BR><!-- BBCode Start --><B><font color=red>Problema 2:</font></B><!-- BBCode End --> mostrare che, se n è un intero > 1 e k il numero dei divisori primi naturali distinti di n, allora: log(n) >= k · log(2).
<BR>
<BR><!-- BBCode Start --><B><font color=blue>Problema 3:</font></B><!-- BBCode End --> provare che, per ogni intero positivo n: n^{pi(2n) - pi(n)} < 4ⁿ.
<BR>
<BR>
<BR>\"Certa gente ha proprio una gran bella faccia tosta.\" - un pensiero ricorrente<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 09-10-2004 18:27 ]

[DB85]

<!-- BBCode Start --><IMG SRC="http://www.thelearningtree.it/esercizio3.gif"><!-- BBCode End -->
<BR>
<BR>Se sostituiamo 2 con la media geometrica dei divisori di k, allora esce qualcosa di più (poco di più) interessante. Questo sempre supponendo di non aver preso qualche cantonata... <BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 09-10-2004 19:14 ]

[HiTLeuLeR]

No, non sei ubriaco, il problema è veramente facile, pensavo fosse chiaro dal testo del messaggio precedente! Solo non capisco perché mai tu abbia dovuto assumere che n sia della forma prod_i=1...k p_i, evitandoti anche soltanto <!-- BBCode Start --><B>una</B><!-- BBCode End --> singola battuta relativa al caso più generale in cui un qualche p_i possa figurare fra i divisori dello stesso n con un esponente intero e_i > 1.
<BR>
<BR>
<BR>\"Domandare è lecito, rispondere è cortesia.\" - saggezza popolare<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 09-10-2004 19:22 ]

[Simo_the_wolf]

Problema 1: ln(n)>k*ln(2) [k=numero di primi che dividono n]
<BR>è equivalente a dire che n>2^k dove k è il numero di primi che dividono n.
<BR>Esprimiamo ora n come n=p₁^a₁p₂^a₂...p_k^a_k [con i>j ==> p_i>p_j]e osserviamo che abbiamo:
<BR>p₁^a₁>=2 xkè p₁>=2 e x ogni i>1:
<BR>p_i^a_i>2
<BR>
<BR>moltiplicando il tutto abbiamo la tesi (ricordiamo che se a>=b e c>d allora ac>bd)
<BR>
<BR>c\'è da precisare che la disuguaglianza stretta vale per ogni intero > 2 perchè solo se n=2 allora si avrebbe l\'uguaglianza
<BR>
<BR>D\'oh! mi hanno battuto sul tiempo... <IMG SRC="images/forum/icons/icon27.gif"> <BR><BR>[ Questo Messaggio è stato Modificato da: Simo_the_wolf il 09-10-2004 19:29 ]

[DB85]

Hai assolutamente ragione HiTLeuLeR, è stata una mia svista nello scrivere di fretta nel programma di elaborazione grafica delle formule. Ora ho sistemato. Comunque il procedimento è lo stesso.

[HiTLeuLeR]

Volevo far notare che nessuno di voi altri ragassuoli, nel postare la propria soluzione al problema n° 2, si è curato minimamente di prendere in esame, quantunque banale, il caso n = 1, cui non sono applicabili le molteplici argomentazioni, da più parti utilizzate, conseguenti all\'applicazione del teorema fondamentale dell\'Aritmetica (ricordo infatti che la forma \"standard\" di quest\'ultimo si applica soltanto agli interi > 1). Ora, non è mia intenzione interpretare il ruolo di chi s\'industria con tutte le sue forze per cercare il cavillo di ogni legge, ma non posso non ricordarvi che, a quanto mi risulta, una \"mancanza\" di questo genere, seppure in assoluto tutt\'altro che imperdonabile, nel contesto di una gara internazionale IMO-<!-- BBCode Start --><I>style</I><!-- BBCode End -->, vi avrebbe soffiato via almeno un punto! Forse mi sbaglierò, ma nel dubbio...
<BR>
<BR>
<BR>\"Similia excogitationem non habent difficilem.\" - Cicerone<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 10-10-2004 13:13 ]