wu :: forums - Print Page


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

        riddles >> hard >> Integers problem
        
(Message started by: BenVitale on Nov 13^th, 2008, 4:34pm)

Title: Integers problem
Post by BenVitale on Nov 13^th, 2008, 4:34pm

I'm interested in integers that have the sum of positive integers whose reciprocals sum to 1.

1, 1/1=1
2=1+1, 1/1 + 1/1 =/= 1
3=2+1, 1/2 + 1/1 =/= 1
4=2+2, 1/2 + 1/2 = 1,
5=2+3, 1/2 + 1/3 =/= 1
6=4+2,6=3+3, 6=5+1, the sums of the reciprocals are not equal to 1.
7=3+4, 7=2+5, 7=1+6, idem
8=4+4, 8=3+5, 8=2+6, idem
9=3+3+3, 1/3 + 1/3 + 1/3 = 1
10=5+5, 10=6+4, 10=7+3, 10=8+2, 10=9+1
10=4+4+2, 1/4 + 1/4 + 1/2 = 1
11=2+3+6, 1/2 + 1/3 + 1/6 = 1.

In this short list, 4, 9, 11, do fit. However with 4 and 9, the sums are not of distinct integers, since
4=2+2, 1/2 + 1/2 = 1,
9=3+3+3, 1/3 + 1/3 + 1/3 = 1
But, 11, is the sum of distinct integers whose whose reciprocals sum to 1.
I imagine there would numbers that could have either feature, i.e. sum of distinct integers, or are sum of not distinct integers.
Let's take 64, for example
We could write: 64 = 8+8+8+8+8+8+8+8
64 is then the sum of not distinct integers.
Or we could write:
64 = 2 + 4 + 8 + 10 + 40, thus making 64 sum of distinct integers, and 1/2 + 1/4 + 1/8 + 1/10 + 1/40 = 1.

So an integer can be partitioned in more than one way. In one way it could be sum of distinct integers, and in another way, sum of NOT-distinct integers.

Is there a way to find them-- distinct and Not-distinct? If we can find one, can we predict the next one? Any relations to Egyptian fractions?

Title: Re: Integers problem
Post by Eigenray on Nov 13^th, 2008, 5:41pm

What you call 'distinct' are called strictly [link=http://mathworld.wolfram.com/EgyptianNumber.html]Egyptian numbers[/link]. Not-necessarily-distinct are just Egyptian numbers. I'm not sure what not-distinct would be called.

All but finitely many n are Egyptian, and all but finitely many are 'not-distinct'. I expect all but finitely many are 'distinct' (strictly Egyptian) as well.

Hint: If n is Egyptian, so are ...?

Title: Re: Integers problem
Post by BenVitale on Nov 13^th, 2008, 7:40pm

on 11/13/08 at 17:41:42, Eigenray wrote:

....

Hint: If n is Egyptian, so are ...?

If n is strict-sense Egyptian we can partition m = x1+x2+...+xk into distinct positive integers xi such that Sum_{i=1..k} 1/xi = 1.

Thanks

Title: Re: Integers problem
Post by Michael Dagg on Nov 16^th, 2008, 8:09am

Your question has a classical application: the classification of
platonic solids requires knowing the solutions to 1/x + 1/y + 1/z = 1.
More generally there is a theory of "groups generated by reflections",
having a presentation as abstract groups in the form
< x1, x2, ... | (x_i)^2 = 1 and (x_i x_j)^{m_ij} = 1 >
The main fact is something like: these groups act in a natural way as
isometries on Euclidean space iff the sum 1/(m_ij) = 1 ;when the
sum is > 1, the group acts on a sphere (and is finite)
and when the sum is < 1, the group acts on hyperbolic space.

Your particular question about adding the denominators seems a little
contrived to me but it's a fine way to sort all the possible solutions.
To my way of thinking that will just be an addendum to the attempt
to find all possible solutions. And as for that quest:

> Is there a way to find them -- distinct and not-distinct?

I guess I would do it recursively. Here is a Maple procedure that
finds all N-tuples of integers a_i >= M for which sum 1/a_i = target .
(Note that the smallest of the N integers must be at least 1/target
but no more than N/target .)

getall:=proc(N, M, targ)
local x, ANS, BNS, i:
option remember:
#Maple remembers its outputs to avoid re-computation -- runs fast, uses space.
if targ <= 0 then [] else
if N=1 then x:=1/targ: if type(x, integer) and x>=M then [x] else [] fi: else
ANS:=[]:
for i from max(M, ceil(1/targ)) to floor(N/targ) do
BNS:=getall(N-1, max(M,i+1), targ-1/i):
ANS:=[op(ANS), seq([i,op(b)],b=BNS)]:
od:
fi:
fi:
end:

Change the "i+1" to "i" if repetitions are OK.

Here's how you use this in Maple:

S:=[]: #Elements of S are N-tuples, preceded by their sum-of-denominators
for N from 1 to 7 do
T:=getall(N,1,1):
S:=[op(S),seq([add(a,a=s),op(s)],s=T)]:
lprint(N,nops(S),{seq(s[1],s=S)}):
od:

In 2 seconds, Maple finds all sums of at most 6 summands, but the
7-term ones really slow it down. (I didn't wait for completion.)
There are 2400 such sums with at most 6 terms; the denominators
sum to these values:

1, 11, 24, 30, 31, 32, 37, 38, 43, 45, 50, 52, 53, 54, 55, 57, 59, 60,
61, 62, 64, 65, 66, 67, 69, 71, 74, 75, 76, 78, 79, 80, 81, 82, 83, 84,
85, 86, 87, 88, 89, 92, 93, 95, 96, 97, 99, 100, ..., 3265304

A 7-term nonrepeating sequence obviously has to have denominators
sum to at least 2+3+...+8 = 35, and I'm sure there's none that have
a sum anywhere near that small. So I wouldn't expect too many additional
small entries in the list above.

If you allow repeating denominators, the program equally fast gets
through the 6-term sequences; now there are 3628 of them, and their sums are
1, 4, 9, 10, 11, 16, 17, 18, 20, 22, 24, 25, ...
(then every integer through 298 is represented, except 250!)
..., 248, 249, 251, 252, ..., 297, 298, 301, ..., 3265304 .
I guess from these data I might conjecture that every integer greater
than 23 can be written as the sum of integers whose reciprocals sum to 1.
That would be cute -- 23 is also the exception to some other number theory
problems. (For example -- Waring's Problem -- every integer is a sum of
9 cubes; 8 is enough for every integer except 23 and 239.)

I don't know anything about a general theory you can use here.
"Egyptian fractions" would be a keyword; that's all I can suggest.

Title: Re: Integers problem
Post by BenVitale on Nov 17^th, 2008, 4:37pm

Thanks Michael.

I showed this problem to one of my friends, and he gave me a link where this very same problem is discussed at this link.

http://perplexus.info/show.php?pid=2798&op=sol

Wow, i didn't know about it. I was just fooling around with the Egyptian numbers

Quote:

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.