Home > Numbers
| Lucky Numbers (Posted on 2005-02-19) |
 |
Call an integer lucky if it is a sum of positive integers (not necessarily distinct) whose reciprocals sum to 1. For example, 4 and 11 are lucky: 4=2+2 and 1/2+1/2=1, and 11=2+3+6 and 1/2+1/3+1/6=1. But 2, 3, and 5 are unlucky. How many unlucky positive integers are there?
|
|
Submitted by David Shin
|
|
Rating: 3.7500 (4 votes)
|
|
|
Solution:
|
(Hide)
|
A key observation is that if n is lucky, then so is 2n+2. For if n=a+b+... is a lucky decomposition, then 1/2+1/2(1/a+1/b+...)=1 and so 2+2a+2b+...=2+2n is a lucky decomposition. Similarly, 3+6+2a+2b+... is a lucky decomposition of 2n+9. Thus it remains only to show that all integers between 24 and 55 are lucky, and to determine which integers less than 24 are unlucky.
Both tasks are easy to implement by computer: simply write a program that, given n, finds all partitions of n. This must be done slightly intelligently to reduce the search space: the program can work recursively and be made to ignore sums greater than 1.
In any case, one finds the following unlucky numbers in the range [1,23]:
{2,3,5,6,7,8,12,13,14,15,19,21,23}
This gives 13 unlucky numbers. |
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (0)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
