wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> 'Holey' set reciprocal sum never an integer
        
(Message started by: Aryabhatta on Dec 21^st, 2007, 12:02pm)

Title: 'Holey' set reciprocal sum never an integer
Post by Aryabhatta on Dec 21^st, 2007, 12:02pm

From the set of n >= 4 consecutive integers {1, 2,3, ..., n} you remove less than log sqrt(n)/ log 2 integers.

Suppose the numbers left form the set {a₁, ..., a_m}

Prove/Disprove:

1/a₁ + 1/a₂ + ... + 1/a_m is never an integer.

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Hippo on Dec 25^th, 2007, 12:44pm

I would try to prove there is a prime > n/2 in the set.
The sum times the prime gives 1 mod that prime. Therefore the sum is not integer. ... Ooops not as easy ...

Hmm this would probably fail, but at least all such numbers are excluded from the set.

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Joe Fendel on Dec 25^th, 2007, 7:36pm

1/1 is an integer, and so is 1/2 + 1/3 + 1/6. Are there any other examples of sums of reciprocals of distinct positive integers that totals an integer? ???

Title: Re: 'Holey' set reciprocal sum never an integer
Post by towr on Dec 26^th, 2007, 2:22am

on 12/25/07 at 19:36:42, Joe Fendel wrote:

1/1 is an integer, and so is 1/2 + 1/3 + 1/6. Are there any other examples of sums of reciprocals of distinct positive integers that totals an integer? ???

Of course, e.g. 1/2 + 1/4 + 1/7 + 1/14 + 1/28 and
1/2 + 1/4 + 1/8 + 1/16 + 1/31 + 1/62 + 1/124 + 1/248 + 1/496
[hide]6, 28 and 496 are perfect numbers[/hide]

And you can find other sets than these, e.g.
1/3 + 1/6 + 1/7 + 1/8 + 1/14 + 1/16 + 1/28 +1/31 + 1/62 + 1/124 + 1/248 + 1/496
Well, ok, it's a combination of the three previous ones; but still.

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Aryabhatta on Dec 26^th, 2007, 12:11pm

Addendum, instead of log sqrt(n)/ log 2 I think even log n/log 2 - 1 will work (or maybe -2).

Perhaps this should have been in putnam?

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Hippo on Dec 26^th, 2007, 1:40pm

on 12/26/07 at 02:22:50, towr wrote:

I guess the base pattern would be \sum_i=0,j=0^k,1 1/(2ⁱ (2^k+1-1)^j)=2

Are there other bases?

Yes, take an odd integer ... in binary
b_kb_k-1b_k-2...b₀
Use
b_kb_k-1b_k-2...b₀000 with i zeros whenever b_i=1
Sum of reciprocals would be 1/2^k.

Can an odd number reciprocal be eliminated other way?

Yes, it can:
15=3*5 ... 1/3+1/5=8/15 ... We can use 1/(3*16), 1/(5*16) instead of 1/(15*2)...

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Pietro K.C. on Dec 28^th, 2007, 7:22pm

Is the prime number theorem overkill? Modulo proportionally small errors, the number of primes between n/2 and n is

n/ln(n) -- n/2ln(n/2) > n/2ln(n/2) >> n^1-http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/supvarepsilon.gif>> log₂(n)

in the long run. Therefore, removing less than that many numbers from the set will certainly leave primes in the interval [n/2, n]. It is easily seen that any such prime messes up the integrality property required of the sum.

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Aryabhatta on Dec 29^th, 2007, 11:39am

on 12/28/07 at 19:22:59, Pietro K.C. wrote:

Is the prime number theorem overkill?

Err.. maybe. But the fact that there is at least one prime in [k/2,k] is enough I think.

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Pietro K.C. on Dec 30^th, 2007, 10:05pm

Quote:

But the fact that there is at least one prime in [k/2,k] is enough I think.

I'm not sure I follow you. Since there's a prime between 2^k and 2^k+1 for each k, there are at least floor(log₂(n)) primes smaller than n. Therefore, the amount of numbers you allow us to remove from the set can't ever remove all primes.

However, the obvious argument, that works when p is between n/2 and n (multiply the sum of inverses by n!, lo and behold, the result is not divisible by p), doesn't quite work here. We might have terms like 1/p + 1/2p, etc.

It seems we need something stronger than Bertrand's postulate, perhaps weaker than the prime number theorem, establishing the existence of at least log₂(n) primes between n/2 and n, for that kind of approach to work.

Do you have a cleverer proof in mind?

Title: Re: 'Holey' set reciprocal sum never an integer
Post by Aryabhatta on Dec 31^st, 2007, 12:20pm

Consider the "standard" proof (found in most textbooks/web) involving a power of 2 of the fact that 1 + 1/2 + 1/3 + ... + 1/n is never an integer.

A similar proof works here too, I think.