StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here's a solution, keeping in mind the spirit of [Project] Euler. [Warning: <strong>spoiler</strong>. I've tried to keep the hints slow, so that you can read only part of the answer and think on your own if you want. :)]</p> <p>When you are confronted with a problem having to do with numbers, one good strategy (as you probably already know from solving 210 Project Euler problems) is to look at small examples, find a pattern, and prove it. [The last part may be optional depending on your attitude to mathematics ;-)]</p> <p>In this problem, though, looking at small examples -- for n=1,2,3,4,... will probably not give you any hint. But there is another sense of "small examples" when dealing with number-theoretic problems, which you also probably know by now -- primes are the building blocks of the natural numbers, so start with the primes.</p> <p>For a prime number p, its only divisors are 1 and p, so the sum of the squares of its divisors is 1+p<sup>2</sup>.<br/> For a prime power p<sup>k</sup>, its only divisors are 1, p, p<sup>2</sup>, … p<sup>k</sup>, so the sum of the squares of its divisors is 1+p+p<sup>2</sup>+…+p<sup>k</sup>=(p<sup>k+1</sup>-1)/(p-1).<br/> That was the simplest case: you've solved the problem for all numbers with only one prime factor.</p> <p>So far nothing special. Now suppose you have a number n that has <em>two</em> prime factors, say n=pq. Then its factors are 1, p, q, and pq, so the sum of the squares of its divisors is 1+p<sup>2</sup>+q<sup>2</sup>+p<sup>2</sup>q<sup>2</sup>=(1+p<sup>2</sup>)(1+q<sup>2</sup>). <br/> What about n=p<sup>a</sup>q<sup>b</sup>? What is the sum of the squares of its factors?</p> <p>[............................Dangerous to read below this line...................]</p> <p>It is ∑<sub>0≤c≤a, 0≤d≤b</sub>(p<sup>c</sup>q<sup>d</sup>)<sup>2</sup> = ((p<sup>a+1</sup>-1)/(p-1))((q<sup>b+1</sup>-1)/(q-1)).</p> <p>That should give you the hint, both on what the answer is and how to prove it: the sum of the divisors of n is simply the product of the (answer) for each of the prime powers in its factorization, so all you need to do is to factorize 64000000 (which is very easy to do even in one's head :-)) and multiply the answer for each (=both, because the only primes are 2 and 5) of its prime powers.</p> <p>That solves the Project Euler problem; now the moral to take away from it.</p> <p>The more general fact here is about <em>multiplicative functions</em> -- functions on the natural numbers such that f(mn) = f(m)f(n) whenever gcd(m,n)=1, i.e. m and n have no prime factors in common. If you have such a function, the value of the function at a particular number is completely determined by its values at prime powers (can you prove this?)</p> <p>The slightly harder fact, which you can try to prove[it's not <em>that</em> hard], is this: if you have a multiplicative function f [here, f(n)=n<sup>2</sup>] and you define the function F as F(n) = ∑<sub>d divides n</sub>f(d), (as the problem did here) then F(n) is also a multiplicative function.</p> <p>[In fact <a href="http://en.wikipedia.org/wiki/M%C3%B6bius_inversion_formula" rel="noreferrer">something very beautiful</a> is true, but don't look at it just yet, and you'll probably never need it. :-)]</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload