OliForum Matematico

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.

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 $

Santana ha scritto: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 $?

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 $?

Santana ha scritto: 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} ?

HiTLeuLeR ha scritto:

Santana ha scritto: 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).

Santana ha scritto: 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?

HiTLeuLeR ha scritto:

Santana ha scritto: 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

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

HiTLeuLeR ha scritto: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

Santana ha scritto: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 $.

HiTLeuLeR ha scritto:

Santana ha scritto: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ì