Il secondo fattore primo

[Gianfranco]

Attenzione, ho modificato il testo in base a un'osservazione di Panurgo e ad altre su Facebook.

1) Formulazione amichevole.
La probabilità che il secondo fattore primo di un intero positivo scelto a caso sia 37 è circa 1/2.

2) Formulazione più precisa.
Supponiamo di scegliere a caso un numero intero positivo k nell’intervallo [1,n].
La probabilità che il secondo fattore primo di k sia 37 è circa 1/2, per n che tende a infinito.
Provate a verificarlo scrivendo un programmino per computer in un linguaggio a vostra scelta.

3) Formulazione fulminante.
37 è la MEDIANA dei secondi fattori primi dei numeri interi positivi.
---
Cosa si intende per secondo fattore primo.
---
$19395 = 3^2 \cdot 5 \cdot 431$
il secondo fattore primo è 5 che è minore di 37.
---
$431261 = 53 \cdot 79 \cdot 103$
il secondo fattore primo è 79 che è maggiore di 37.
---
$4546449= 3^4 \cdot 37^2 \cdot 41$
il secondo fattore primo è 37.
---
Potete trovare la probabilità in modo sperimentale, con un programmino per computer.
Questo problema è stato segnalato da Chris Grossack.

[panurgo]

Come dobbiamo interpretare il concetto di secondo divisore primo? Per esempio, qual è il secondo divisore primo di $12$: $2$ (come $2\cdot 2 \cdot 3$) o $3$ (come $2^2\cdot 3$)?

[Gianfranco]

Come dobbiamo interpretare il concetto di secondo divisore primo? Per esempio, qual è il secondo divisore primo di $12$: $2$ (come $2\cdot 2 \cdot 3$) o $3$ (come $2^2\cdot 3$)?

Buongiorno Panurgo, giusta domanda, grazie.
La seconda che hai detto.
Vado subito a correggere il testo originale.
Avevo citato una breve notizia di David Eppstein ma poi sono andato a leggere l'articolo originale di Chris Grossack che spiega meglio questa proprietà di 37.
Link: https://grossack.site/2023/11/08/37-median.html

[panurgo]

Avevo citato una breve notizia di David Eppstein ma poi sono andato a leggere l'articolo originale di Chris Grossack che spiega meglio questa proprietà di 37.

...

[Gianfranco]

...

La mia domanda NON è di dimostrare matematicamente quella proprietà ma di stimarla con un programmino per computer scritto in un linguaggio a piacere.

[franco]

Giusto un altro chiarimento (poi provo a scrivere il programmino).
Nel caso il numero scelto a caso sia esso stesso un numero primo come ci comportiamo?
Lo escludiamo dal computo delle probabilità visto che non esiste un secondo fattore primo?

[Gianfranco]

Grazie Frenco, la cosa si fa sempre più interessante.
Nell'articolo di Chris Grossack la cosa che chiedi non mi sembra chiarissima.
Infatti, nel codice del suo programmino (credo in Python) c'è scritto:
...
else:
# If there's only one prime factor
# say the second prime factor is infinity
data += [oo]
...

Sembra che il secondo fattore dei numeri primi sia posto a "infinito" e messo nella lista dei "secondi fattori primi".
Però non è chiaro (per me) come Python tratta questo dato nel calcolo della mediana.
Inoltre mi chiedo: se includiamo o escludiamo i numeri primi dal conteggio, il risultato cambia, per n abbastanza grande?
Liberi di indagare.

[Gianfranco]

Nel caso il numero scelto a caso sia esso stesso un numero primo come ci comportiamo?
Lo escludiamo dal computo delle probabilità visto che non esiste un secondo fattore primo?

Il Matematico Alberto Saracco mi ha chiarito (in un post su Facebook) che escludere i numeri primi dal conteggio, per n che tende a infinito, non cambia il risultato perché la densità dei numeri primi negli interi è zero.

[Quelo]

Secondo i miei calcoli, la probabilità che il secondo fattore primo sia minore o uguale di 37 è circa del 50%

Segnalo che 1 non ha fattori primi, quindi sono partito da 2.

per n = 10 milioni, questi sono i risultati per i fattori primi fino a 97:

Codice: Seleziona tutto

