(1^1 + 2^2 + ... + n^n) mod p

[info]

mmm... Io ponevo x = kp(p-1)...

Inoltre piu che su G(1,x) lavoravo su G(0,x) che e poi A_x... dovevo trovare una x adatta e quindi, come dopo affermo, consideravo i primi p(p-1) termini della sequenza e li ripetavo p volte di modo che A_p^2(p-1) risultava divisibile per p... Fammi sapere!

ps: scusa gli accenti ma queste tastiere straniere sono impossibili!

[HiTLeuLeR]

[...] # data la periodicita, prendo il valore della somma dei primi x^x in un periodo e lo ripeto p volte di modo che A_p^2(p-1) e divisibile per p e la x trovata e della forma che avevamo posto prima. Questo e quanto ci si era proposti di trovare, che dovrebbe essere sufficiente….

Ok, ci siamo! E' solo che mi era letteralmente sfuggito il pezzettino qui sopra... Certo al tutto manca un po' d'ordine, info, ma di fatto hai colto nel segno. MOLTO BRAVO, il problema non era per nulla semplice.

Tanto per la cronaca, anche questo l'ho scritto e risolto da me (sì, esattamente, ne sto rivendicando il copyright! ), per rispondere ad un quesito decisamente più elementare tratto dall'Olimpiade Nazionale Russa del 1988. A questo punto dovrebbe essere *banale* rispondergli. Dunque eccolo, tutto per voi:

Problema #2: mostrare ch'esistono infiniti termini della sequenza $ 1^1, 1^1 + 2^2, 1^1 + 2^2 + 3^3, \ldots $ che siano contemporaneamente dispari e composti.

[enomis_costa88]

ok provo con il problema 2:

Sia $ f(n)= \sum_{i=1}^{n} i^i $

se $ n \equiv 0 (mod 3) $ allora $ n^n \equiv 0 (mod 3) $
se $ n \equiv 1 (mod 3) $ allora $ n^n \equiv 1^n \equiv 1 (mod 3) $
se $ n \equiv 2 (mod 3) $ allora $ n^n \equiv 2^n (mod 3) $ ovvero $ n^n \equiv 1 (mod 3) $ se n è pari e $ n^n \equiv 2 (mod 3) $ se n è dispari.

per cui modulo 3 la sequenza n^n si riscrive come: 1,1,0,1,2,0 e a ripetersi (mod 6)
la somma modulo 3 sarà: 1;1+1;1+1+0;1+1+0+1;1+1+0+1+2;1+1+0+1+2+0..dove il sesto termine è $ \equiv 2 (mod 3) $ per cui il dodicesimo sarà $ \equiv 4 \equiv 1 (mod 3) $ e il diciottesimo sarà $ \equiv 6 \equiv 0 (mod 3) $ e poi si ripeterà tutto modulo diciotto.

noto (ma è ininfluente: al fine della dimostrazione potevamo accontentarci degli n $ \equiv 0 (mod 18 $ )) quindi che i numeri della sequenza $ \sum_{i=1}^{n} i^i $ con $ n \equiv $ 4,7,14,15,16,17,0 (mod 18 ) sono multipli di 3.

Devo ora capire se sono tutti pari o se per mia fortuna c'è di mezzo qualche dispari.

Un numero della sequenza f(n) è pari se c'è un numero pari di numeri dispari nella sommatoria altrimenti è dispari (per convincersene basta ossevare gli $ n^n $ modulo 2 che è equivalente all'osservazione degli n modulo 2).
Per cui cambia parità ogni due elementi della sequenza f(n) ovvero modulo 4. I numeri appartenenti alla sequenza pari saranno quelli con $ n \equiv 3,0 (mod 4) $ gli altri saranno dispari .

ora basta analizzare modulo 4 i numeri di prima..e io lo farò solo per i multipli di 18(che fannullone che sono..)..
$ 18 \equiv 2(mod 4) $ per cui i suoi multipli saranno alternativamente $ \equiv $ 2 e 0 (mod 4) e per quanto detto prima agli infiniti multipli di 18 $ \equiv 2 (mod 4) $ si associa un f(n) dispari e composta..

Buona serata Simone

Ps l'ho notato solo ora..questo problema è vecchio quanto me!

[HiTLeuLeR]

Sì, enomis, è tutto corretto! Soltanto nota che, a fronte dell'ottimo lavoro svolto da info, avresti potuto semplicemente considerare che, posto $ a_n = 1^1 + 2^2 + \ldots + n^n $, per ogni $ n\in\mathbb{N}_0 $, risulta $ a_2 \equiv a_{2 + 100k} \bmod 10 $, quando $ k\in\mathbb{N} $, e concludere osservando che $ 5 \mid a_2 $; $ a_2 \equiv 1 \bmod 2 $ e $ \{a_n: n \in\mathbb{N}_0\} $ è una sequenza monotona crescente. Del resto, se ci presti attenzione, anche tu hai sfruttato la periodicità della successione dei resti! Ma vabbè...

[info]

Grazie, Hitleuler... e sempre un piacere azzeccare un tuo problema

[jordan]

Problema: per ogni intero $ n > 0 $, sia $ a_n = 1^1 + 2^2 + \ldots + n^n $. Essendo $ p $ un numero primo naturale, mostrare che esiste allora $ T_p \in \mathbb{N}_0 $ tale che, per ogni $ n\in\mathbb{N}_0 $: $ r_{n+T_p} = r_n $, dove $ r_n $ è il resto della divisione intera di $ a_n $ per $ p $, quando $ n\in\mathbb{N}_0 $.

Premetto che ho letto solo il testo e forse c'è già la soluzione qui sopra, ma questa e' la mia versione..

Per $p=2$ e' sufficiente scegliere $T_2=4$ dal momento che $r_{n+4}-r_n=(n+1)^{n+1}+(n+2)^{n+2}+(n+3)^{n+3}+(n+4)^{n+4}$ che e' pari, dato che e' somma di due pari e due dispari.

Per $p>2$ e' sufficiente scegliere $T_p=p\varphi(p)$ dal momento che $r_{n+p(p-1)}-r_n=\displaystyle \sum_{1\le i\le p(p-1)}{(n+i)^{n+i}}$ ; in questa sommatoria compaiono (come basi delle potenze) esattamente $p-1$ multipli di $j$, per ogni $1\le j\le p$. Dato che vale che $p\mid a^p-a$ possiamo concludere in $\mathbb{Z}/p\mathbb{Z}$ che: $\displaystyle \sum_{1\le i\le p(p-1)}{(n+i)^{n+i}} = \sum_{1\le i\le p}{\left(\sum_{1\le j\le p-1}{i^j}\right)}$ $\displaystyle =\sum_{1\le j\le p-1}{\left(\sum_{1\le i\le p}{i^j}\right)}=0$. []

[julio14]

Senza conti: riducendo tutto modulo p e usando lft, sia la base che l'esponente sono periodici, quindi $ k^k $ è periodico, quindi le somme sono periodiche perché $ \mathbb{Z}_p $ è finito.

[jordan]

Giusto, il testo infatti non richiedeva di cercare il valore di un tale $T_p$