Problem 401 of the Euler Project in Maxima

Question

Problem 401 of the Euler Project in Maxima

Navigation

#1 by (3 votes)

2

Problem statement:

The divisors of 6 are 1,2,3 and 6. The sum of the squares of these numbers is:

1 + 4 + 9 + 9 + 36 = 50

Allow sigma2(n) to represent the sum of the squares of the divisors of n.

Thus, sigma2 (6) = 50 .

Y sumas_sigma2(n) is the sum of all sigma2, less than or equal to n. For example,

sumas_sigma2(6) = 113

This is what I have programmed:

/* sigma2(n) devuelve la suma de los divisores de n elevados al
   cuadrado. Por ejemplo,
   sigma2(6);
    50
*/

sigma2(n) :=
   divsum(n,2)$

sumas_sigma2(n) :=
    lreduce("+", makelist(sigma2(k), k, 1, n))$

But, it's very inefficient. Well I need to calculate sumas_sigma(10^8) and my algorithm is not able to calculate it, in less than a minute.

maxima

asked by aprendiendo-a-programar 07.03.2018 в 12:53

source

1 answer

Problem with foreign keys in hosting with php Write to a file mapped in memory (using mmap)

score 3 · Accepted Answer

After the magnificent help of different users of stackOverflow and Mathematics, I have arrived at the following solution, which is able to solve the problem in a good interval of time (5 secs - 7 secs)

sigma2(n) :=
   divsum(n,2)$

sumas_sigma2(n) :=
    sum(sumas_sigma2(k), k, 1, n)$
    memoize(sumas_sigma2);

Once again, thank you very much everyone.