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

        riddles >> easy >> Sum-Product Numbers
        
(Message started by: Sir Col on Jan 7th, 2005, 9:08am)
Title: Sum-Product Numbers
Post by Sir Col on Jan 7th, 2005, 9:08am
We shall define a sum-product number to be a natural number, N, for which there exists a set of numbers: S = {a1,a2,...,ak} [in] [bbn] and k>1, such that N = a1+a2+...+ak = a1a2...ak.

For example, 8 = 1+1+2+4 = 1*1*2*4.

(1) Prove that N is a sum-product number iff it is composite.

Let fj represent any natural number greater than or equal to 2.

(2) Given that N = f1f2f3, prove that there exists at least two different sets for which N is a sum-product number.

(3) Prove that f1+f2+...+fk [le] f1f2...fk.

(4) What can you deduce about the number of solution sets for N in general?

[e]Edited to qualify that S must contain at least two elements; thanks, Grimbal.[/e]
Title: Re: Sum-Product Numbers
Post by Grimbal on Jan 7th, 2005, 9:25am

on 01/07/05 at 09:08:12, Sir Col wrote:
We shall define a sum-product number to be a natural number, N, for which there exists a set of numbers: S = {a1,a2,...,ak} [in] [bbn], such that N = a1+a2+...+ak = a1a2...ak.

For example, 8 = 1+1+2+4 = 1*1*2*4.

Uh... Mister, do you accept k=1?  please?
Title: Re: Sum-Product Numbers
Post by JocK on Jan 7th, 2005, 3:07pm

on 01/07/05 at 09:08:12, Sir Col wrote:
(1) Prove that N is a sum-product number iff it is composite..

:: [hide]If N is composite, one can write N = A*B with A [ge] 2 and B [ge] 2.
For A [ge] 2 and B [ge] 2 we have A*B [ge] A + B.

So: one can write N = A*B = A + B + K with K a non-negative integer.

Hence, one can represent N as:

N = A*B*1*1* .. *1 = A+B+1+1+ .. +1   (with K 1's)
[/hide] ::


on 01/07/05 at 09:08:12, Sir Col wrote:
Let fj represent any natural number greater than or equal to 2.

(2) Given that N = f1f2f3, prove that there exists at least two different sets for which N is a sum-product number.


:: [hide]Follows from above taking into account that:

N = f1f2f3 > f1 + f2 + f3

N = f1f2*3 > f1 + f2*3 with f2*3 = f2f3
[/hide] ::


on 01/07/05 at 09:08:12, Sir Col wrote:
(3) Prove that f1+f2+...+fk [le] f1f2...fk.


Isn't that trivial? (I happily used it above..  :-/ )

::[hide] Just write out (2+x1)*(2+x2)* ...  *(2+xk) and use the fact that all x's are non-negative. [/hide] ::


on 01/07/05 at 09:08:12, Sir Col wrote:
(4) What can you deduce about the number of solution sets for N in general?


Leave this one for another riddler... ;)
Title: Re: Sum-Product Numbers
Post by Sir Col on Jan 7th, 2005, 5:47pm
Certainly proving (1) and (2) with (3) is straight-forward, but I'm not sure that it is trivial, which is why I asked it. Maybe I'm missing something in your method, but I don't quite follow how that proves it?
Title: Re: Sum-Product Numbers
Post by TenaliRaman on Jan 8th, 2005, 1:48am
3>::[hide]
Induction Basis :
f1 <= f1
f1 + f2 <= f1f2
which follows from f1<=f2(f1-1)

Induction Hypothesis :
f1+f2+...+fk<=f1....fk .. (*)

Add fk+1 to both sides of (*),
f1+f2+...+fk+1
<=f1f2..fk + fk+1
The RHS is a sum of two numbers which is less than their products and hence proved.
[/hide]::

4>an attempt
::[hide]
Let N = p1^e1*p2^e2*...*pn^en
It can be shown that max #S = e1+e2+..+en+K
(where K is the number of 1's required to make N the sum product number)
Then number of solution set would be the Bell Number.
I wonder if this was the expected answer.  :-/
[/hide]::

-- AI
Title: Re: Sum-Product Numbers
Post by THUDandBLUNDER on Jan 8th, 2005, 10:25am

Quote:
Let N = p1^e1*p2^e2*...*pn^en
It can be shown that max #S = e1+e2+..+en+K  
(where K is the number of 1's required to make N the sum product number)
Then number of solution set would be the Bell Number.
I wonder if this was the expected answer.
 
TenaliRaman, perhaps you mean something like this:

If N = a1 + a2 + .......+ aK = a1a2......aK
then we need
N = (1K-E) * (p1)e1 * (p2)e2 * ....... * (pn)en
and
N = e1p1 + e2p2 + ....... + enpn + (K - E), where the last term is all 1's
and
pi is prime, ei is a positive integer
and
E = e1 + e2 + ....... + en

I will leave it for you to finish off.  ;)
Title: Re: Sum-Product Numbers
Post by THUDandBLUNDER on Jan 8th, 2005, 2:36pm

on 01/07/05 at 09:08:12, Sir Col wrote:
We shall define a sum-product number to be a natural number, N, for which there exists a set of numbers: S = {a1,a2,...,ak} [in] [bbn] and k>1, such that N = a1+a2+...+ak = a1a2...ak.

For what values of N is there a solution if
1) ai [in] [smiley=bfcz.gif]?
and
2) k = N
Title: Re: Sum-Product Numbers
Post by Sir Col on Jan 8th, 2005, 3:45pm
I wondered about 1) when I first looked at Jock's 2005 problem: what if we were looking for a set of 2005 integers (positive and negative) that make a sum-product number.

