Sequence of length n having equal sum and product
Louis Marmet
2005 March 19
(PAGE UNDER
CONSTRUCTION)
The series A104173(n),
is listed in the "On-Line Encyclopedia of Integer Sequences", is
defined as:
A104173(n) is the smallest integer
equal to the sum and the product of the same n positive integers:
A104173(n) = i(1) + i(2) + ... + i(n) = i(1) * i(2) * ... *
i(n).
The first few terms are A104173(n)={1, 4, 6,
8, 8, 12, 12, 12,
15, 16, 16, 16, 18, 20, 24, 24, 24, 24, 24, 28, 27, 32, 30, 48, 32, 32,
32, 36, 36, 36, 42, 40, 40, 48, 48, 48, 45, 48, 48, 48, 48, 48, 54, 60,
54, 56, 54, 60, 63, 60, 60, 60, 63, 64, 64, 64, 64, 64, 70, 72, 72, 72,
72, 72, 72, 84, 80, 80, 81, 80, 80, 80, 81, 84, 88, 96, 90, 96, 90,
108, 90, 96, 96, 96, 96, 96, 96, 96, 96, 100, 110, 112, 105, 108, 108,
108, 117, 108, 108, 108, 112, 112, 120, 120, 120, 120, 120, 120, 120,
120, 120, 152, 125, 228, 126,
128, 128, 128, 128, 128, 128, 140, ...}.
The factors are (more numbers here, 1MB file!):
A104173( 1) = 1
= 1+ 1×0
A104173( 2) = 4
= 2+ 2+ 1×0
A104173( 3) = 6
= 3+ 2+ 1×1
A104173( 4) = 8
= 4+ 2+ 1×2
A104173( 5) = 8
= 2+ 2+ 2+ 1×2
A104173( 6) = 12 = 6+
2+ 1×4
A104173( 7) = 12 = 4+
3+ 1×5
A104173( 8) = 12 = 3+
2+ 2+ 1×5
A104173( 9) = 15 = 5+
3+ 1×7
A104173( 10)= 16 = 4+
4+ 1×8
A104173( 11)= 16 = 4+
2+ 2+ 1×8
A104173( 12)= 16 = 2+
2+ 2+ 2+
1×8
A104173( 13)= 18 = 3+
3+ 2+ 1×10
A104173( 14)= 20 = 5+
2+ 2+ 1×11
A104173( 15)= 24 = 8+
3+ 1×13
A104173( 16)= 24 = 6+
4+ 1×14
A104173( 17)= 24 = 6+
2+ 2+ 1×14
A104173( 18)= 24 = 4+
3+ 2+ 1×15
A104173( 19)= 24 = 3+
2+ 2+ 2+
1×15
A104173( 20)= 28 = 7+
2+ 2+ 1×17
A104173( 21)= 27 = 3+
3+ 3+ 1×18
A104173( 22)= 32 = 8+
4+ 1×20
A104173( 23)= 30 = 5+
3+ 2+ 1×20
A104173( 24)= 48 = 24+ 2+
1×22
...
A104173(114)=228 = 114+ 2+
1×112
...
A104173(174)=348 = 174+ 2+
1×172
...
A104173(444)=888 = 444+ 2+
1×442
Of interest is the series when A104173(n)=2n. This is the series A033179(n)
representing the "Numbers i such that there is just one sequence of
length i having equal sum and product."
The
series is A033179(n) = {2, 3, 4, 6, 24, 114, 174, 444}. No
more
terms are given. A search up to 13587782064 has not
found any additional term.
Attempt to find
another term for A033179
(Or to prove
that the series is finite!)
I.
BASIC DEFINITIONS
Excluding the trivial case with n=1, we wish to find n positive
integers i1, i2,
i3, ..., in such that their sum is equal to their
product:
i1+i2+i3+...
+in = i1×i2×i3×...
×in [n>1].
|
(1)
|
To avoid repetition of equivalent
solutions, we sort the ik such that ik≥ik+1.
For example, the
solutions for n<8 are:
n=2: 4= 2+2= 2×2
n=3: 6= 3+2+1=
3×2×1
n=4: 8= 4+2+1+1=
4×2×1×1
n=5: 10= 5+2+1+1+1=
5×2×1×1×1
9= 3+3+1+1+1= 3×3×1×1×1
8= 2+2+2+1+1= 2×2×2×1×1
n=6: 12= 6+2+1+1+1+1=
6×2×1×1×1×1
n=7: 14= 7+2+1+1+1+1+1=
7×2×1×1×1×1×1
12= 4+3+1+1+1+1+1= 4×3×1×1×1×1×1
If there is a solution to
Eq. (1) and i2, i3, ..., in are given,
there is only one possible value for i1. To
demonstrate this, we write Eq. (1) differently:
g(n,p) =
a×f1×f2×... ×fr=
a+f1+f2+... +fr+1×(n-r-1)
[a≥fk≥fk+1≥2, n>r≥1],
|
(2)
|
where a and fi are
positive integers and p is
the product of the fi:
|
r
p = Π fi [fi≥2, r≥1].
i=1
|
(4)
|
It is useful to define s as the
sum
of the fi:
|
r
s = Σ fi [fi≥2, r≥1],
i=1 |
(3)
|
and h=s-r. From these it is
easy
to see that the following useful relations hold:
p ≥ s ≥ 2r
and
p
≥ s > h ≥ r.
|
(5)
|
We thus obtain the following
list for
n<8:
g(2,2)= 4=
2+2= 2×2
g(3,2)= 6= 3+2+1=
3×2
g(4,2)= 8= 4+2+1+1=
4×2
g(5,2)= 10= 5+2+1+1+1=
5×2
g(5,3)= 9=
3+3+1+1+1=
3×3
g(5,4)= 8=
2+2+2+1+1=
2×2×2
g(6,2)= 12= 6+2+1+1+1+1=
6×2
g(7,2)= 14= 7+2+1+1+1+1+1=
7×2
g(7,3)= 12= 4+3+1+1+1+1+1=
4×3
II.
GENERAL RELATIONS
THEOREM 1: For
given
values of i2,
i3, ..., in, there is either no solution or only
one
possible value of i1 that will satisfy Eq. (1).
It is easy to show
that for a solution of Eq. (2) to exist, we must have:
|
n+h-1
a = ——————— [a is an integer, p>1],
p-1 |
(6)
|
since
(n+h-1)÷(p-1)×p=
(n+h-1)÷(p-1)+s+(n-r-1). We therefore have from Eq.
(2):
|
n+h-1
g(n,p) = ———————×p.
p-1
|
(7)
|
It follows that for given values
of i2, i3, ..., in, the values
for f1, f2, ..., fr, s, p and r are
defined and there is a unique solution if:
n ≡ 0 (mod 1) if
p=2, n ≡
p-h (mod p-1) if p>2,
|
(8)
|
no solution
otherwise.
Q.E.D.
THEOREM 2: For
given values
of n, s and p, there could be more than one representation for g(n,p),
but all with the same value of r.
For example:
g(558,72)= 576=
8+6+6+2+1×554= 8×6×6×2 and g(558,72)= 576=
8+8+3+3+1×554= 8×8×3×3.
The only way to satisfy Eq. (8) with another value r' would be
to have
n+s-r'-1 ≡ 0 (mod p-1) with r'=r+m×(p-1) [m a positive
integer].
From Eq. (5) p≥2r' we obtain the condition p≥2(r+m(p-1)) which is never
satisfied. There is therefore no other value of r satisfying Eq.
(8).
Q.E.D.
THEOREM 3: For given
values
of n, r and p, there could be more than one representation for g(n,p),
but all with the same value of s.
The only way to satisfy Eq. (8) with another value s' would be
to have
n+s'-r-1 ≡ 0 (mod p-1) with s'=s+m×(p-1) [m a positive
integer].
From Eq. (5) p≥s' we obtain the condition p≥s+m(p-1) which is never
satisfied. There is therefore no other value of s satisfying Eq.
(8).
Q.E.D.
Note that if n, r and s are given, there could be more than one
values of p that would satisfy Eq. (8). For example:
g(53,8)= 64= 8+4+2+1×50 but g(53,9)= 63= 7+3+3+1×50.
THEOREM 4: For a
given n and p, the value h=s-r is the same for any solution of Eq.
(2). The value of g(n,p) is completely determined by n and p.
For example:
g(275,48)= 288= 6+4+4+3+1×271, h=8, and g(275,48)= 288=
6+6+2+2+2+1×270, h=8.
We can simply re-write Eq. (8) as: h+n ≡ 1 (mod p-1).
There is no other solution of the form h'=h+m×(p-1) since from
Eq. (5),
h'<p. From Eq. (7) follows that the value of g(n,p) is
completely determined by n and p.
Q.E.D.
THEOREM 5: For a
given n, there is always a solution
which is of the form:
n+2+1+...
= n×2×1×... = 2n.
Using Eq. (8) with r=1, s=2 and p=2, n ≡ 0 (mod 1), that is, any
n gives a
solution to Eq. (1).
Q.E.D.
III. USEFUL RELATIONS
THEOREM 6: Given
a value for n, the largest value g(n,p) can take is 2n.
Since a=(n+h-1)÷(p-1) and a≥f1 (Eqs. (2) and
(6)), we find:
We want to confirm that:
g(n,p)= a×p=
|
n+h-1
———————×p ≤ 2n.
p-1 |
(10)
|
We can simplify Eq. (10) to get:
Eq. (11) should hold true for all
values of n satisfying Eq. (9). We have then:
(h-1)×p
≤ (f1×(p-1)-h+1)×(p-2).
|
(12)
|
A few simplifications of Eq. (12)
gives:
Starting from:
fb×(pb-2)
≥ 2×(hb-1)
[b<r]. |
(14)
|
where: pb=fb×fb+1×...×fr,
hb=sb-rb, sb=fb+fb+1+...+fr
and rb=r-b+1, we obtain:
fb×(fbpb+1-4)+2
≥ 2×(hb+1-1).
Since fb≥fb+1≥2
and pb+1>1, it is easy to see that fb×(fbpb+1-4)+2 ≥ fb+1×(pb+1-2).
The relation:
fb×(fbpb+1-4)+2
≥ fb+1×(pb+1-2) ≥ 2×(hb+1-1)
[b<r, pb+1>1]
is true if:
fb+1×(pb+1-2)
≥ 2×(hb+1-1). |
(15)
|
Eq. (15) is Eq. (14) with the
first factor fb removed.
It is easy to show that Eq. (14) is true for b=r since sr=pr=fr
and hr=fr-1:
fr×(fr-2)
≥ 2×(fr-2). |
(16)
|
This is true since fr≥2.
We now recursively show
that if Eq. (16) is true, Eq. (14) is true for b=r-1, b=r-2, etc.
Eq. (14) is therefore true for b=1 which corresponds to Eq. (13).
Thus Eq. (11) is true which leads to:
Q.E.D.
IV. SOLUTIONS TO
g(n,p)<2n
Details about each step of the calculation are given at this
page: long.html.
... to be continued ...
Updated last: April 11th,
2005
Visitors since March 28th, 2005:
