I recently read the following: (Backdrop- the author had already defined p(n) to be the number of partitions of n.) NOTE- I use ki where the actual quote uses ki. Looks better in html, though I am sure a better htmler than I could handle this.
For a positive integer n let d(n) be the sum of the divisors of n. For exampleThey are assuming factoring is easy. Or perhaps they are assuming you are given the number already factored. There are no comments on what easy to compute might really mean, though they seem to think that having a simple explicit formula implies easy to compute.
Unlike the numbers p(n), the numbers d(n) are easy to compute. There is a simple explicit formula for them. Namely, if n=2k23k3 ... pkp then
- d(4) = 1 + 2 + 4 = 7
- d(1000)=1+2+4+5+8+10+20+25+40+50+100+125+200+250+500+1000 = 2340
To be fair, this book was written a while back before people in math really took these notions seriously. The book is Mathematical Omnibus: Thirty Lectures on Classic Mathematics by Fuchs and Tabachnikov. Copyright 2007.
Disclosure: I got my copy for free in my capacity as SIGACT NEWS book review editor.