CTK Exchange
Front Page
Movie shortcuts
Personal info
Reciprocal links
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sit's
Guest book
News sit's

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content |Store| Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Does this series ever sum to an integer?"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #637
Reading Topic #637
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
Member since May-22-05
Aug-30-05, 04:32 PM (EST)
Click to EMail mr_homm Click to send private message to mr_homm Click to view user profileClick to add this user to your buddy list  
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

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

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny