Author |
Topic: Sum-Product Numbers (Read 723 times) |
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender: 
Posts: 1825
|
 |
Sum-Product Numbers
« on: Jan 7th, 2005, 9:08am » |
 Quote  Modify
|
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]
|
| « Last Edit: Jan 7th, 2005, 10:26am by Sir Col » |
 IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Sum-Product Numbers
« Reply #1 on: Jan 7th, 2005, 9:25am » |
Quote Modify
|
on Jan 7th, 2005, 9:08am, 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?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Sum-Product Numbers
« Reply #2 on: Jan 7th, 2005, 3:07pm » |
Quote Modify
|
on Jan 7th, 2005, 9:08am, Sir Col wrote:| (1) Prove that N is a sum-product number iff it is composite.. |
|
:: 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)
::
on Jan 7th, 2005, 9:08am, 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. |
|
:: Follows from above taking into account that:
N = f1f2f3 > f1 + f2 + f3
N = f1f2*3 > f1 + f2*3 with f2*3 = f2f3
::
on Jan 7th, 2005, 9:08am, Sir Col wrote:
(3) Prove that f1+f2+...+fk [le] f1f2...fk. |
|
Isn't that trivial? (I happily used it above..  )
:: Just write out (2+x1)*(2+x2)* ... *(2+xk) and use the fact that all x's are non-negative. ::
on Jan 7th, 2005, 9:08am, Sir Col wrote:
(4) What can you deduce about the number of solution sets for N in general? |
|
Leave this one for another riddler... 
|
| « Last Edit: Jan 7th, 2005, 3:12pm by JocK » |
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum-Product Numbers
« Reply #3 on: Jan 7th, 2005, 5:47pm » |
Quote Modify
|
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?
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Sum-Product Numbers
« Reply #4 on: Jan 8th, 2005, 1:48am » |
Quote Modify
|
3>::
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.
::
4>an attempt
::
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.
::
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum-Product Numbers
« Reply #5 on: Jan 8th, 2005, 10:25am » |
Quote Modify
|
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.
|
| « Last Edit: Jan 9th, 2005, 3:09am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum-Product Numbers
« Reply #6 on: Jan 8th, 2005, 2:36pm » |
Quote Modify
|
on Jan 7th, 2005, 9:08am, 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
|
| « Last Edit: Jan 9th, 2005, 6:04am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum-Product Numbers
« Reply #7 on: Jan 8th, 2005, 3:45pm » |
Quote Modify
|
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.
::
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.
::
|
| « Last Edit: Jan 8th, 2005, 4:25pm by Sir Col » |
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum-Product Numbers
« Reply #8 on: Jan 8th, 2005, 4:17pm » |
Quote Modify
|
Okay, I've managed to form some generalisations...
::
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].
::
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
Sir Col
Uberpuzzler
impudens simia et macrologus profundus fabulae
Gender:
Posts: 1825
|
|
Re: Sum-Product Numbers
« Reply #9 on: Jan 8th, 2005, 4:45pm » |
Quote Modify
|
It's me again! I've made yet another generalisation...
::
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].
::
|
|
IP Logged |
mathschallenge.net / projecteuler.net
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Sum-Product Numbers
« Reply #10 on: Jan 9th, 2005, 10:46am » |
Quote Modify
|
on Jan 8th, 2005, 4:45pm, 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...?  What about:
1 = 1003[times]1 + 1002[times](-1) = 11003 [times] (-1)1002
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
rmsgrey
Uberpuzzler
    
Gender:
Posts: 2873
|
|
Re: Sum-Product Numbers
« Reply #12 on: Jan 10th, 2005, 7:09pm » |
Quote Modify
|
2005 0's?
|
|
IP Logged |
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Sum-Product Numbers
« Reply #13 on: Jan 11th, 2005, 9:18am » |
Quote Modify
|
on Jan 10th, 2005, 7:09pm, rmsgrey wrote:
As a minimum...? Mwahhh...:
(-2005) * (-2) * (-1)2003 = (-2005) + (-2) + 2003 * (-1) = -4010
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum-Product Numbers
« Reply #14 on: Jan 11th, 2005, 12:42pm » |
Quote Modify
|
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..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Sum-Product Numbers
« Reply #15 on: Jan 11th, 2005, 1:32pm » |
Quote Modify
|
on Jan 11th, 2005, 12:42pm, 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 Jan 8th, 2005, 3:45pm, 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. |
|
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Sum-Product Numbers
« Reply #16 on: Jan 11th, 2005, 1:38pm » |
Quote Modify
|
Yes, integer factors/terms, but still a (natural number) sum-product number
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: Sum-Product Numbers
« Reply #17 on: Jan 12th, 2005, 8:03am » |
Quote Modify
|
on Jan 11th, 2005, 9:18am, JocK wrote:| As a minimum...? Mwahhh...: |
|
Minimum magnitude...
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print