(no subject)
Jul. 31st, 2007 01:26 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
jackIntro
Question. Let Sn be the sum of the first n primes. Show that there is a square number strictly between any successive Sn.
Eg. (2+3+5)<16<(2+3+5+7)
First, I charged down a blind alley considering lots of things about primes. In fact, you ought to be able to see primes have nothing to do with it, it works for any similar sequence of odd numbers.
If you actually try it, you get:
Sn<x2<Sn+1
1<2<4
4<5<9
9<10<16
16<17<25
You'll notice each Sn is one more than a square number, because a square number is a sum of the first n odd numbers, and the first primes 2,3,5,7 are odd, but with an extra 1 added to the first one.
At 11 something else happens, you add an extra two to that term, and each successive term. (Which accumulate, since each following prime must be higher by at least that amount.) Notionally, this "slides up" all the Sn, but leaves square numbers between them, since if two successive Sn slide up and Sn doesn't surpass the next prime, neither does Sn+1, and if Sn does, so does Sn+1. (Since Sn+1 is increasing by 4 if Sn increases by 2, and the differences between the following squares also increases by 2.) But that's not rigorous, it depends on how much each exceeds the appropriate square.
I made a complicated sum by representing each pn+1=pn+2*dn, and associated each Sn with a square with whom the differences lockstepped, and showed an appropriate square existed between Sn and Sn+1. Then I realised that instead of starting at the bottom and adding up, I ought to start and pn and consider what the previous "primes" ought to be.
Solution
Let Sn be the sum of the first n primes, up to pn.
Sn <= 1 + (1+3+5+7+9+11+...pn)
Sn <= 1 + ((pn-1)/2)2 [By summing the series]
For S1, S2, S3 and S4 we've shown a square number between Sn and Sn+1 in the example above. But for pn>=11, we know the sum has missed out 9, so
Sn < ((pn-1)/2)2
Let (x-1)2<=Sn<x2, ie. x2 be the least square greater than Sn. We will show Sn+1>x2.
Sn+1 >= Sn+pn+1
>= Sn + pn + 2
>= (x-1)2 + 2x+1 + 2 [Since x2<((pn-1)/2)2 so x<(pn-1)/2]
>= x2 + 2 [by considering sums of odd numbers]
> x2
So Sn < x2 < Sn+1.
Extra
This works for any sum of an increasing sequence of odd numbers starting with a 1, plus a constant equal to 1 or 2. The proof is the same, except that instead of saying "We know it works for Sn, n=1,2,3,4" we need to consider Sn>=((pn-1)/2)2.
But the smallest member of the sequence 1,3,5,7,9... that might have been missed out the sum was 3, so Sn=1+((pn-1)/2)2 holds exactly, and then Sn+1>=1+((pn+1)/2)2.
Afterword
It probably wasn't worth describing this in that much detail. It wasn't that complicated. But:
* It was all written down on scrap paper anyway.
* Someone may take heart from seeing how people go down blind alleys and home in on relatively short answer.
* It's always worth writing something up neatly in case you missed something obviously wrong/interesting.
Question. Let Sn be the sum of the first n primes. Show that there is a square number strictly between any successive Sn.
Eg. (2+3+5)<16<(2+3+5+7)
First, I charged down a blind alley considering lots of things about primes. In fact, you ought to be able to see primes have nothing to do with it, it works for any similar sequence of odd numbers.
If you actually try it, you get:
Sn<x2<Sn+1
1<2<4
4<5<9
9<10<16
16<17<25
You'll notice each Sn is one more than a square number, because a square number is a sum of the first n odd numbers, and the first primes 2,3,5,7 are odd, but with an extra 1 added to the first one.
At 11 something else happens, you add an extra two to that term, and each successive term. (Which accumulate, since each following prime must be higher by at least that amount.) Notionally, this "slides up" all the Sn, but leaves square numbers between them, since if two successive Sn slide up and Sn doesn't surpass the next prime, neither does Sn+1, and if Sn does, so does Sn+1. (Since Sn+1 is increasing by 4 if Sn increases by 2, and the differences between the following squares also increases by 2.) But that's not rigorous, it depends on how much each exceeds the appropriate square.
I made a complicated sum by representing each pn+1=pn+2*dn, and associated each Sn with a square with whom the differences lockstepped, and showed an appropriate square existed between Sn and Sn+1. Then I realised that instead of starting at the bottom and adding up, I ought to start and pn and consider what the previous "primes" ought to be.
Solution
Let Sn be the sum of the first n primes, up to pn.
Sn <= 1 + (1+3+5+7+9+11+...pn)
Sn <= 1 + ((pn-1)/2)2 [By summing the series]
For S1, S2, S3 and S4 we've shown a square number between Sn and Sn+1 in the example above. But for pn>=11, we know the sum has missed out 9, so
Sn < ((pn-1)/2)2
Let (x-1)2<=Sn<x2, ie. x2 be the least square greater than Sn. We will show Sn+1>x2.
Sn+1 >= Sn+pn+1
>= Sn + pn + 2
>= (x-1)2 + 2x+1 + 2 [Since x2<((pn-1)/2)2 so x<(pn-1)/2]
>= x2 + 2 [by considering sums of odd numbers]
> x2
So Sn < x2 < Sn+1.
Extra
This works for any sum of an increasing sequence of odd numbers starting with a 1, plus a constant equal to 1 or 2. The proof is the same, except that instead of saying "We know it works for Sn, n=1,2,3,4" we need to consider Sn>=((pn-1)/2)2.
But the smallest member of the sequence 1,3,5,7,9... that might have been missed out the sum was 3, so Sn=1+((pn-1)/2)2 holds exactly, and then Sn+1>=1+((pn+1)/2)2.
Afterword
It probably wasn't worth describing this in that much detail. It wasn't that complicated. But:
* It was all written down on scrap paper anyway.
* Someone may take heart from seeing how people go down blind alleys and home in on relatively short answer.
* It's always worth writing something up neatly in case you missed something obviously wrong/interesting.