interi e potenze di primi

[luca95]

Trovare n interi consecutivi tali che nessuno di essi sia la potenza di un primo

[mr96]

Non ho capito, intendi "trovare il massimo n per cui esistono n interi consecutivi tali che nessuno di essi sia una potenza di un primo"?

[luca95]

il testo dice "find n consecutive positive integers, none of which is a power of a prime" cioè esattamente quello che ho scritto, è tratto da una raccolta di problemi per la preparazione dei canadesi alle imo

[Drago96]

Penso sia una cosa del tipo: dimostrare che per ogni $n$ intero esistono $n$ interi consecutivi non potenze di primi, e mostrarli esplicitamente (e boh, non so se si possa fare senza farli vedere)

[mr96]

Penso sia una cosa del tipo: dimostrare che per ogni $n$ intero esistono $n$ interi consecutivi non potenze di primi, e mostrarli esplicitamente (e boh, non so se si possa fare senza farli vedere)

Sisi, ci ho pensato anch'io dopo... Beh, dovrebbero andar bene

Testo nascosto:

$ (n+1)!^2+k $ con $ k=2,3,..,n+1 $

Edit:

Testo nascosto:

Anche $ (n+1)!+k $ con $ k=2,3,..,n+1 $ direi, visto che $ (n+1)!+k=k(\frac{(n+1)!}{k}+1) $ e la frazione è sempre intera poichè $ 2\leq k \leq n+1 $

[Delfad0r]

Edit:

Testo nascosto:

Anche $ (n+1)!+k $ con $ k=2,3,..,n+1 $ direi, visto che $ (n+1)!+k=k(\frac{(n+1)!}{k}+1) $ e la frazione è sempre intera poichè $ 2\leq k \leq n+1 $

Umh, questo pare non essere vero ($n=2$ ci da $3!+2,3!+3$, ovvero $8,9$ che, guarda un po', sono entrambe potenze di primi)

[mr96]

Edit:

Testo nascosto:

Anche $ (n+1)!+k $ con $ k=2,3,..,n+1 $ direi, visto che $ (n+1)!+k=k(\frac{(n+1)!}{k}+1) $ e la frazione è sempre intera poichè $ 2\leq k \leq n+1 $

Umh, questo pare non essere vero ($n=2$ ci da $3!+2,3!+3$, ovvero $8,9$ che, guarda un po', sono entrambe potenze di primi)

Vero! Dopo dovrebbe andare però, o, al limite, il primo non dovrebbe avere "intoppi"

Edit:
Facciamola un po' più formale va.
$ (n+1)!^2+k $ con $ k=2,3,..,n+1 $ funziona visto che $ (n+1)^2!+k=k((n+1)!\frac{(n+1)!}{k}+1) $ e la frazione è sempre intera poichè $ 2\leq k \leq n+1 $.

Dobbiamo sistemare i casi in cui la roba in parentesi è una potenza di $ k $, ed è per questo che non funziona il secondo metodo, ma in questo caso non esistono, perchè $ \frac{(n+1)!^2}{k} $ contiene ancora almeno un fattore $ k $ e di conseguenza $ \frac{(n+1)!^2}{k}+1 \equiv 1 \pmod{k} $, quindi non può essere potenza di $ k $. Ora funge?

[Delfad0r]

Facciamola un po' più formale va.
$ (n+1)!^2+k $ con $ k=2,3,..,n+1 $ funziona visto che $ (n+1)^2!+k=k((n+1)!\frac{(n+1)!}{k}+1) $ e la frazione è sempre intera poichè $ 2\leq k \leq n+1 $.

Dobbiamo sistemare i casi in cui la roba in parentesi è una potenza di $ k $, ed è per questo che non funziona il secondo metodo, ma in questo caso non esistono, perchè $ \frac{(n+1)!^2}{k} $ contiene ancora almeno un fattore $ k $ e di conseguenza $ \frac{(n+1)!^2}{k}+1 \equiv 1 \pmod{k} $, quindi non può essere potenza di $ k $. Ora funge?

Sì, dovrebbe abbastanza andare. Se proprio volessi essere puntigliosissimo, direi che non basta dimostrare che $\frac{(n+1)!^2}{k}+1$ non è potenza di $k$, ma bisognerebbe dimostrare che non possono essere potenze dello stesso primo (ad esempio, $\frac{(n+1)!^2}{k}+1=3^5$ e $k=3^3$); perchè questo non è possibile?

[<enigma>]

mostrarli esplicitamente (e boh, non so se si possa fare senza farli vedere)

Sì, si può! Anzi è un facile esercizio mostrare che, se $N(x)$ è la funzione di conteggio delle potenze di primi fino a $x$, allora $N(x) \sim x/\log x$ (assumendo il teorema dei numeri primi).
Si può però anche mostrare in modo elementare che i numeri primi (e anche le potenze di primi) hanno densità asintotica $0$ (esercizio); se esistesse un $N$ tale che ogni stringa di $N+1$ interi consecutivi contiene una potenza di primo, le potenze di primi avrebbero densità asintotica positiva di almeno $1/(N+1)$, contrariamente all'altro fatto. Questo si può rendere una dimostrazione elementare (libera dall'uso del PNT) e non costruttiva del teorema del thread; provare a scriverla per bene è un buon esercizio

[luca95]

Per chi fosse interessato nell'ultimo video di tdn del senior medium del 2011 c'è una dimostrazione di questa cosa simile a quella che propone <enigma>

[<enigma>]

Sì, ma con tale metodo questo problema ha un pezzo in più: mostrare che i numeri primi hanno densità $0$

[Drago96]

Alur, grazie al grosso aiuto di enigma, provo a scrivere per bene tutto, se c'è qualcuno a cui interessa...
Sia $A\subseteq\mathbb N$ un sottoinsieme dei naturali e definiamo la sua densità asintotica come $$\displaystyle d(A)=\lim_{n\to\infty}\frac{|A\cap[1,n]|}n$$

Parte 1 (del video): considerando $A=\{x^a:x\in\mathbb N,a\ge2\in\mathbb N\}$, allora $d(A)=0$
Fissiamo un $M\in\mathbb N$, allora gli elementi di $A$ minori di $M$ soddisfano $x^a\le M$ ovvero $x\le\sqrt[a]M$; quindi ci sono al più $M^{1/2}$ quadrati, $M^{1/3}$ cubi, ecc.
Il più grande $k$ tale che ci sia una potenza $k$-esima è quello con la base minore, ovvero $2$: abbiamo $2^k\le M$ da cui $k\le\log_2M$.
Abbiamo quindi $|A\cup[1,M]|\le M^{1/2}+\dots+M^{1/k}$ (e stiamo anche contando tre volte tipo le potenze seste, ma questo upper bound ci basta).
Facciamo ancora una stima più brutale e diciamo che $M^{1/a}\le M^{1/2}$, ed avendo $k$ termini otteniamo $|A\cup[1,M]|\le M^{1/2}\cdot k\le\log_2M\cdot M^{1/2}$.
Ora $\displaystyle\lim_{M\to\infty}\frac{\log_2M\cdot M^{1/2}}M$ è 0, perché il logaritmo cresce più lento di qualunque potenza (o se proprio volete, con quella cosa brutta di de l'Hopital)

Parte 2: $d(\mathbb P)=0$
Consideriamo i primi $n$ primi $p_1,p_2,\dots,p_n$ e sia $P=p_1\cdot p_2\cdot\dots\cdot p_n$ il loro prodotto; ci chiediamo ora quanti primi ci sono nell'intervallo $[1,P]$.
Sicuramente se un numero è divisibile per uno tra i $p_i$ e il quoziente è maggiore di 1, allora non è primo; i candidati primi sono dunque i numeri coprimi con $P$; abbiamo quindi $\mathbb P\cap[1,P]\le\varphi(P)+n$.
Vale che $\varphi(P)=(p_1-1)\dots(p_n-1)$ per come è definito; consideriamo allora il rapporto, che diventa $\displaystyle\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_n}\right)+\frac n P$ e dimostriamo che per $n\to\infty$ questo va a 0.
Prima il secondo pezzo, che è facile: $P\ge 2^n$ (ci sono $n$ fattori, tutti più grandi di $2$), e quindi $\displaystyle\frac n P\le\frac n{2^n}$ che va a 0 banalmente.
Ora, la parte interessante... "moralmente" quel prodotto è $1/\zeta(1)$, ma non lo dico troppo forte se no mi uccide... quindi facciamo le cose per benino:
$\displaystyle\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_n}\right)=e^{\displaystyle\log\prod\left(1-\frac1{p_i}\right)}=e^{\displaystyle\sum\log\left(1-\frac1{p_i}\right)}$
Poi, usando l'espansione del logaritmo $\displaystyle-\log(1-x)=x+\frac{x^2}2+\frac{x^3}3+\dots$ valida per $|x|<1$ diciamo che $\displaystyle\log\left(1-\frac1{p_i}\right)=-\frac1{p_i}+O(1/p_i^2)$, e quindi $\displaystyle\sum\log\left(1-\frac1{p_i}\right)=\sum-\frac1{p_i}+O(1/p_i^2)=O(1)-\sum\frac1{p_i}$ dato che la somma dei reciproci dei quadrati converge.
Siamo dunque arrivati a dire che $\displaystyle\left(1-\frac1{p_1}\right)\cdots\left(1-\frac1{p_n}\right)=e^{\displaystyle O(1)-\sum\frac1{p_i}}$; ma la somma dei reciproci dei primi diverge, quindi abbiamo un esponenziale di un numero sempre più piccolo, che allora tende a 0, che è ciò che volevamo.

Parte 3: tutto insieme
Siamo alla fine, perché detto $X$ l'insieme dei primi e delle potenze dei primi, ovvero $X=\{p^i:p\in\mathbb P,i\in\mathbb N\}$ abbiamo che $X\subset A\cup\mathbb P$, in modo che $d(X)\le d(A\cup\mathbb P)$; ma vale in generale $d(A\cup B)\le d(A)+d(B)$. E quindi alla fine abbiamo $d(X)=0$.
Se per assurdo ci fosse un $N$ tale che per ogni $N$ interi consecutivi trovo almeno un elemento di $X$, allora dividendo l'intervallo $[1,M]$ in blocchi da $N$ interi, si vede che $|X\cap[1,M]|=M/N$, portando ad una densità di $d(X)=\frac1 N$, che è assurdo perché la densità è nulla.