Author |
Topic: 'Holey' set reciprocal sum never an integer (Read 926 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
'Holey' set reciprocal sum never an integer
« on: Dec 21st, 2007, 12:02pm » |
 Quote  Modify
|
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 {a1, ..., am}
Prove/Disprove:
1/a1 + 1/a2 + ... + 1/am is never an integer.
|
|
 IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #1 on: Dec 25th, 2007, 12:44pm » |
Quote Modify
|
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.
|
| « Last Edit: Dec 25th, 2007, 12:52pm by Hippo » |
IP Logged |
|
|
|
Joe Fendel
Full Member
Posts: 158
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #2 on: Dec 25th, 2007, 7:36pm » |
Quote Modify
|
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? 
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #3 on: Dec 26th, 2007, 2:22am » |
Quote Modify
|
on Dec 25th, 2007, 7:36pm, 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
6, 28 and 496 are perfect numbers
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #4 on: Dec 26th, 2007, 12:11pm » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #5 on: Dec 26th, 2007, 1:40pm » |
Quote Modify
|
on Dec 26th, 2007, 2:22am, towr wrote:
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
6, 28 and 496 are perfect numbers
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. |
|
I guess the base pattern would be \sumi=0,j=0k,1 1/(2i (2k+1-1)j)=2
Are there other bases?
Yes, take an odd integer ... in binary
bkbk-1bk-2...b0
Use
bkbk-1bk-2...b0000 with i zeros whenever bi=1
Sum of reciprocals would be 1/2k.
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)...
|
| « Last Edit: Dec 27th, 2007, 1:21am by Hippo » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #6 on: Dec 28th, 2007, 7:22pm » |
Quote Modify
|
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) >> n1- >> log2(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.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #7 on: Dec 29th, 2007, 11:39am » |
Quote Modify
|
on Dec 28th, 2007, 7:22pm, 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.
|
| « Last Edit: Dec 30th, 2007, 10:33am by Aryabhatta » |
IP Logged |
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #8 on: Dec 30th, 2007, 10:05pm » |
Quote Modify
|
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 2k and 2k+1 for each k, there are at least floor(log2(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 log2(n) primes between n/2 and n, for that kind of approach to work.
Do you have a cleverer proof in mind?
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: 'Holey' set reciprocal sum never an integer
« Reply #9 on: Dec 31st, 2007, 12:20pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print