numero di divisori primi di n dalla Germania

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
Leblanc
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00

numero di divisori primi di n dalla Germania

Messaggio da Leblanc » 16 giu 2006, 15:28

Dato un intero positivo n, sia $ f(n) $ il numero di divisori primi diversi di n; ad esempio $ f(24)=2 $. Dimostrare che esistono infiniti interi positivi per cui $ f(n)<f(n+1)<f(n+2) $

Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Messaggio da what » 20 giu 2006, 13:34

uff che problema infido...

diciamo che vogliamo trovare infiniti naturali a per cui $ n=2^a $ mi soddisfa la relazione nel testo.

pensiamo prima alla disuguaglianza di sinistra, e cerchiamo i casi che non ci vanno bene (mi pare fosse anche un vecchio cesenatico), ossia risolviamo $ 2^a+1=p^b $ con p primo.
trascuriamo il caso $ p=2 $, perché porta ad una singola soluzione particolare e quindi non ci disturba.

abbiamo $ 2^a=(p-1)(p^{b-1}+...+p+1) $ e dunque $ p-1=2^k $ per qualche k>0.
Se $ b>1 $, allora $ p^{b-1}+...+p+1>p-1 $, quindi anche $ p^{b-1}+...+p+1 $ è una potenza di 2 maggiore di 1
Ma chiaramente $ p^{b-1}+...+1\equiv b \pmod 2 $ ossia b è pari. Scriviamo b=2h e si ha che $ p^h-1,p^h+1 $ sono entrambe potenze di 2, quindi $ (a,b,p)=(3,2,3) $ che ancora una volta è una soluzione singola e non ci crea problemi.
Resta da analizzare il caso $ b=1 $. Ma è un fatto noto che se $ 2^a+1 $ è primo allora $ a $ è una potenza di 2.

In sostanza, possiamo star sicuri che se prendiamo $ a\neq 0,3 $ ed $ a $ non potenza di 2 abbiamo $ 1=f(p^a)<f(p^a+1) $.


Resta da sistemare la disuguaglianza di destra, dobbiamo cioè assicurarci che
$ f(2^a+1)<f(2^a+2)=f(2(2^{a-1}+1))=1+f(2^{a-1}+1) $

Dimostriamo che presi molti interi consecutivi, ce n'è almeno uno (diciamo y) tale che n=2^y soddisfi la relazione del testo.
Siano ora $ x_1,...,x_m $ m interi consecutivi ordinati in modo crescente.
Supponiamo per assurdo che $ f(2^{x_m}+1)>...> f(2^{x_1}+1)\geq 1 $

Allora $ f(2^{x_m}+1) \ge m $ da cui $ \displaystyle 2^{x_m}+1 \ge \prod_{i=1}^m p_i $ dove $ p_i $ rappresenta l'i-esimo primo.
Ma si vede abbastanza facilmente che l'ultima relazione è falsa per m molto grandi.

Dunque se prendo una sequenza abbastanza lunga di interi, ce ne sarà almeno uno che mi va bene. Inoltre, per quanto lunga sia questa sequenza, riesco sempre a fare in modo che non contenga potenze di 2; così facendo, trovo un $ a $ che mi soddisfa entrambe le disuguaglianze. Poiché chiaramente posso prendere infinite sequenze abbastanza lunghe, posso trovare anche infiniti $ a $ che mi vanno bene.
Ultima modifica di what il 20 giu 2006, 23:00, modificato 1 volta in totale.

Poeth
Messaggi: 37
Iscritto il: 17 giu 2006, 14:46

Messaggio da Poeth » 20 giu 2006, 13:59

Mmmm mi piacerebbe risolverla in un altro modo... però non riesco a completarla: mi dite se è fattibile?

Posto x un numero primo, avrà sicuramente meno divisori di x+1.
x+1 è nella forma 2n, x+2 nella forma 2n+1

quindi $ f(x)<f(x+1) $

Ma poi non so continuare..


E' dimostrabile che 2n ha meno divisori di 2n+1, posto che 2n-1 è un numero primo? (e ovviamente 2n+1 non sia un suo gemello)

Potrebbe essere anche spunto di un altro problema :P


OT adoro i numeri primi =) /OT
Ecco le prime buffe formule che ho scoperto.... ne sono fierissimo anche se sono inutili :D

[tex]\pi \simeq 10*(\sqrt{2} - 1) -1

e\pi(\pi+e) \simeq (\frac{10}{\sqrt2})^{2}

2*phi \simeq 1+ \sqrt{\frac{e\pi(e+\pi)}{10}}
[/tex]

Avatar utente
moebius
Messaggi: 433
Iscritto il: 08 mag 2005, 19:14

Messaggio da moebius » 20 giu 2006, 16:46

Poeth ha scritto: E' dimostrabile che 2n ha meno divisori di 2n+1, posto che 2n-1 è un numero primo? (e ovviamente 2n+1 non sia un suo gemello)
Sia che fosse inteso come numero di "divisori" o come numero di "divisori primi": n=12, 2n=24 (2n-1=13) 2n+1=25 è un controesempio.
Fondatore: [url=http://olimpiadi.dm.unipi.it/oliForum/viewtopic.php?t=8899]Associazione non dimenticatevi dei nanetti![/url]
Membro: Club Nostalgici
Sono troppo scarso in italiano per usare parole con la c o la q...

Avatar utente
Leblanc
Messaggi: 173
Iscritto il: 01 gen 1970, 01:00

Messaggio da Leblanc » 20 giu 2006, 20:16

What, bella soluzione :) , anch'io avevo seguito piu' o meno lo stesso percorso

Per quanto riguarda l'idea di dimostrare che 2n ha meno divisori di 2n+1 per infiniti n, con 2n-1 primo, sinceramente non saprei proprio da dove partire... non dico che sia impossibile ovviamente, pero' non sembra affatto facile.

Rispondi