Summing series
Moderator: Michael Wallace
-
- Post-apocalypse
- Posts: 13279
- Joined: Mon Jan 21, 2008 10:37 pm
Summing series
This isn't really a puzzle that I'm setting, but something I want to know the answer to. I'm not sure if this is something that's actually quite trivial and I'm just being thick. Is there a simple formula for:
1 + 1/2 + 1/3 + 1/4 +...+ 1/n
also
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2n-1)?
Thanks in advance.
1 + 1/2 + 1/3 + 1/4 +...+ 1/n
also
1 + 1/3 + 1/5 + 1/7 + ... + 1/(2n-1)?
Thanks in advance.
-
- Post-apocalypse
- Posts: 13279
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Summing series
http://mathworld.wolfram.com/HarmonicNumber.html
Edit:
Euler–Mascheroni constant
http://en.wikipedia.org/wiki/Euler%E2%8 ... i_constant
Piece of piss.A harmonic number can be expressed analytically as
where is the Euler-Mascheroni constant and is the digamma function.
Edit:
Euler–Mascheroni constant
http://en.wikipedia.org/wiki/Euler%E2%8 ... i_constant
That bit's OK. It's the digamma function that looks an arse. And this is just for 1 + 1/2 etc. I wouldn't know where to start with the other one.Its numerical value to 50 decimal places is
0.57721 56649 01532 86060 65120 90082 40243 10421 59335 93992
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Summing series
gamma + ln(n) is a pretty good approximation (in the limit).Gavin Chipper wrote: That bit's OK. It's the digamma function that looks an arse. And this is just for 1 + 1/2 etc. I wouldn't know where to start with the other one.
For the other one you can use the fact that
1 + 1/3 + 1/5 + ... + 1/n
= (1 + 1/2 + ... + 1/n) - (1/2 + 1/4 + 1/6 + ... + 1/(n-1))
= H_n - (1/2) (1 + 1/2 + 1/3 + ... + 1/((n-1)/2) )
= H_n - (1/2) * H_{(n-1)/2}
(I just did that so I might've screwed up one of the limits but you get the idea.)
-
- Kiloposter
- Posts: 1123
- Joined: Sat Mar 01, 2008 3:15 pm
- Location: Harlow
Re: Summing series
That reminds me of another problem I've been thinking about recently (stimulated by one of Professor Stewart's Hoard of Mathematical Treasures.
How do you find an efficient way of expressing integers n>1 as Egyptian Fractions?
The greedy algorithm becomes increasingly inefficient as it pulls in more and more primes with increasing n, whilst better solutions are given by the known multiperfect numbers, which are clearly not the best, though the factors of abundant numbers look to be the most promising line of attack.
The best for n=2 I've got so far is {2,3,4,5,6,8,9,10,12,15,18} - with the obvious notation, and maximizing the smallest fraction. I haven't found one with fewer terms, even by going down to smaller fractions
How do you find an efficient way of expressing integers n>1 as Egyptian Fractions?
The greedy algorithm becomes increasingly inefficient as it pulls in more and more primes with increasing n, whilst better solutions are given by the known multiperfect numbers, which are clearly not the best, though the factors of abundant numbers look to be the most promising line of attack.
The best for n=2 I've got so far is {2,3,4,5,6,8,9,10,12,15,18} - with the obvious notation, and maximizing the smallest fraction. I haven't found one with fewer terms, even by going down to smaller fractions
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Summing series
Given that the harmonic series diverges incredibly slowly, you shouldn't expect to be able to find compact solutions. Not very helpful, I know. Is it even possible to solve for every n? (Edit: Yes.)Peter Mabey wrote:That reminds me of another problem I've been thinking about recently (stimulated by one of Professor Stewart's Hoard of Mathematical Treasures.
How do you find an efficient way of expressing integers n>1 as Egyptian Fractions?
The greedy algorithm becomes increasingly inefficient as it pulls in more and more primes with increasing n, whilst better solutions are given by the known multiperfect numbers, which are clearly not the best, though the factors of abundant numbers look to be the most promising line of attack.
The best for n=2 I've got so far is {2,3,4,5,6,8,9,10,12,15,18} - with the obvious notation, and maximizing the smallest fraction. I haven't found one with fewer terms, even by going down to smaller fractions
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Summing series
I know this isn't exactly your problem, but I found this on Mathworld: "No algorithm is known for producing unit fraction representations having either a minimum number of terms or smallest possible denominator" which suggests that your algorithm isn't known either.Peter Mabey wrote:That reminds me of another problem I've been thinking about recently (stimulated by one of Professor Stewart's Hoard of Mathematical Treasures.
How do you find an efficient way of expressing integers n>1 as Egyptian Fractions?
-
- Post-apocalypse
- Posts: 13279
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Summing series
By the way, the reason I asked the original question was that I've been comparing the Sainte-Laguë and D'Hondt systems of allocating seats in elections. As far as I understand, they both give proportional representation when a party's proportion of the vote matches exactly with a whole number of seats. I was hoping to get the formula for fractional seats and "break" one of the systems. There's probably a much easier way though.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Summing series
You're welcome.Gavin Chipper wrote:By the way, the reason I asked the original question was that I've been comparing the Sainte-Laguë and D'Hondt systems of allocating seats in elections. As far as I understand, they both give proportional representation when a party's proportion of the vote matches exactly with a whole number of seats. I was hoping to get the formula for fractional seats and "break" one of the systems. There's probably a much easier way though.
-
- Post-apocalypse
- Posts: 13279
- Joined: Mon Jan 21, 2008 10:37 pm
Re: Summing series
Haha - I was going to say thank you a few hours ago but decided to do so next time I posted. Then forgot. Thanks!Charlie Reams wrote:You're welcome.Gavin Chipper wrote:By the way, the reason I asked the original question was that I've been comparing the Sainte-Laguë and D'Hondt systems of allocating seats in elections. As far as I understand, they both give proportional representation when a party's proportion of the vote matches exactly with a whole number of seats. I was hoping to get the formula for fractional seats and "break" one of the systems. There's probably a much easier way though.
Edit - actually
Gavin Chipper wrote:Thanks in advance.
- Charlie Reams
- Site Admin
- Posts: 9494
- Joined: Fri Jan 11, 2008 2:33 pm
- Location: Cambridge
- Contact:
Re: Summing series
Haha. Dick. Thanks accepted (both times).Gavin Chipper wrote:Edit - actuallyGavin Chipper wrote:Thanks in advance.
- Michael Wallace
- Racoonteur
- Posts: 5458
- Joined: Mon Jan 21, 2008 5:01 am
- Location: London
Re: Summing series
Christ, get a room you homos.Charlie Reams wrote:Haha. Dick. Thanks accepted (both times).Gavin Chipper wrote:Edit - actuallyGavin Chipper wrote:Thanks in advance.
-
- Post-apocalypse
- Posts: 13279
- Joined: Mon Jan 21, 2008 10:37 pm