4 ms·

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. ht

by ipsin 12y ago

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 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_for_the_number_of_divisors_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.

sdenton4 12y ago
I love the way the harmonic series seems to juuuuuuust baaaaarely diverge....
- ipsin 12y ago
  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.
  - cperciva 12y ago
    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)) ...)).
  - gjm11 12y ago
    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.]
deleted 12y ago
[deleted]

by ipsin 12y ago

sdenton4 12y ago

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

ipsin 12y ago
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.
- cperciva 12y ago
  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)) ...)).
- gjm11 12y ago
  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.]

deleted 12y ago

[deleted]