CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Terms of use Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's Recommend this site    |Store|    CTK Exchange

 Subject: "Does this series ever sum to an integer?" Previous Topic | Next Topic
 Conferences The CTK Exchange This and that Topic #637 Printer-friendly copy Email this topic to a friend Reading Topic #637
ak guest
Aug-29-05, 03:30 PM (EST)

"Does this series ever sum to an integer?"

 This is a problem I've spent many hours vainly on. If a and d are relatively prime, is 1/(a) +1/(a+d) +1/(a+2d)...+1/(a+nd) ever an integer for some n? I know erdos proved this in the 30's. Can anyone tell me how I can get hold of the proof? I've looked all over the net and books.

Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
mr_homm
Member since May-22-05
Aug-30-05, 04:32 PM (EST)    1. "RE: Does this series ever sum to an integer?"
In response to message #0

 >This is a problem I've spent many hours vainly on. If a and >d are relatively prime, is 1/(a) +1/(a+d) >+1/(a+2d)...+1/(a+nd) ever an integer for some n? I know >erdos proved this in the 30's. Can anyone tell me how I can >get hold of the proof? I've looked all over the net and >books. I'm not familiar with this problem, and I don't know where to find a proof for it, but here are some ideas I have thought of. Perhaps they will help.First, let's name the terms x_n = a+nd. Putting the first n terms over a common denominator gives the numerator as a sum of products, each of which contains all but one of the x_n's. For example 1/x_0 + 1/x_1 + 1/x_2 + 1/x_3 = (x_1 x_2 x_3 + x_0 x_2 x_3 + x_0 x_1 x_3 + x_0 x_1 x_2)/x_0 x_1 x_2 x_3.Now it is clear that all but the last term contain a factor of x_3, or in general x_n. For this fraction to represent an integer, every factor in the denominator must divide into the numerator, and since x_3 already occurs in all but the last term of the numerator, it must divide the last term also. Therefore, x_n must divide the product of all the other x_k's. The situation is symmetrical for all the other x_k's for 0 <= k <= n. Hence each x_k must divide into the product of all the others.Now suppose p is a prime factor of x_k. Then p must also occur as a factor of some other x_j, and so p|(x_k - x_j). But x_k - x_j = (k-j)d, so either p|d or p|(k-j). However, p|d is impossible, because p|x_k implies that p|x_k - kd = a, so gcd(a,d)>=p, contradicting their relative prime status. Therefore, if p|x_k, p must also divide the distance k-j to some other term of the series.This implies that for each x_k, if it has a prime factor p > k, then the series must extend to at least the n=k+p term. If new primes are encountered, when the series is extended, it may need to be extended further. If the number of terms ever "catches up" to the size of the prime factors, the series will terminate.However, this does not prove that the series does sum to an integer. It is only a necessary, not a sufficient condition. If you could show that new prime factors showed up often enough to prevent the series from terminating, this would prove the impossiblity of getting an integer from a sum of its first n terms.At this point, you need something like Bertrand's Postulate, also known as Chebyshev's Theorem. But these discuss the occurence of primes in stretches of consecutive integers, and you would need a version of this theorem for arithmetic sequences. I do not know of such a result, although you could perhaps derive it by copying Chebyshev's proof but using some of the theory of primes in arithmetic progressions (perhaps Dedekind already proved it -- I'm not too familiar with that area). By the way, the link above has a reference to a paper by Erdos in 1934, where he proves a fact that looks relevant, about the occurance of prime factors in a block of integers. This makes me suspect that that 1934 paper may be the one you want. He wrote so MANY papers though, that saying "Erdos" doesn't narrow the search much.Well, this is not very conclusive, but perhaps there are ideas here you could use. Hope this helps.--Stuart Anderson

Alert | IP Printer-friendly page | Reply | Reply With Quote | Top ak guest
Sep-01-05, 01:40 PM (EST)

2. "RE: Does this series ever sum to an integer?"
In response to message #1

 Thanks so much for your response!Those are exactly the conclusions I reached (though it took me considerably longer!) and all the things I've tried have been on the basis of proving a prime always remains in the denominator. Surely a proof must revolve around this fact. Could there be any other way?At first I thought I might be lucky and that a itself would be, or, contain that prime, which seems like a good idea at first but gets nightmarish after a while. I also determined when exactly a previous term of the sequence could be contained as a factor in a later term which gave results such as : (a+nd) is at first a factor when k=(a+nd+n) so that (a + kd)=(1+d)(a+nd) and indeed whenever it does appear the relevant term is (a+nd) by one more than a factor of d : some (1+md)Using that you can pick a term and determine whether or not it is one of those terms which have a previous term as a factor and if it is not then obviously that previous term must contain a prime factor which the aforementioned doesn't. Too late I realised this fact is useless! But anyway, the result was that, by generating a 'sequence of sequences' namely M={m: m=ka+kand+n} for the two parameters k and n, you include in that set all those values of k for which a+kd embeds a previous term within itself. Thus since a term is first a factor of a greater term at k=(a+nd+n) then if f is the finalth term we need k>f, which is n>(f-a)/(d+1) for a term which contains at least one prime factor which nothing greater than it up to the final term has, and if we pick it'so that it is not an element of M we also have that no previous term is a factor of it. Summing up, it is 'a term which has no previous term as a factor and is no factor of a later term'. This result is not only useless relative to a proof but also dubious, because it is not certain there is always such a term and indeed I think I've proved there sometimes isn't.As for copying chebyshev's proof, I can't even understand erdos's proof of that theorem which is allegedly a simplification!Thanks again for spending your time on this.P.S. I have a suspicion (when did I forget how to spell that?) that there is a way of reaching the result intuitively and totally unrigourously, euler style, by evaluating the integral of (x^a(1+x^(a+d-1))/(1-x^d))dx from 0 up to 1, turning the other cheek many times along the way. It will be a few years before I can do that. I think it involves hypergeometric functions. What do you think?

Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

 Conferences | Forums | Topics | Previous Topic | Next Topic
 Select another forum or conference Lobby The CTK Exchange (Conference)   |--Early math (Public)   |--Middle school (Public)   |--High school (Public)   |--College math (Public)   |--This and that (Public)   |--Guest book (Public) Educational Press (Conference)   |--No Child Left Behind (Public)   |--Math Wars (Public)   |--Mathematics and general education (Public) You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.  