f2 <= 3; p = 16.667%
f2 <= 5; p = 26.667%
f2 <= 7; p = 33.333%
f2 <= 11; p = 37.316%
f2 <= 13; p = 40.539%
f2 <= 17; p = 42.909%
f2 <= 19; p = 44.963%
f2 <= 23; p = 46.613%
f2 <= 29; p = 47.89%
f2 <= 31; p = 49.062%
f2 <= 37; p = 50.025%
f2 <= 41; p = 50.88%
f2 <= 43; p = 51.683%
f2 <= 47; p = 52.407%
f2 <= 53; p = 53.039%
f2 <= 59; p = 53.6%
f2 <= 61; p = 54.137%
f2 <= 67; p = 54.621%
f2 <= 71; p = 55.073%
f2 <= 73; p = 55.511%
f2 <= 79; p = 55.913%
f2 <= 83; p = 56.294%
f2 <= 89; p = 56.649%
f2 <= 97; p = 56.973%

Programma scritto in Python:

Codice: Seleziona tutto

def primefact(x,n,b):
    f = []
    p = 2
    while x >= p:
        e = 0
        while x % p == 0:
            x = x // p
            e += 1
        if e > 0:
            f.append((p,e))
            if len(f) > n-1: break
        if p == 2: p = 3
        else: p += 2
        if p > b: break
    if f == []: f = [(x,1)]
    return f

n = 10000000
m = [0]*100
s = [0]*100

for i in range(2,n):
    p = primefact(i,2,97)
    if len(p) == 1: p.append((n+1,1))
    q,r = p[1]
    if q < len(m): m[q] += 1

for j in range(len(m)):
    if m[j] > 0: s[j] = sum(m[:j+1])

for j in range(len(s)):
    if s[j] > 0:
        print(f'f2 <= {j}; p = {round((s[j]+1)/n*100,3)}%')

SE&O

[Quelo]

Analizzando i dati mi sono accorto che la probabilità che il secondo fattore primo sia <= 3 è 1/6
Questo si spiega facilmente considerando che i numeri pari sono la metà del totale e quelli multipli di 3 sono un terzo, quindi quelli che hanno il 3 come secondo fattore primo (il primo è per forza il 2) sono i multipli di 6
Se p1 = 2 e p2 = 3, abbiamo una sola possibilità ogni p1 x p2 numeri, cioè 1 su 6

Passando al 5 avremo p1 = 2, p2 = 3 e p3 = 5
I numeri che hanno come secondo fattore primo il 5 sono i numeri pari multipli di 10 (fattori primi 2 e 5) e i numeri dispari multipli di 15 (fattori primi 3 e 5)
Dai multipli di 10 devo togliere i multipli di 3: 1/10 - 1/30 = 2/30
Dai multipli di 15 devo togliere i multipli di 2: 1/15 - 1/30 = 1/30

Complessivamente la probabilità che un numero abbia come secondo fattore primo il 5 si calcola con questa formula

$P_{\large p3}=\displaystyle \frac{(p2-1)+(p1-1)}{p1 \cdot p2 \cdot p3}=\frac{(p2-1)+(p1-1)}{p3\#}=\frac{2+1}{30}=\frac{1}{10}$

Con 7 avremo 4 parametri (2,3,5,7), per ogni combinazione di 2 fattori (2,7), (3,7), (5,7), ne rimangono fuori 2 (3,5), (2,5), (2,3)
Quindi la nostra formula diventa

$P_{\large p4}=\displaystyle \frac{(p2-1)(p3-1)+(p1-1)(p3-1)+(p1-1)(p2-1)}{p4\#}=\frac{8+4+2}{210}=\frac{1}{15}$

Sommando si ottengono i risultati già visti

$P_{<=3}=16,6666667%$
$P_{<=5}=26,6666667%$
$P_{<=7}=33,3333333%$

Iterando il processo fino a 37

$P_{<=37}=50,0247504%$

[Gianfranco]

Grazie Sergio, ti ringrazio di cuore!
Ho letto le tue risposte e ho capito i concetti espressi ma meritano ancora una meditazione approfondita.
A presto.

[Quelo]

Ti ringrazio per l'apprezzamento, anche se non sempre ho gli strumenti matematici adatti, cerco di arrivarci con il ragionamento.

Metto qualche schema per supportare le mie argomentazioni
Con 2x, 3x indico i numeri che sono multipli di 2, di 3, ecc... mentre con (2x), (3x) indico i numeri che non sono multipli di 2, 3, ecc...

SecondoPrimo3.png (5.02 KiB) Visto 81651 volte

SecondoPrimo5.png (13.45 KiB) Visto 81651 volte

SecondoPrimo7.png (29.13 KiB) Visto 81651 volte