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:
n ≥ f1×(p-1)-h+1.
(9)
  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:
(h-1)×p ≤ n×(p-2).
(11)
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:
f1×(p-2) ≥ 2×(h-1).
(13)

  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:
g(n,p) ≤ 2n.
(17)
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: 2020-5-22