121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Messaggio da jordan » 28 lug 2012, 19:51

121. (Own) notazioni: Siano $\text{gpf}(x)$ e $\text{lpf}(x)$ il piu' grande fattore primo e il piu' piccolo fattore primo che dividono un intero $x>1$ e $\upsilon_p(x)$ la valutazione p-adica di $x$.
Definiamo infine la funzione aritmetica $f(\cdot):\mathbb{N}_0\to \mathbb{N}_0$ di modo tale che :
$f(n)=1$ se $n=1$ oppure se $\text{gpf}(n)<100$
$f(n)=\text{lpf}\left(n\prod_{p\in \mathbb{P}\cap[1,100]}{p^{-\upsilon_p(n)}}\right)$ altrimenti.

In altre parole, f(n) e' il piu' piccolo primo che divide n, che è maggiore di 100; se tale primo non esiste allora f(n)=1.


Dimostrare che, fissata una costante $C>10^{40}$, esistono infiniti interi positivi $n$ tali che $C<f(n)<f(n+1)<f(n+2)<...<f(n+99)<C^2$.
Ultima modifica di jordan il 29 lug 2012, 15:01, modificato 10 volte in totale.
The only goal of science is the honor of the human spirit.

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: 121. C<lpf(n)<lpf(n+1)<lpf(n+2)<C^(3/2)

Messaggio da Leonida » 28 lug 2012, 20:18

Ma almeno uno tra $ lpf(n) $, $ lpf(n+1) $ e $ lpf(n+2) $ è uguale a 2... Sbaglio?
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 121. C<lpf(n)<lpf(n+1)<lpf(n+2)<C^(3/2)

Messaggio da jordan » 28 lug 2012, 20:57

Leonida ha scritto:Ma almeno uno tra $ lpf(n) $, $ lpf(n+1) $ e $ lpf(n+2) $ è uguale a 2... Sbaglio?
Una piccola svista, grazie della correzione; con l'occasione, ho reso il problema un po piu' generale..
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Messaggio da jordan » 03 ago 2012, 16:55

Seppur e' un risultato che si puo' provare con tecniche "elementari", si puo' prendere "per dato" il postulato di Bertrand..
The only goal of science is the honor of the human spirit.

Avatar utente
Leonida
Messaggi: 61
Iscritto il: 12 set 2011, 19:37
Località: Maserada (Treviso)

Re: 121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Messaggio da Leonida » 04 ago 2012, 00:42

Lemma: esistono almeno 100 numeri primi $p$ tali che $C < p < C^2$.
Dim.: dimostro per induzione su $k$ che tra $C$ e $2^k C$ vi sono almeno $k$ numeri primi.
Passo base: $k=1$. Segue dal il Teorema di Chebyshef (o Postulato di Bertrand), il quale afferma che esiste almeno un primo tra $C$ e $2C$, purchè $C > 1$.
Passo induttivo: supponiamo esistano $k$ numeri primi tra tra $C$ e $2^k C$. Ancora per il Teorema di Chebyshef, esiste almeno un primo tra $2^k C$ e $2^{k+1} C$, perciò tra $C$ e $2^{k+1} C$ vi sono almeno $k+1$ primi e il passo induttivo è verificato.
In particolare esistono almeno 100 numeri primi $p$ tali che $C < p < 2^{100} C$. Ma $2^{100} C < 8^{34} C < 10^{34} C < 10^{40} C < C^2$ è vera poichè per ipotesi $C > 10^{40}$, da cui segue il Lemma.
Indico con $101 < 103 < ... < p_{C-1} \leq C$ i primi compresi tra 100 e $C$ e con $C < p_{C}< p_{C+1}< ... < p_{C+99} < C^2$ cento numeri primi compresi tra $C$ e $C^2$ (esistono per il Lemma). E' sufficiente scegliere $n$ in modo che risolva il seguente sistema di congruenze:
\[
\left\{
\begin{array}{l}
n \equiv 1 \pmod {101} \\
n \equiv 1 \pmod {103} \\
n \equiv 1 \pmod {...} \\
n \equiv 1 \pmod {p_{C-1}} \\
n +i \equiv 0 \pmod {p_{C +i}}, \forall i, 0 \leq i \leq 99
\end{array}
\right.
\]
Innanzitutto per il Teorema Cinese del Resto esistono infinite soluzioni a questo sistema di congruenze, dato che i moduli sono a due a due coprimi. Inoltre, se $101 \leq p \leq p_{C-1}$, $n +i \equiv i+1 = 1, ... , 100 \not \equiv 0 \pmod p$.
Pertanto $f(n +i) \geq p_{C} > C$, $\forall i, 0 \leq i \leq 99$.
Allora $f(n +i) = p_{C +i}$ ; di conseguenza $f(n) < f(n+1) < ... < f(n +99) < C^2$ è vera perchè lo è $p_C < p_{C +1} < ... < p_{C +99} < C^2$. In conclusione, si ha $C < f(n) < f(n+1) < ... < f(n +99) < C^2$ che è la tesi.
P.S.: dato che questa soluzione è un po' barata, se qualcuno ne ha una che non passi per il Postulato di Bertrand mi sembra giusto cedergli il testimone della staffetta.
Cit.: "Ora, qui, su questo aspro frammento di terra chiamato Platea, le orde di Serse affrontano LA LORO DISFATTA!!"

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Messaggio da jordan » 04 ago 2012, 10:21

Leonida ha scritto:[...]
P.S.: dato che questa soluzione è un po' barata, se qualcuno ne ha una che non passi per il Postulato di Bertrand mi sembra giusto cedergli il testimone della staffetta.
La definirei "barata" solo se hai l'impressione di usare un "cannone" senza un'idea di come si dimostra
In ogni caso, vai avanti, perchè la dimostrazione dell'esistenza di almeno 100 primi nell'intervallo $[C,C^2]$ deve passare da qualche disuguaglianza sulla distribuzione di $\mathbb{P}$, e mi pare questa sia la soluzione piu' naturale..
The only goal of science is the honor of the human spirit.

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: 121. C<f(n)<f(n+1)<...<f(n+99)<C^2

Messaggio da jordan » 07 ago 2012, 12:05

Visto che sono già 3 giorni che non viene postato il problema 122, si faccia avanti chi vuole
The only goal of science is the honor of the human spirit.

Rispondi