Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Happy 500th!

If you've never tried Project Euler, it's a great way to learn new mathematical concepts, sequences, dynamic programming and other algorithms.

https://projecteuler.net/problem=368 was one of my favorites, because it involved turning an algorithm described in a paper into code.

I don't consider this a spoiler for problem #500, but if you're counting the number of divisors, you'll need this function: http://oeis.org/wiki/Number_of_divisors_function#Formulae_fo...

As an example, 120 = 2^3 * 3^1 * 5^1

number of divisors of 120 => (3+1)(1+1)(1+1)

Even if you don't solve it, exploring the problem is a fun afternoon for a person with a computer.



I love the way the harmonic series seems to juuuuuuust baaaaarely diverge....


One of the things that's freaky to me is that the harmonic series up to n terms is proportional to log(n)...

but the sum of the reciprocals of the primes is roughly proportional to log(log(n)). That's a crazy slow divergence.


For even more crazy, consider the following series:

H(n) = 1/1 + 1/2 + ... + 1/n

H_2(n) = 1 / (H(1)) + 1 / (2 H(2)) + 1 / (3 H(3)) + ... + 1 / (n H(n))

H_3(n) = 1 / (H(1) H_2(1)) + 1 / (2 H(2) H_2(2)) + 1 / (3 H(3) H_2(3)) + ... + 1 / (n H(n) H_2(n))

...

H_k(n) = 1 / (H(1) H_2(1) ... H_{k-1}(1)) + 1 / (2 H(2) H_2(2) ... H_{k-1}(2)) + ... + 1 / (n H(n) H_2(n) ... H_{k-1}(n))

The series H_k(n) diverges roughly proportional to log(log(... k logs ... (log(n)) ...)).


The n'th prime looks a bit like n log n. (This is basically the same fact as the "prime number theorem": the number of primes up to n is roughly n/log(n).)

We have:

sum (up to n) of 1/x ~= log n [harmonic series]

sum (up to n) of 1/(x log x) ~= log log n [reciprocals of primes, roughly]

sum (up to n) of 1/(x log x log log x) ~= log log log n

and so on. All these series diverge, but slower and slower and slower. And clearly these series "only just" diverge. In fact, iIf you take, e.g.,

sum of 1/(x log x log log x (log log log x)^1.1)

then it converges. If you have just the right kind of warped mind, the question that will immediately occur to you on contemplating this is: what if you define L(x) := x log x log log x log log log x ... continuing the product up to, but excluding, the first factor that's < 1, and ask about the sum of 1/L(x)?

Answer: The series diverges really slowly. The points at which L(x) starts to use one extra logarithm are e, e^e, e^e^e, e^e^e^e, etc. The sums between each adjacent pair of these are comparable in size. So the sum up to n is roughly the number of times you need to take logs, starting with n, before you get down to 1.

[EDITED to add: The first bit of the above is closely related to cperciva's comment that's a sibling of this one.]




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: