Eccoci.

Self Powers

ℹ️Published on Friday, 18th July 2003, 06:00 pm; Solved by 120889;
Difficulty rating: 5%

Problem 48

The series, $1^1 + 2^2 + 3^3 + \cdots + 10^{10} = 10405071317$.

Find the last ten digits of the series, $1^1 + 2^2 + 3^3 + \cdots + 1000^{1000}$.

Soluzione

Ancora un semplice esercizio che si appoggia alla comoda funzione powermod(a,b,m), che calcola \(a^b \mod m\). Volendo ce la si fa anche in una sola linea:

@time mod(sum([powermod(i,i,10^10) for i in 1:1000]),10^10)

  0.085799 seconds (76.06 k allocations: 3.742 MiB, 99.66% compilation time)
9110846700

che però è più dispendiosa perché alloca materialmente il vettore delle potenze \(i^i\). Altrimenti qui segue la sua forma estesa, più classica, che calcola una valore per volta e quindi non alloca memoria inutile:

sol = 0
@time for i in 1:1000
	global sol += powermod(i,i,10^10)
end
@show mod(sol,10^10)

  0.000200 seconds (1.89 k allocations: 29.562 KiB)
mod(sol, 10 ^ 10) = 9110846700