Tutti i primi minori o uguali di n

[HiTLeuLeR]

Siano n un intero > 1 e $ p_1, p_2, \ldots, p_m $ tutti i primi $ \le n $, con l'assuzione che $ p_1 < p_2 < \ldots < p_k $. Si dimostri che $ s_n = \displaystyle\sum_{i} \left\lfloor \frac{n}{p_{i_1} p_{i_2} \ldots p_{i_k}}\right\rfloor $ ha parità differente da $ n $, se la sommatoria indicata si estende a tutti e soli i sottoinsiemi non vuoti di tipo $ i = (i_1, i_2, \ldots, i_k) $ dell'm-upla $ (1, 2, \ldots, m) $ tali che $ i_1 < i_2 < \ldots < i_k $.

Esempio: n = 6; m = 3; $ p_1 = 2; p_2 = 3; p_3 = 5 $. Vale $ \displaystyle s_6 = \left\lfloor \frac{6}{2}\right\rfloor + \left\lfloor \frac{6}{3}\right\rfloor + \left\lfloor \frac{6}{5}\right\rfloor + \left\lfloor \frac{6}{6}\right\rfloor + \left\lfloor \frac{6}{10}\right\rfloor + \left\lfloor \frac{6}{15}\right\rfloor +\left\lfloor \frac{6}{30}\right\rfloor = 7 $, e perciò $ s_6 $ non ha la stessa parità di 6.

[Santana]

Definiamo il seguente insieme $ P(n)=\{ a>1 : \mu^2(a)=1 , p|a \Rightarrow p\leq n \} $

Abbiamo che $ s_n=\sum_{k \in P(n)} \left\lfloor \frac{n}{k} \right\rfloor $

Dimostriamo per induzione, $ 2|s_n+n+1 $ allora $ 2|s_{n+1}+n+2 $.

Caso 1 $ n+1 $ non è primo

Allora sarà $ P(n)=P(n+1) $ e

$ s_{n+1}=\sum_{k \in P(n)} \left\lfloor \frac{n+1}{k} \right\rfloor $

sappiamo che (1) $ \lfloor \frac{n+1}{k} \rfloor - \lfloor \frac{n}{k} \rfloor $ è $ =1 $ se $ k|n+1 $ altrimenti è $ =0 $, da cui

$ s_{n+1}=s_{n}+\sum_{d \in P(n),d|n+1} 1=s_{n}+2^{\omega(n+1)}-1 $

dove $ \omega(n) $ è il numero di primi distinti che dividono $ n $, otteniamo come volevamo $ 2|s_{n+1}+n+2 $.

Caso 2 $ n+1 $ è primo, scriviamo $ n+1=q $

Si ha $ P(n+1)=P(n) \cup \{aq: a \in P(n) \vee a=1\} $ e $ P(n) \cap \{aq: a \in P(n) \vee a=1\}=\{\} $, quindi

$ s_{n+1}=\sum_{k \in P(n)} \left\lfloor \frac{n+1}{k} \right\rfloor+\sum_{k \in P(n)} \left\lfloor \frac{n+1}{kq} \right\rfloor $

e con (1) si ricava facilmente $ s_{n+1}=s_{n}+1 $ da cui anche stavolta $ 2|s_{n+1}+n+2 $

[HiTLeuLeR]

Definiamo il seguente insieme $ P(n)=\{ a>1 : \mu^2(a)=1 , p|a \Rightarrow p\leq n \} $

Non mi è del tutto chiaro come definisci l'insieme P(n). Forse che p deve intendersi primo, qui sopra? Di modo che P(n) sia non altri che l'insieme degli interi > 1 e liberi da quadrati i cui divisori primi in N sono tutti $ \le n $?

[Santana]

Si $ p $ è primo, $ P(n) $ è appunto l'insieme degli interi > 1 e liberi da quadrati i cui divisori primi in N sono tutti $ \le n $?

[HiTLeuLeR]

Caso 1 $ n+1 $ non è primo. Allora sarà $ P(n)=P(n+1) $ [...]

...e allora come spieghi che P(5) = {2, 3, 5} e P(6) = {2, 3, 5, 6} ?

[Santana]

Caso 1 $ n+1 $ non è primo. Allora sarà $ P(n)=P(n+1) $ [...]

...e allora come spieghi che P(5) = {2, 3, 5} e P(6) = {2, 3, 5, 6} ?

Da come ho definito P abbiamo che P(5)={2,3,5,6} infatti P(5) contiene tutti gli interi >1 liberi da quadrati divisibili solo per numeri primi <=5, e 6=2x3 appartiene a P(5).

[HiTLeuLeR]

Da come ho definito P abbiamo che P(5)={2,3,5,6} infatti P(5) contiene tutti gli interi >1 liberi da quadrati divisibili solo per numeri primi <=5, e 6=2x3 appartiene a P(5).

Ah, d'accordo - forse finalmente ho capito! Non so perché, avevo assunto - e non era detto da nessuna parte - che gli elementi di P(n) dovessero esser pure $ \le n $ - forse colpa delle sassate prese in testa, ieri, alla cascate di Maisano!? Però a questo punto P(5) = P(6) = {2, 3, 5, 6, 10, 15, 30}, no?

[Santana]

Da come ho definito P abbiamo che P(5)={2,3,5,6} infatti P(5) contiene tutti gli interi >1 liberi da quadrati divisibili solo per numeri primi <=5, e 6=2x3 appartiene a P(5).

Ah, d'accordo - forse finalmente ho capito! Non so perché, avevo assunto - e non era detto da nessuna parte - che gli elementi di P(n) dovessero esser pure $ \le n $ - forse colpa delle sassate prese in testa, ieri, alla cascate di Maisano!? Però a questo punto P(5) = P(6) = {2, 3, 5, 6, 10, 15, 30}, no?

Ah si giusto bisogna moltiplicare anche 2x5 3x5 ecc. in ogni caso P(n+1)=P(n) se n+1 non è primo

[HiTLeuLeR]

Ho appena finito di leggere per intero la tua soluzione, Santana. E' molto bella, oltre che corretta.

[Santana]

Ho appena finito di leggere per intero la tua soluzione, Santana. E' molto bella, oltre che corretta.

Grazie, immagino quindi la tua soluzione fosse diversa... se non ti toglie troppo tempo postarla mi farebbe piacere vederla

[HiTLeuLeR]

Grazie, immagino quindi la tua soluzione fosse diversa... se non ti toglie troppo tempo postarla mi farebbe piacere vederla

Volentieri: i) $ \displaystyle 1 = \sum_{k=1}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor = n + \sum_{k=2}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor $; ii) $ \displaystyle \sum_{k=2}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor \equiv \sum_{k=2}^n \mu^2(k) \left\lfloor \frac{n}{k}\right\rfloor \bmod 2 $.

[Santana]

Grazie, immagino quindi la tua soluzione fosse diversa... se non ti toglie troppo tempo postarla mi farebbe piacere vederla

Volentieri: i) $ \displaystyle 1 = \sum_{k=1}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor = n + \sum_{k=2}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor $; ii) $ \displaystyle \sum_{k=2}^n \mu(k) \left\lfloor \frac{n}{k}\right\rfloor \equiv \sum_{k=2}^n \mu^2(k) \left\lfloor \frac{n}{k}\right\rfloor \bmod 2 $.

Sintetica, meglio di così