Harmonic Series

Post a reply


This question is a means of preventing automated form submissions by spambots.
Smilies
:D :) :( :o :shock: :? 8) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :?: :idea: :| (o~o) :geek: :[] :geek2: :][>:=~+:

BBCode is ON
[img] is ON
[flash] is OFF
[url] is ON
Smilies are ON

Topic review
   

Expand view Topic review: Harmonic Series

Re: Harmonic Series

by MBenesi » Tue Jul 07, 2015 3:27 am

I don't get it.

1/1 + 1/10 + 1/11 + 1/100 + 1/101...


beep.

Re: Harmonic Series

by rpenner » Fri Jun 26, 2015 5:16 pm

Thank you, NameAlreadyTaken2 and Gibborim

The sum over reciprocals of all positive integers except those with a digit of b-1 when expressed in base b, converges.

I don't think Mathematica can prove that
Sum[ If[MemberQ[IntegerDigits[n, b], b-1], 1/n, 0 ], {n, 1, Infinity}]
= Sum[1/FromDigits[IntegerDigits[n, b-1], b], {n, 1, Infinity}]
is an equality or that it converges.

But I think:
FromDigits[IntegerDigits[n, b-1], b]
= n + Sum[ b^k Floor[ n / (b-1)^(1+k) ], {k, 0, Infinity} ]
= n + Sum[ b^k Floor[ n / (b-1)^(1+k) ], {k, 0, Floor[ Log[n] / Log[b-1] ] } ]
≈ n + n Sum[ b^k / (b-1)^(1+k) ], {k, 0, Floor[ Log[n] / Log[b-1] ] } ]
= n ( (b-1) / b )^( -1 - Floor[ Log[n] / Log[b-1] ] )
≈ n ( (b-1) / b )^( -1 - Log[n] / Log[b-1] )
= b/(b-1) * n^(Log/Log[b-1])

which produces (b-1) Zeta[ Log/Log[b-1] ] / b as an estimate ( lower bound ) of the limit.

NameAlreadyTaken2 's estimate is Zeta[1 - Log[(b-1)/b]/Log] = Zeta[ 2 - Log[b-1] / Log ] and when 3 < b < 10, this estimate is between 7/4 and 13/4 larger than my lower bound

(2/3) Zeta[ Log[3] / Log[2] ] ≈ 1.55
Zeta[ 2 - Log[2] / Log[3] ] ≈ 3.31
Sum[1/FromDigits[IntegerDigits[n, 2], 3], {n, 1, 10}] ≈ 2.06
Sum[1/FromDigits[IntegerDigits[n, 2], 3], {n, 1, 100}] ≈ 2.31
Sum[1/FromDigits[IntegerDigits[n, 2], 3], {n, 1, 1000}] ≈ 2.64
Sum[1/FromDigits[IntegerDigits[n, 2], 3], {n, 1, 10000}] ≈ 2.67
(9/10) Zeta[ Log[10] / Log[9] ] ≈ 19.29
Zeta[ 2 - Log[9] / Log[10] ] ≈ 22.43
Sum[1/FromDigits[IntegerDigits[n, 9], 10], {n, 1, 10}] ≈ 2.91
Sum[1/FromDigits[IntegerDigits[n, 9], 10], {n, 1, 100}] ≈ 4.95
Sum[1/FromDigits[IntegerDigits[n, 9], 10], {n, 1, 1000}] ≈ 6.83
Sum[1/FromDigits[IntegerDigits[n, 9], 10], {n, 1, 10000}] ≈ 8.51

Re: Harmonic Series

by NameAlreadyTaken2 » Thu Jun 25, 2015 6:05 am

Gibborim already gave a proof of why it converges, but I thought I'd give more insight into how fast it converges, and "why" it should intuitively work. [I wrote this while really tired, so don't hesitate to correct anything I messed up]

---

Out of the 1-digit numbers, 9 out of 10 do not contain the number "9" (and that number is obviously "9" itself.)
Out of the 2-digit numbers, 81 of 100 do not have "9" (09, 19, 29, 39, ... 89, 99. Also 90, 91, ... 99. But 99 is counted twice, so it's 19, not 20.)
Out of the 3-digit numbers, 729 of 1000 have "9" by similar logic (009, 019, ... 099, 109, 119, ... 199, 209, ... 299, ... 909, ... 999)

You might notice this pattern: out of the n-digit numbers, 9^n out of 10^n do not have any 9s in them. Every time you add another digit, you lose another 10% of your numbers.

Also, as a rough estimate, adding another digit to a number is "basically" the same as multiplying it by 10. For example, 2753 is roughly ten times as big as 312, and 312 is about 10 times as big as 23.

---

To summarize: Every time you add a digit (or, roughly speaking, every time you multiply by 10), you lose 10% of your terms.

This means we have a polynomial. To see what I mean, look at x^2. If you plug in (2x)^2, you get 4*(x^2). In words, if you multiply x by 2, x^2 goes up by 4.
Similarly, if you do (2x)^-1, you get 0.5 * (x^-1).

We can probably assume that our original problem will also give us something like x^n, since it acts the same way. Whenever we plug in (10*x), we only get 90% of what we would normally expect.
In equation form: (10x)^n = 0.9*(x^n).

Now we just have to solve for n. Divide by (x^n) on both sides to get:
10^n = 0.9
n = log10(0.9) = -0.0457.

All of this basically means that, if you remove 10% of the numbers from every order of magnitude, you end up with a function that grows like x^-.0457. Let's look at a couple examples to clear up what I mean:
10^-.0457 = .9
100^-.0457 = .81
1000^-.0457 = .729
Well, look at that! These are basically the same numbers we saw earlier, except in decimal form. As x (our original denominators) gets bigger, we end up throwing more and more terms out. And, in particular, the numbers start "thinning out" at a rate of x^-.0457.

---

As we know, the harmonic sequence grows like x^-1. When you throw out all the 9's, it's kind of like multiplying the xth term by x^-.0457: that's (roughly) the probability that the number will be free of 9s, and therefore will actually go into the sum.

So now we have a new sequence that grows on the order of (x^-1) * (x^-.0457). Or, if you prefer, (x^-1.0457). (This is a quick estimate, but it should be reasonably close for large partial sums.) Finally, from the integral test, we know that this series will converge, and that it should grow like a rational function.

Re: Harmonic Series

by Gibborim » Thu Jun 25, 2015 5:50 am

zdog291 wrote:I'd like to point out that the sum of the reciprocal primes also diverges so removing some random numbers doesn't always cut it.

https://en.wikipedia.org/wiki/Divergenc ... the_primes
The key is that the rule for removing elements of the Harmonic series converges towards removing all new elements and that that convergence must be faster than the Harmonic series diverges.

For the 9s rule, we can see that the chance of a randomly chosen denominator of n digits being removed is: P = .1*(.9)^0 + .1*(.9)^1 + .1*(.9)^2 + ... + .1*(.9)^(n-1) This is a geometric series that converges to .1/(1-.9) = 1 as the number of digits gets large. For any specific string of digits, like "111111111111111111111111111119111111111111111111111" for example, the chance of that string of digits being present in the denominator converges to unity as the length of the denominator grows large. Now, if you removed every other term with a 9 in the denominator, the series would not converge since your probability of removing a term as the length grows converges to .5 instead of unity.

Re: Harmonic Series

by zdog291 » Wed Jun 24, 2015 9:05 pm

I'd like to point out that the sum of the reciprocal primes also diverges so removing some random numbers doesn't always cut it.

https://en.wikipedia.org/wiki/Divergenc ... the_primes

Re: Harmonic Series

by moocowpong1 » Wed Jun 24, 2015 7:51 pm

"Most large numbers have a 9 in them"

Re: Harmonic Series

by Showsni » Wed Jun 24, 2015 7:46 pm

or is there some smaller subset of terms in the harmonic series that would get the same effect?
Certainly; in fact, the more general rule that you can remove any string of digits from the denominators and it will converge holds true (there's nothing special about 9). So, for instance, you could remove only the terms with 111111111111111111111111111119111111111111111111111 in the denominators and it would converge.

Re: Harmonic Series

by reimu » Wed Jun 24, 2015 5:48 pm

deadmanjones wrote:Not specific to 9, so "Sometimes when you remove something from another thing, the original thing doesn't last as long"
I want to know if there is a subset of denominators containing 9 that would be sufficient, rather than removing all denominators with 9s. But I guess that is not a hard question, you can just add one of the denominators back. But what about infinite subsets?

Re: Harmonic Series

by deadmanjones » Wed Jun 24, 2015 5:18 pm

Not specific to 9, so "Sometimes when you remove something from another thing, the original thing doesn't last as long"

Harmonic Series

by reimu » Wed Jun 24, 2015 5:07 pm

Is removing all terms with 9 in the denominator the smallest possible amount of terms you could remove without introducing new removed terms, or is there some smaller subset of terms in the harmonic series that would get the same effect?

Top