::[hide]
Clearly for ai>0, letting N=k means that the sum of the k elements is equal to N. This can only happen if each element were equal to 1, but then the product would be 1.

So if N=k it is necessary that some of ai are negative. In which case any value of N (prime or composite) is a sum-product number.

As N=-1*-N, and the sum of these factors is -(N+1), we need to add 2N+1 ones to make N. For example, -1+-3+(7 ones)=3; that is, 3=-1+-3+1+1+1+1+1+1+1=-1*-3*1*1*1*1*1*1*1.

However, in applying the extra restriction N=k, the above method requires 2 elements, -N and -1, plus 2N+1 ones; that is, k=2N+3 elements.

But we need not have just two factors. In fact, to give three examples, solutions exist for N=5=-1*-1*5=-1-1+5+1+1 [which is the smallest N=k solution], N=12=-1*-2*6*1*..*1=-1-2+6+(9 ones), and N=28=-2*-2*7*1*...*1=-2-2+7+(25 ones).

I've not been able to generalise this yet.
[/hide]::
Title: Re: Sum-Product Numbers
Post by Sir Col on Jan 8th, 2005, 4:17pm
Okay, I've managed to form some generalisations...

::[hide]
All numbers of the form a(a+4) solve N=k.

Proof:
-1*-a*b=ab
-1-a+b+(ab+a-b+1)=ab, where ab+a-b+1 is the number of ones.

So the sum contains ab+a-b+4 elements.

Solving ab+a-b+4=ab, b=a+4, so N=ab=a(a+4) are sum-product numbers with N elements.

For example, N=3*(3+4)=21=-1*-3*7*1*...*1=-1-3+7+(18 ones) [21 elements].

We can take this one step further:
N=-a*-b*c=abc
-a-b+c+(abc+a+b-c)=abc

That is, abc+a+b-c+3 elements.

Solving abc+a+b-c+3=abc, c=a+b+3.

Hence all number of the form ab(a+b+3) solve N=k (note that the previous result, N=a(a+4), is a special case where b=1).

For example, a=2, b=3, c=8, and N=48=-2*-3*8*1*...*1=-2-3+8+(45 ones) [48 elements].
[/hide]::
Title: Re: Sum-Product Numbers
Post by Sir Col on Jan 8th, 2005, 4:45pm
It's me again! I've made yet another generalisation...

::[hide]
All number of the form N=4a+1 are solutions to N=k:

In the set {-1,-1,...,-1,4a+1,1,1,...1,} there are 2a lots of -1 and 2a lots of 1, making 4a+1 elements.

Clearly the sum, -2a+(4a+1)+2a=4a+1, and the product of an even number of -1's will be 1, hence the product is also 4a+1.


Which means, in response to my own unanswered and niggling question from Jock's 2005 integer sum problem, the mininum sum-product number made up of a set of 2005 integers (positive and negative), is 2005=(1002 lots of -1)+2005+(1002 lots of 1) [2005 elements].
[/hide]::
Title: Re: Sum-Product Numbers
Post by JocK on Jan 9th, 2005, 10:46am

on 01/08/05 at 16:45:43, Sir Col wrote:
.. the mininum sum-product number made up of a set of 2005 integers (positive and negative), is 2005=(1002 lots of -1)+2005+(1002 lots of 1) [2005 elements].


Ehhh...?  :o What about:

1  =  1003[times]1 + 1002[times](-1) = 11003 [times] (-1)1002
Title: Re: Sum-Product Numbers
Post by Sir Col on Jan 9th, 2005, 12:37pm
Good point!  :-[
Title: Re: Sum-Product Numbers
Post by rmsgrey on Jan 10th, 2005, 7:09pm
2005 0's?
Title: Re: Sum-Product Numbers
Post by JocK on Jan 11th, 2005, 9:18am

on 01/10/05 at 19:09:26, rmsgrey wrote:
2005 0's?


As a minimum...? Mwahhh...:

(-2005) * (-2) * (-1)2003 = (-2005) + (-2) + 2003 * (-1) = -4010

;D
Title: Re: Sum-Product Numbers
Post by towr on Jan 11th, 2005, 12:42pm

Quote:
We shall define a sum-product number to be a natural number
-4010 most certainly isn't a natural number, and under Sir Col's definitions, neither is 0 if I recall..
Title: Re: Sum-Product Numbers
Post by THUDandBLUNDER on Jan 11th, 2005, 1:32pm

on 01/11/05 at 12:42:17, towr wrote:
-4010 most certainly isn't a natural number, and under Sir Col's definitions, neither is 0 if I recall..

But he later speculated:


on 01/08/05 at 15:45:30, Sir Col wrote:
I wondered about 1) when I first looked at Jock's 2005 problem: what if we were looking for a set of 2005 integers (positive and negative) that make a sum-product number.
Title: Re: Sum-Product Numbers
Post by towr on Jan 11th, 2005, 1:38pm
Yes, integer factors/terms, but still a (natural number) sum-product number
Title: Re: Sum-Product Numbers
Post by rmsgrey on Jan 12th, 2005, 8:03am

on 01/11/05 at 09:18:56, JocK wrote:
As a minimum...? Mwahhh...:

Minimum magnitude...


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board