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 i₁, i₂, i₃, ..., i_n such that their sum is equal to their product:

i₁+i₂+i₃+... +i_n = i₁×i₂×i₃×... ×i_n [n>1].

(1)

To avoid repetition of equivalent solutions, we sort the i_k such that i_k≥i_k+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 i₂, i₃, ..., i_n are given, there is only one possible value for i₁. To demonstrate this, we write Eq. (1) differently:

g(n,p) = a×f₁×f₂×... ×f_r= a+f₁+f₂+... +f_r+1×(n-r-1) [a≥f_k≥f_k+1≥2, n>r≥1],

(2)

where a and f_i are positive integers and p is the product of the f_i:

r
p = Π f_i [f_i≥2, r≥1].
i=1

(4)

It is useful to define s as the sum of the f_i:

r
s = Σ f_i [f_i≥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 i₂, i₃, ..., i_n, there is either no solution or only one possible value of i₁ 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 i₂, i₃, ..., i_n, the values for f₁, f₂, ..., f_r, 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≥f₁ (Eqs. (2) and (6)), we find:

n ≥ f₁×(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 ≤ (f₁×(p-1)-h+1)×(p-2).

(12)

A few simplifications of Eq. (12) gives:

f₁×(p-2) ≥ 2×(h-1).

(13)

Starting from:

f_b×(p_b-2) ≥ 2×(h_b-1) [b<r].

(14)

where: p_b=f_b×f_b+1×...×f_r, h_b=s_b-r_b, s_b=f_b+f_b+1+...+f_r and r_b=r-b+1, we obtain:

fb×(fbpb+1-4)+2
≥ 2×(hb+1-1).

Since f_b≥f_b+1≥2 and p_b+1>1, it is easy to see that f_b×(f_bp_b+1-4)+2 ≥ f_b+1×(p_b+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:

f_b+1×(p_b+1-2) ≥ 2×(h_b+1-1).

(15)

Eq. (15) is Eq. (14) with the first factor f_b removed.

It is easy to show that Eq. (14) is true for b=r since s_r=p_r=f_r and h_r=f_r-1:

f_r×(f_r-2) ≥ 2×(f_r-2).

(16)

This is true since f_r≥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: April 11^th, 2005

Visitors since March 28^th, 2005: Number of visitors