Back
 OALibJ  Vol.7 No.12 , December 2020
Subset of the Shape of Numbers
Abstract: This article is based on the concept of Shape of numbers, introduces subset of the Shape and obtains its calculation formula. This article also makes some analysis and draws new conclusions, especially the calculation method of 1M+2M+3M+···+NM. The Shape’s concept becomes clearer and richness.

1. Introduction

Peng, J. has introduced Shape of numbers in [1] [2]:

( I 1 , I 2 , , I M ) , I i N , I 1 < I 2 < < I M

There are M-1 intervals between adjacent numbers.

I i + 1 I i = 1 means continuity, I i + 1 I i > 1 means discontinuity.

Shape of numbers: collect ( I 1 , I 2 , , I M ) with the same continuity and discontinuity at the same position into a catalog, call it a Shape. A Shape has a min Item:

( 1 , K 1 , K 2 , ) , Use the symbol PS = [min Item] to represent it. If K i + 1 K i = D > 1 then only I i + 1 I i D is allowed.

The single ( I 1 , I 2 , , I M ) is an item, I 1 I 2 I M is the product. Ii is a factor.

Example:

P S = [ 1 , 2 ] ( 1 , 2 ) , ( 2 , 3 ) , ( 3 , 4 ) , ( 1000 , 1001 ) P S

P S = [ 1 , 3 ] ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 4 ) , ( 1 , 5 ) , ( 2 , 5 ) , ( 3 , 5 ) , ( 1000 , 2001 ) P S

P S = [ 1 , 4 ] ( 1 , 4 ) , ( 1 , 5 ) , ( 2 , 5 ) , ( 1 , 6 ) , ( 2 , 6 ) , ( 3 , 6 ) P S , ( 3 , 5 ) , ( 4 , 6 ) P S

P S = [ 1 , 4 , 6 ] ( 1 , 4 , 7 ) , ( 1 , 5 , 7 ) , ( 2 , 5 , 7 ) P S , ( 3 , 5 , 7 ) P S

Define:

SET(N, PS) = set of items belonging to PS in [ 1 , N 1 ]

PM(PS) = count of factors

PB(PS) = count of discontinuities

MIN(PS) = min product: M I N ( [ 1 , 2 , 3 ] ) = 1 × 2 × 3 , M I N ( [ 1 , 2 , 4 ] ) = 1 × 2 × 4

IDX(PS) = (max factor)+1

PH(PS) = IDX(PS) − PB(PS) − 2

Basic Shape: intervals = 1 or 2

BASE(PS) = BS: if 1) PB(BS) = PB(PS), 2) PM(BS) = PM(PS), 3) BS is a Basic Shape 4) BS has discontinuity intervals at the same positions of PS.

Example:

P S = [ 1 , 2 ] B A S E ( P S ) = [ 1 , 2 ]

P S = [ 1 , 3 ] , [ 1 , 4 ] , [ 1 , K > 2 ] B A S E ( P S ) = [ 1 , 3 ]

P S = [ 1 , 3 , 4 ] , [ 1 , 4 , 5 ] , [ 1 , K > 2 , X = K + 1 ] B A S E ( P S ) = [ 1 , 3 , 4 ]

P S = [ 1 , 3 , 5 ] , [ 1 , 4 , 9 ] , [ 1 , K > 2 , X > K + 1 ] B A S E ( P S ) = [ 1 , 3 , 5 ]

|SET(N, PS)| = Count of items in SET(N, PS)

SUM(N, PS) = Sum of all products in SET(N, PS)

Example:

S U M ( 6 , [ 1 , 2 , 4 ] ) = 1 × 2 × 4 + 1 × 2 × 5 + 2 × 3 × 5

S U M ( 9 , [ 1 , 4 , 7 ] ) = 1 × 4 × 7 + 1 × 4 × 8 + 1 × 5 × 8 + 2 × 5 × 8

[1] [2] came to the following conclusion:

1.1) | S E T ( N , P S ) | = ( N P H ( P S ) 1 P B ( P S ) + 1 )

1.2) S U M ( N , P S ) = M I N ( P S ) ( N I D X ( P S ) ) , PS is a Basic Shape

The following uses count of X K for count of { X 1 , X 2 , , X M } { K 1 , K 2 , , K M }

1.3) P S = [ 1 , K 1 , , K M ] , B S = B A S E ( P S ) = [ 1 , G 1 , , G M ]

Use the form ( G 1 + K 1 ) ( G 2 + K 2 ) ( G M + K M ) = X 1 X 2 X M , Xi = Gi or Ki.

The expansion has 2M items, don’t swap the factors of X 1 X 2 X M , then each X 1 X 2 X M corresponds to one expression = A q ( N P H ( P S ) I D X ( B S ) q ) , q = count of X K

S U M ( N , P S ) = A q ( N P H ( P S ) I D X ( B S ) q ) , 2M items in total.

A q = i = 1 M ( X i + D i ) , D i = { m : X i = G i , m = countof { X 1 , , X i 1 } K + m : X i = K i , m = countof { X 1 , , X i 1 } G

Example:

P S = [ 1 , K 1 3 , K 2 K 1 + 2 , K 3 K 2 + 2 ] , B S = B A S E ( P S ) = [ 1 , 3 , 5 , 7 ]

Theform = ( 3 + K 1 ) ( 5 + K 2 ) ( 7 + K 3 ) = 3 × 5 × 7 + 3 × 5 × K 3 + 3 × K 2 × 7 + 3 × K 2 × K 3 + K 1 × 5 × 7 + K 1 × 5 × K 3 + K 1 × K 2 × 7 + K 1 × K 2 × K 3

P = N P H ( P S ) = N { I D X ( P S ) P B ( P S ) 2 } = N { K 3 + 1 3 2 } = N K 3 + 4

I D X ( B S ) = 8

?

S U M ( N , P S ) = 3 × 5 × 7 ( P 8 ) + 3 × 5 × ( K 3 + 2 ) ( P 7 ) + 3 × ( K 2 + 1 ) × ( 7 1 ) ( P 7 ) + 3 × ( K 2 + 1 ) × ( K 3 + 1 ) ( P 6 ) + K 1 × ( 5 1 ) × ( 7 1 ) ( P 7 ) + K 1 × ( 5 1 ) × ( K 3 + 1 ) ( P 6 ) + K 1 × K 2 × ( 7 2 ) ( P 6 ) + K 1 × K 2 × K 3 ( P 5 )

Anitem P S = { begin , K 1 + E 1 , , K M + E M } , K is fixed, E is variable.

Aproduct = begin × ( K 1 + E 1 ) ( K M + E M ) = begin × F 1 F 2 F M , F i = E i or F i = K i

That is, a product can be broken down into 2M parts.

Define

S U M _ K ( S E T ( N , P S ) , P F = F 1 F 2 F M ) = Sum of one part of S U M ( N , P S )

PF indicates the part. P F = F 1 F 2 F M , F i = E i or F i = K i

Rewrite 1.3) and add {braces}:

S U M ( N , P S ) = product = begin × F 1 F M = i = 1 M ( X i + D i ) ( A M q )

X i + D i = { { G i D i } : X i = G i , D i = countof { X 1 , , X i 1 } K { K i } + { D i } : X i = K i , D i = countof { X 1 , , X i 1 } G

Let S U M 1 ( N , P S ) = S U M ( N , P S ) expand by the {braces}:

1.4) S U M _ K ( S E T ( N , P S ) , P F ) = Expansionof S U M 1 ( N , P S ) with same { K i } P F = i = 1 M Y i ( A M q ) , Y i = { 0 : F i = K i , X i = G i K i : F i = K i , X i = K i G i D i : F i = E i , X i = G i , D i = countof { X 1 , , X i 1 } K D i : F i = E i , X i = K i , D i = countof { X 1 , , X i 1 } G

Example:

S U M ( N , [ 1 , K 1 3 , K 2 K 1 + 2 ] ) , form = ( 3 + K 1 ) ( 5 + K 2 ) ?

= 15 ( N K 2 + 3 6 ) + 3 ( { K 2 } + { 1 } ) ( N K 2 + 3 5 ) + K 1 ( { 5 1 } ) ( N K 2 + 3 5 ) + K 1 K 2 ( N K 2 + 3 4 )

Expand by the {braces}:

= { 15 ( N K 2 + 3 6 ) + 3 ( N K 2 + 3 5 ) } + 3 K 2 ( N K 2 + 3 5 ) + 4 K 1 ( N K 2 + 3 5 ) + K 1 K 2 ( N K 2 + 3 4 ) = begin = 1 N K 2 begin × ( K 1 + E 1 , begin ) ( K 2 + E 2 , begin )

?

S U M _ K ( S E T ( N , P S ) , E 1 E 2 ) = allitems begin E 1 , i E 2 , i = 15 ( N K 2 + 3 6 ) + 3 ( N K 2 + 3 5 )

S U M _ K ( S E T ( N , P S ) , E 1 K 2 ) = allitems begin E 1 , i K 2 = 3 K 2 ( N K 2 + 3 5 )

S U M _ K ( S E T ( N , P S ) , K 1 E 2 ) = allitems begin K 1 E 2 , i = 4 K 1 ( N K 2 + 3 5 )

S U M _ K ( S E T ( N , P S ) , K 1 K 2 ) = allitems begin K 1 K 2 = K 1 K 2 ( N K 2 + 3 4 )

This can explain why 1.3) has that strange form:

We can calculate every part of 1.3) by some way without 1.3). There may be complex relationships between the parts, but their sum just match a simple form.

1.5) Use the symbol of 1.3), when G i = K i , N 1 = Count of X K , N 1 + N 2 = M

H ( N 1 , N 2 , K ) = A q = N 1 = i = 1 M ( X i + D i ) = K 1 K 2 K M ( M N 1 , N 2 )

Sum traverses all (N1, N2)-Choice of K

This ? 1.3) is compatible with 1.2)

1.6) P is a prime number, {PS1, PS2, …} are all of the Basic Shapes,

P M ( P S 1 ) = P M ( P S 2 ) = , P B ( P S 1 ) = P B ( P S 2 ) = > 0 , I D X ( P S 1 ) = I D X ( P S 2 ) = = P ,

That is, them are Basic shapes, have same count of factors and same count of discontinuities > 0, and max factor = P − 1, then M I N ( P S 1 ) + M I N ( P S 2 ) + 0 M O D P

Example:

1 × 2 × 4 × 6 + 1 × 3 × 4 × 6 + 1 × 3 × 5 × 6 1 × 2 × 3 × 4 × 6 + 1 × 2 × 3 × 5 × 6 + 1 × 2 × 4 × 5 × 6 + 1 × 3 × 4 × 5 × 6 0 M O D 7

2. Subset of SET(N, PS)

P S = [ 1 , K 1 , K 2 , , K M ] , P T = [ 1 , T 1 , T 2 , , T M ] , Item = { I 0 , I 1 , I 2 , , I M } S E T ( N , P S )

If PB(PS) = 0, items S E T ( N , P S ) is very simple.

If PB(PS) > 0, some changes appear in SET(N, PS).

We can fix some discontinuities of the Shape to get subsets.

Define SET(N, PS, PT) =Subset of SET(N, PS), a valid

P T = [ 1 , T 1 , , T M ] = { T i + 1 T i = 1 : K i + 1 K i = 1 , means I i + 1 I i = 1 T i + 1 T i = 1 : K i + 1 K i = D > 1 , means I i + 1 I i = D T i + 1 T i = 2 : K i + 1 K i = D > 1 , means I i + 1 I i D (*)

others are invalid.

Example:

S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 3 , 5 ] ) = S E T ( N , [ 1 , 3 , 5 ] )

S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 4 , 5 ] ) , S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 3 , 6 ] ) , S E T ( N , [ 1 , 2 , 9 ] , [ 1 , 3 , 4 ] ) is invalid.

S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 2 , 4 ] ) = { ( 1 , 3 , 5 ) , ( 1 , 3 , 6 ) , ( 2 , 4 , 6 ) , ( 1 , 3 , 7 ) , ( 2 , 4 , 7 ) , ( 3 , 5 , 7 ) , }

I 2 I 1 = ( 3 1 ) = 2 , I 3 I 2 ( 5 3 ) = 2

S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 3 , 4 ] ) = { ( 1 , 3 , 5 ) , ( 1 , 4 , 6 ) , ( 2 , 4 , 6 ) , ( 1 , 5 , 7 ) , ( 2 , 5 , 7 ) , ( 3 , 5 , 7 ) , }

I 3 I 2 = ( 5 3 ) = 2 , I 2 I 1 ( 3 1 ) = 2

S E T ( N , [ 1 , 3 , 5 ] , [ 1 , 2 , 3 ] ) = { ( 1 , 3 , 5 ) , ( 2 , 4 , 6 ) , ( 3 , 5 , 7 ) , }

S E T ( N , [ 1 , 4 , 8 ] , [ 1 , 2 , 4 ] ) = { ( 1 , 4 , 8 ) , ( 1 , 4 , 9 ) , ( 2 , 5 , 9 ) , ( 1 , 4 , 10 ) , ( 2 , 5 , 10 ) , ( 3 , 6 , 10 ) , }

I 2 I 1 = ( 4 1 ) = 3 , I 3 I 2 ( 8 4 ) = 4

PT only has the change at (*). When a change happens, make the interval fixed.

The more changes, the fewer items:

Define PCHG(PS, PT) = count of change from BASE(PS) to PT

Example:

P C H G ( [ 1 , 3 , 5 ] , [ 1 , 2 , 4 ] ) = P C H G ( [ 1 , 4 , 7 ] , [ 1 , 2 , 4 ] ) = 1 , changed at T1

P C H G ( [ 1 , 3 , 5 ] , [ 1 , 3 , 4 ] ) = P C H G ( [ 1 , 4 , 7 ] , [ 1 , 3 , 4 ] ) = 1 , changed at T2

P C H G ( [ 1 , 3 , 5 ] , [ 1 , 2 , 3 ] ) = P C H G ( [ 1 , 8 , 10 ] , [ 1 , 2 , 3 ] ) = 2 , changed at T1, T2

2.1) S E T ( N , P S ) = S E T ( N , P S , B A S E ( P S ) )

2.2) | S E T ( N , P S , P T ) | = ( N P H ( P S ) 1 P C H G ( P S , P T ) P B ( P T ) + 1 )

If PT1 only change Ti of PT, Obvious: P C H G ( P S , P T 1 ) = P C H G ( P S , P T ) + 1

2.3) If PT1 only change Ti of PT, P T 1 = [ 1 , T 1 , , T i 1 , T i 1 , T i + 1 1 , , T M 1 ] .

Let P S 1 = [ 1 , K 1 , , K i 1 , K i + 1 , K i + 1 + 1 , , K M + 1 ] , then

S E T ( N , P S , P T ) = S E T ( N , P S , P T 1 ) S E T ( N , P S 1 , P T )

S E T ( N , P S , P T 1 ) = S E T ( N , P S , P T ) S E T ( N , P S 1 , P T )

In particular: P C H G ( P S , P T ) = 1 ? S E T ( N , P S , P T ) = S E T ( N , P S ) S E T ( N , P S 1 )

[Proof]

PT1 change Ti of PT ? T i T i 1 = 2 ? K i K i 1 > 1 ? P C H G ( P S , P T ) = P C H G ( P S 1 , P T )

| S E T ( N , P S , P T 1 ) | + | S E T ( N , P S 1 , P T ) | = ( N P H ( P S ) 1 P C H G ( P S , P T 1 ) P B ( P T 1 ) + 1 ) + ( N P H ( P S 1 ) 1 P C H G ( P S 1 , P T ) P B ( P T ) + 1 ) = ( N P H ( P S ) 2 P C H G ( P S , P T ) P B ( P T ) ) + ( N P H ( P S ) 2 P C H G ( P S 1 , P T ) P B ( P T ) + 1 )

= ( N P H ( P S ) 2 P C H G ( P S , P T ) P B ( P T ) ) + ( N P H ( P S ) 2 P C H G ( P S , P T ) P B ( P T ) + 1 ) = ( N P H ( P S ) 1 P C H G ( P S , P T ) P B ( P T ) + 1 ) = | S E T ( N , P S , P T ) |

Count of the Items is equal.

Every item in SET(N, PS1, PT) is in SET(N, PS, PT), and not in SET(N, PS, PT1).

q.e.d.

if P C H G ( P S , P T ) = 2 , PT changes at Ti and Tj, then

P T = [ 1 , G 1 , , G i 1 , G i 1 , , G j 1 1 , G j 2 , G j + 1 2 , , G M 2 ]

Let

P T A = [ 1 , G 1 , , G i 1 , G i 1 , , G M 1 ] ,

P T B = [ 1 , G 1 , , G j 1 , G j 1 , , G M 1 ]

P S A = [ 1 , K 1 , , K i 1 , K i + 1 , , K M + 1 ] ,

P S B = [ 1 , K 1 , , K j 1 , K j + 1 , , K M + 1 ]

P S 2 = [ 1 , K 1 , , K i 1 , K i + 1 , , K j 1 + 1 , K j + 2 , K j + 1 + 2 , , K M + 2 ]

?

S E T ( N , P S , P T ) = S E T ( N , P S , P T A ) S E T ( N , P S A , P T A ) = { S E T ( N , P S , B S ) S E T ( N , P S B , B S ) } { S E T ( N , P S A , B S ) S E T ( N , P S 2 , B S ) } = S E T ( N , P S , B S ) [ S E T ( N , P S A , B S ) S E T ( N , P S B , B S ) ] + S E T ( N , P S 2 , B S ) = S E T ( N , P S ) [ S E T ( N , P S A ) S E T ( N , P S B ) ] + S E T ( N , P S 2 )

General:

2.4) The relationship between SET(N, PS, PT) and SET(N, PSX) is similar to the Inclusion Exclusion Principle.

3. Calculation formula of SET(N, PS, PT)

Define:

SUM_SUBSET(N, PS, PT) = Sum of all products in SET(N, PS, PT)

When PT is invalid, SUM_SUBSET(N, PS, PT) = 0

Only valid PT is discussed below.

P S = [ 1 , K 1 , K 2 , , K M ] , B S = B A S E ( P S ) = [ 1 , G 1 , G 2 , , G M ] , P T = [ 1 , T 1 , T 2 , , T M ]

3.1) Use the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) = X 1 X 2 X M , then

S U M _ S U B S E T ( N , P S , P T ) = A q ( N P H ( P S ) P C H G ( P S , P T ) I D X ( P T ) q )

A q = i = 1 M ( X i + D i ) , D i = { m : X i = T i , m = countof { X 1 , , X i 1 } K + m : X i = K i , m = countof { X 1 , , X i 1 } T

q = count of X K

[Proof]

1) If PT = BS, then S U M _ S U B S E T ( N , P S , B S ) = S U M ( N , P S ) ? the formula holds.

2) If M = 1 and PT has 1 change, then P S = [ 1 , K 1 > 2 ] , P T = [ 1 , T 1 ] = [ 1 , 2 ] , B S = [ 1 , G 1 ] = [ 1 , 3 ] ,

Let P S 1 = [ 1 , K 1 + 1 ] , 2.3) →

S U M _ S U B S E T ( N , P S , P T ) = S U M ( N , P S ) S U M ( N , P S 1 ) = { G 1 ( N P H ( P S ) I D X ( B S ) ) + K 1 ( N P H ( P S ) I D X ( B S ) 1 ) } { G 1 ( N P H ( P S 1 ) I D X ( B S ) ) + ( K 1 + 1 ) ( N P H ( P S 1 ) I D X ( B S ) 1 ) }

= { G 1 ( N P H ( P S 1 ) I D X ( B S ) ) + K 1 ( N P H ( P S 1 ) I D X ( B S ) 1 ) + G 1 ( N P H ( P S 1 ) I D X ( B S ) 1 ) + K 1 ( N P H ( P S 1 ) I D X ( B S ) 2 ) } { G 1 ( N P H ( P S 1 ) I D X ( B S ) ) + ( K 1 + 1 ) ( N P H ( P S 1 ) I D X ( B S ) 1 ) } = ( G 1 1 ) ( N P H ( P S 1 ) I D X ( B S ) 1 ) + K 1 ( N P H ( P S 1 ) I D X ( B S ) 2 )

= T 1 ( N P H ( P S 1 ) I D X ( B S ) 1 ) + K 1 ( N P H ( P S 1 ) I D X ( B S ) 2 ) = T 1 ( N P H ( P S ) 1 I D X ( P T ) ) + K 1 ( N P H ( P S ) 1 I D X ( P T ) 1 ) = T 1 ( N P H ( P S ) P C H G ( P S , P T ) I D X ( P T ) ) + K 1 ( N P H ( P S ) P C H G ( P S , P T ) I D X ( P T ) 1 )

The form = (T1 + K1) ? The formula holds.

3) If M > 1 and PT only has 1 change at TM, then P T = [ 1 , G 1 , , G M 1 , G M 1 ]

Let P S 1 = [ 1 , K 1 , , K M 1 , K M + 1 ] , 2.3) → P H ( P S 1 ) = P H ( P S ) + 1 :

S U M ( N , P S , P T ) = S U M ( N , P S ) S U M ( N , P S 1 ) = i = I D X ( B S ) M I D X ( B S ) A i ( N P H ( P S ) i ) i = I D X ( B S ) M I D X ( B S ) B i ( N P H ( P S 1 ) i ) = i = I D X ( B S ) M I D X ( B S ) A i { ( N P H ( P S 1 ) i ) + ( N P H ( P S 1 ) i 1 ) } i = I D X ( B S ) M I D X ( B S ) B i ( N P H ( P S 1 ) i )

= i = I D X ( B S ) M I D X ( B S ) ( A i B i ) ( N P H ( P S 1 ) i ) + A i ( N P H ( P S 1 ) i 1 ) = i = I D X ( B S ) M I D X ( B S ) ( A i B i ) ( N P H ( P S ) 1 i ) + A i ( N P H ( P S ) 1 i 1 ) = i = I D X ( B S ) M 1 I D X ( B S ) C J ( N P H ( P S ) 1 J ) , J = i 1 , C J 1 = A i + 1 + A i B i = J = I D X ( P T ) M I D X ( P T ) + 1 C J ( N P H ( P S ) 1 J )

When i = I D S ( B S ) , C i = M I N ( B S ) M I N ( B S ) = 0

= J = I D X ( P T ) M I D X ( P T ) C J ( N P H ( P S ) 1 J )

Use the symbol of (1.3)

i = I D X ( B S ) C N T , C N T = Count of X K

Let R ( E ) = L = 1 M 1 ( X L + D L ) , E = Count of { X 1 , , X M 1 } K

A i + 1 = R ( C N T 1 ) ( G M ( C N T 1 ) ) + R ( C N T 2 ) ( K M + ( M 1 ) ( C N T 2 ) )

A i = R ( C N T ) ( G M C N T ) + R ( C N T 1 ) ( K M + ( M 1 ) ( C N T 1 ) )

B i = R ( C N T ) ( G M C N T ) + R ( C N T 1 ) ( ( K M + 1 ) + ( M 1 ) ( C N T 1 ) )

C J 1 = A i + 1 + A i B i = R ( C N T 1 ) ( G M C N T ) + R ( C N T 2 ) ( K M + M C N T + 1 ) = R ( C N T 1 ) ( T M { C N T 1 } ) + R ( C N T 2 ) ( K M + { ( M 1 ) ( C N T 2 ) } )

? Match of the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M )

4) If M > 1 and PT only has 1 change at T i < M , Let R ( E ) = L = 1 , l i M ( X L + D L ) , use the same method of (3).

5) if P C H G ( P S , P T ) > 1 , Use 2.3) → divide the Items into subset ? deducing by induction.

q.e.d.

Example:

N P H ( [ 1 , 3 , 5 , 7 ] ) P C H G ( [ 1 , 3 , 5 , 7 ] , [ 1 , 2 , 3 , 4 ] ) = N ( 8 3 2 ) 3 = N 6

S U M _ S U B S E T ( N , [ 1 , 3 , 5 , 7 ] , [ 1 , 2 , 3 , 4 ] )

?

form = ( 2 + 3 ) ( 3 + 5 ) ( 4 + 7 ) = 24 ( N 6 5 ) + 108 ( N 6 4 ) + 174 ( N 6 3 ) + 105 ( N 6 2 ) = 1 × 3 × 5 × 7 + 2 × 4 × 6 × 8 + 3 × 5 × 7 × 9 +

Among:

24 = 2 × 3 × 4 ; 105 = 3 × 5 × 7

108 = 2 × 3 × ( 7 + 2 ) + 2 × ( 5 + 1 ) × ( 4 1 ) + 3 × ( 3 1 ) × ( 4 1 )

174 = 2 × ( 5 + 1 ) × ( 7 + 1 ) + 3 × ( 3 1 ) × ( 7 + 1 ) + 3 × 5 × ( 4 2 )

Use the same method of 3.1)

3.2) Calculation formula of SUM_K(SET(N, PS, PT), PF) is similar to 1.4).

Example:

S U M _ S U B S E T ( N , [ 1 , 3 , 7 ] , [ 1 , 2 , 3 ] ) = 6 ( N 6 4 ) + 2 × ( { 7 } + { 1 } ) ( N 6 3 ) + 3 × ( { 3 1 } ) ( N 6 3 ) + 3 × 7 ( N 6 2 )

S U M _ S U B S E T ( 10 , [ 1 , 3 , 7 ] , [ 1 , 2 , 3 ] ) = 1 × 3 × 7 + 2 × 4 × 8 + 3 × 5 × 9 = 1 × 3 × 7 + 2 × ( 3 + 1 ) × ( 7 + 1 ) + 3 × ( 3 + 2 ) × ( 7 + 2 ) = { 1 × 3 × 7 + 2 × 3 × 7 + 3 × 3 × 7 } + { 2 × 3 × 1 + 3 × 3 × 2 } + { 2 × 1 × 7 + 3 × 2 × 7 } + { 2 × 1 × 1 + 3 × 2 × 2 }

?

{ 1 × 3 × 7 + 2 × 3 × 7 + 3 × 3 × 7 } = 3 × 7 ( 10 6 2 )

{ 2 × 3 × 1 + 3 × 3 × 2 } = 3 × ( { 3 1 } ) ( N 6 3 ) = 6 ( 10 6 3 )

{ 2 × 1 × 7 + 3 × 2 × 7 } = 2 × 7 ( N 6 3 ) = 14 ( N 6 3 )

{ 2 × 1 × 1 + 3 × 2 × 2 } = 6 ( 10 6 4 ) + 2 × { 1 } ( 10 6 3 )

3.3) Use the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) = X 1 X 2 X M

S U M _ K ( S E T ( N , P S , P T ) , E 1 E 2 E M ) = A q ( N P H ( P S ) P C H G ( P S , P T ) I D X ( P T ) q )

A q = i = 1 M D i , D i = { T i m : X i = T i , m = countof { X 2 , , X i 1 } K + m : X i = K i , m = countof { X 2 , , X i 1 } T

q = count of X K , X 1 = T 1 , 2M-1 Items in total.

In particular:

If P T 1 = [ 1 , T 1 , , T M ] = [ 1 , 2 , , M + 1 ] , then P B ( P S ) = P C H G ( P S , P T 1 )

N P H ( P S ) P C H G ( P S , P T 1 ) = N [ I D X ( P S ) 2 P B ( P S ) ] P B ( P S ) = N ( K M 1 )

I D X ( P T 1 ) = M + 2

S U M ( S E T ( N , P S , P T 1 ) , E 1 E M ) = 2 × 1 M + 3 × 2 M + + ( N K M ) × ( N K M 1 ) M

?

S U M ( S E T ( N + K M + 1 , P S , P T 1 ) , E 1 E M ) = 2 × 1 M + 3 × 2 M + + ( N + 1 ) × N M

3.4) n = 1 N ( n + 1 ) n M = S U M _ K ( S E T ( N + K M + 1 , P S , P T 1 ) , E 1 E M )

4. Analysis of SUM_SUBSET(N, PS, [1, 2, ∙∙∙, M + 1])

P S = [ 1 , K 1 , K 2 , , K M ] , P T 1 = [ 1 , 2 , 3 , , M + 1 ] . The simplest subset of PS is SET(N, PS, PT1).

S U M _ S U B S E T ( N , P S , P T 1 ) = q = 0 M C q ( N ( K M 1 ) M + 2 q ) = n = 1 N K M q = 0 M C q ( n M + 1 q ) = 1 × K 1 × × K M + 2 × ( 1 + K 1 ) × × ( 1 + K M ) + + ( N K M ) × ( [ N K M 1 ] + K 1 ) × × ( N 1 ) = n = 1 N K M n ( n + K 1 1 ) ( n + K 2 1 ) ( n + K M 1 ) (1*)

Solve (1*) in a normal way:

Decompose n ( n + K 1 1 ) ( n + K M 1 ) to j = 1 M + 1 D j ( n j ) ? D j = C q , q = M + 1 j

4.1) 1 < K 1 < < K M , 3.1) can decompose n ( n + K 1 1 ) ( n + K M 1 ) to j = 1 M + 1 D j ( n j )

In particular, 1.5) ? C q = ( M + 1 ) ! ( M M q ) ? D j = ( M + 1 ) ! ( M j 1 ) ?

4.2) [ x ] M = M ! M ! ( M 1 M 1 ) [ x ] M + M ! ( M 1 ) ! ( M 1 M 2 ) [ x ] M 1 + + M ! 1 ! ( M 1 0 ) [ x ] 1

4.3) P is a prime number, N ( K M 1 ) = P

1) | S E T ( N , P S , P T 1 ) | = P 1 ,

2) S E T ( N , P S , P T 1 ) = { ( 1 , K 1 , , K M ) , ( 2 , 1 + K 1 , , 1 + K M ) ( P 1 , , N 1 ) }

3) if K M P 1 and P S [ 1 , 2 , , P 1 ] , then S U M _ S U B S E T ( N , P S , P T 1 ) 0 M O D P

[Proof]

| S E T ( N , P S , P T 1 ) | = ( N P H ( P S ) 1 P C H G ( P S , P T 1 ) P B ( P T 1 ) + 1 ) = ( ( P + K M 1 ) ( K M + 1 P B ( P S ) 2 ) 1 P C H G ( P S , P T 1 ) 1 ) P B ( P S ) = P C H G ( P S , P T 1 ) P 1 ( 1 ) ( 2 )

S U M _ S U B S E T ( N , P S , P T 1 ) = q = 0 M C q ( P I D X ( P T 1 ) q )

K M P 1 and P S [ 1 , 2 , , P 1 ] I D X ( P T 1 ) < P ( 3 )

q.e.d.

When K M = P 1 and P S [ 1 , 2 , , P 1 ]

S U M _ S U B S E T ( N , P S , P T 1 ) = 1 × K 1 × × K M + 2 × ( 1 + K 1 ) × × P + 3 × ( 2 + K 1 ) ( 2 + K M 1 ) ( 2 + K M ) + 4 × ( 3 + K 1 ) ( 3 + K M 1 ) ( 3 + K M ) + + ( P 1 ) × ( P 2 + K 1 ) × × ( P 2 + K M )

3 × ( 2 + K 1 ) ( 2 + K M 1 ) ( 2 + K M ) 1 × 3 × ( 2 + K 1 ) ( 2 + K M 1 )

4 × ( 3 + K 1 ) ( 3 + K M 1 ) ( 3 + K M ) 2 × ( 1 + [ 3 ] ) × ( 1 + [ 2 + K 1 ] ) ( 1 + [ 2 + K M 1 ] )

( P 1 ) × ( P 2 + K 1 ) ( P 2 + K M ) ( P 1 ) × ( P 2 + K 1 ) ( P 2 + K M 1 ) ( 2 P 3 ) ( P 4 + [ 1 ] ) ( P 4 + [ 3 ] ) ( P 4 + [ 2 + K 1 ] ) ( P 4 + [ 2 + K M 1 ] )

1 × K 1 × × K M 1 × K 1 × × ( P 1 ) ( P + 1 ) ( P + K 1 ) ( P + P 1 ) ( P 1 ) ( P 2 + 3 ) ( [ P 2 ] + [ 2 + K 1 ] ) ( [ P 2 ] + [ 2 + K M 1 ] )

?

S U M _ S U B S E T ( N , P S , P T 1 ) S U M _ S U B S E T ( N , [ 1 , 3 , 2 + K 1 , ϵ , 2 + K M 1 ] , P T 1 ) M O D P

P S = [ 1 , K 1 K M ] can be slided to [ 1 , 3 , 2 + K 1 , , 2 + K M 1 ] by MOD P

If K M = P 1 and exists K i + 1 K i > 2 , PS can be slided to [ 1 , , X < P 1 ]

If K M = P 1 and not exists K i + 1 K i > 2 , PS must be a Basic Shape, can only be slided to [ 1 , , X = P 1 ]

Define:

A Basic Shape P S = [ 1 , K 1 K M ] = L 1 L 2 L Q , among:

Li = count of continuity. (Li, Li+1) means a discontinuity, there are Q-1 discontinuities.

Example: [ 1 , 3 , 5 ] = 1 , 1 , 1 , [ 1 , 2 , 3 , 5 ] = 3 , 1 , [ 1 , 2 , 4 , 5 ] = 2 , 2

Obvious: L 1 L 2 L Q can been slided to [ L Q , L 1 , L 2 , ] , [ L Q 1 , L Q , L 1 , L 2 , ] ,

4.4) PS is a Basic Shape, I D X ( P S ) = P , P S [ 1 , 2 , , P 1 ] , { P S 1 , P S 2 , } are all shapes that PS can scroll to, then M I N ( P S 1 ) + M I N ( P S 2 ) + 0 M O D P . This is a promotion of 1.6)

[Proof]

3 × ( 2 + K 1 ) ( 2 + K M 1 ) ( 2 + K M ) 1 × 3 × ( 2 + K 1 ) ( 2 + K M 1 ) M O D P

If 2 + K M 1 P , [ 1 , 3 , ( 2 + K 1 ) , , ( 2 + K M 1 ) ] { P S 1 , P S 2 , }

S U M _ S U B S E T ( N , P S 1 , P T 1 ) M I N ( P S 1 ) + M I N ( P S 2 ) + 0 M O D P

q.e.d.

Example:

1 × ( 3 × 4 × 5 ) × ( 7 × 8 ) × 10 + 1 × 3 × ( 5 × 6 × 7 ) × ( 9 × 10 ) + ( 1 × 2 ) × 4 × 6 × ( 8 × 9 × 10 ) + ( 1 × 2 × 3 ) × ( 5 × 6 ) × 8 × 10 = 139260 0 M O D 11

5. Calculation Formula of 1 M + 2 M + 3 M + + N M

Use the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) .

In general, Ki and Kj cannot be exchanged, but when P T = P T 1 = [ 1 , 2 , , M + 1 ] ,

S U M _ S U B S E T ( N , P S , P T 1 ) = q = 0 M C q ( N P H ( P S ) P C H G ( P S , P T 1 ) I D X ( P T 1 ) q )

C q = i = 1 M ( X i + D i ) = choice M q from T ( T D ) choice q from K ( K + D )

Easy to see: choice M q from T ( T D ) = ( M + 1 q ) !

Can prove: ( K 1 , K 2 , , K M ) is permutable in choice q from K ( K + D )

? ( K 1 , K 2 , , K M ) is permutable in the form.

S U M _ S U B S E T ( N , P S , P T 1 ) = q = 0 M A q ( N K M + 1 M + 2 q ) = n = K M + 1 N q = 0 M A q ( n K M M + 1 q ) = 1 × K 1 × × K M + 2 × ( 1 + K 1 ) × × ( 2 + K M ) +

Add one more factor Ki to the end:

1 × K 1 × × K M × K i + 2 × ( 1 + K 1 ) × × ( 1 + K M ) × ( 1 + K i ) + = n = K M + 1 N q = 0 M A q ( n K M M + 1 q ) ( n 1 K M + K i ) = n = K M + 1 N q = 0 M A q ( n K M M + 1 q ) ( [ n K M + 1 ] + [ K i 2 ] ) = n = K M + 1 N q = 0 M { A q ( M + 2 q ) ( n K M + 1 M + 2 q ) + A q ( K i 2 ) ( n K M M + 1 q ) } = q = 0 M A q ( M + 2 q ) ( N K M + 2 M + 3 q ) + q = 0 M A q ( K i 2 ) ( N K M + 1 M + 2 q )

= q = 0 M A q ( M + 2 q ) ( N K M + 1 M + 3 q ) + q = 0 M { A q ( M + 2 q ) + A q ( K i 2 ) } ( N K M + 1 M + 2 q ) = q = 0 M A q ( M + 2 q ) ( N K M + 1 M + 3 q ) + q = 0 M A q ( K i + ( M q ) ) ( N K M + 1 M + 3 ( q + 1 ) )

Let P S 2 = [ 1 , K 1 , , K M , K M + 1 = K i ] ,

P T 2 = [ 1 , T 1 , , T M , T M + 1 ] = [ 1 , 2 , , M + 1 , M + 2 ]

I D X ( P T 2 ) = M + 3 , N P H ( P S 2 ) P C H G ( P S 2 , P T 2 ) = N K M + 1

q = count of { X 1 , , X M } K

A q ( M + 2 q ) = A q ( T M + 1 q ) means X M + 1 = T M + 1 , A q ( K i + ( M q ) ) means X M + 1 = K M + 1

It’s match the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M ) ( T M + 1 + K i )

Recursion ?

5.1) K i < K j , K i = K j , K i > K j are allowed, S U M _ S U B S E T ( N , P S , P T 1 ) can use the form ( T 1 + K 1 ) ( T 2 + K 2 ) ( T M + K M )

Example:

The form = ( 2 + 3 ) ( 3 + 5 ) ( 4 + 3 ) ?

S U M _ S U B S E T ( N , [ 1 , 3 , 5 , 3 ] , [ 1 , 2 , 3 , 4 ] ) = 24 ( N 4 5 ) + 84 ( N 4 4 ) + 102 ( N 4 3 ) + 45 ( N 4 2 )

Among:

45 = 3 × 5 × 3

102 = 3 × 5 × ( 4 2 ) + 3 × ( 3 1 ) × ( 3 + 1 ) + 2 × ( 5 + 1 ) × ( 3 + 1 )

84 = 2 × 3 × ( 3 + 2 ) + 2 × ( 5 + 1 ) × ( 4 1 ) + 3 × ( 3 1 ) × ( 4 1 )

S U M _ S U B S E T ( 9 , [ 1 , 3 , 5 , 3 ] , [ 1 , 2 , 3 , 4 ] ) = 1 × 3 × 3 × 5 + 2 × 4 × 4 × 6 + 3 × 5 × 5 × 7 + 4 × 6 × 6 × 8 = 1914 = 24 ( 5 5 ) + 84 ( 5 4 ) + 102 ( 5 3 ) + 45 ( 5 2 )

The form = ( 2 + 4 ) ( 3 + 7 ) ( 4 + 7 ) ?

S U M _ S U B S E T ( N , [ 1 , 4 , 7 , 7 ] , [ 1 , 2 , 3 , 4 ] ) = 24 ( N 6 5 ) + 126 ( N 6 4 ) + 248 ( N 6 3 ) + 196 ( N 6 2 )

Among:

196 = 4 × 7 × 7

248 = 4 × 7 × ( 4 2 ) + 4 × ( 3 1 ) × ( 7 + 1 ) + 2 × ( 7 + 1 ) × ( 7 + 1 )

126 = 2 × 3 × ( 7 + 2 ) + 2 × ( 7 + 1 ) × ( 4 1 ) + 4 × ( 3 1 ) × ( 4 1 )

S U M _ S U B S E T ( 12 , [ 1 , 4 , 7 , 7 ] , [ 1 , 2 , 3 , 4 ] ) = 1 × 4 × 7 × 7 + 2 × 5 × 8 × 8 + 3 × 6 × 9 × 9 + 4 × 7 × 10 × 10 + 5 × 8 × 11 × 11 = 9934 = 24 ( 6 5 ) + 126 ( 6 4 ) + 248 ( 6 3 ) + 196 ( 6 2 )

In particular:

5.2) n = 1 M n M = S U M _ S U B S E T ( N + 1 , [ 1 , 1 , , 1 ] , [ 1 , 2 , , M ] )

Example:

( N + 1 ) P H ( P S ) P C H G ( P S , P T 1 ) = ( N + 1 ) 0 0 = N + 1

The form = ( 2 + 1 )

? 1 2 + 2 2 + + N 2 = 2 ( N + 1 3 ) + ( N + 1 2 ) = N ( N + 1 ) ( 2 N + 1 ) 6

The form = ( 2 + 1 ) ( 3 + 1 )

? 1 3 + 2 3 + + N 3 = 6 ( N + 1 4 ) + 6 ( N + 1 3 ) + ( N + 1 2 ) = N 2 ( N + 1 ) 2 4

The form = ( 2 + 1 ) ( 3 + 1 ) ( 4 + 1 )

? 1 4 + 2 4 + + N 4 = 24 ( N + 1 5 ) + 36 ( N + 1 4 ) + 14 ( N + 1 3 ) + ( N + 1 2 )

Among:

14 = 2 × ( 1 + 1 ) × ( 1 + 1 ) + 1 × 1 × ( 4 2 ) + 1 × ( 3 1 ) × ( 1 + 1 )

36 = 2 × 3 × ( 1 + 2 ) + 2 × ( 1 + 1 ) × ( 4 1 ) + 1 × ( 3 1 ) × ( 4 1 )

S(M, K) is Stirling number of the second kind,

Definition of S(M, K) ? n = 1 N n M = K = 1 M K ! S ( M , K ) ( N + 1 K + 1 )

It’s equal to 5.2), so we have a way to calculate S(M, K).

3.4) can be seen as n = 1 N ( n + 1 ) n M = S U M _ S U B S E T ( N + 1 , [ 1 , 0 , , 0 ] , [ 1 , 2 , , M + 1 ] )

Cite this paper: Peng, J. (2020) Subset of the Shape of Numbers. Open Access Library Journal, 7, 1-15. doi: 10.4236/oalib.1107040.
References

[1]   Peng, J. (2020) Shape of Numbers and Calculation Formula of Stirling Numbers. Open Access Library Journal, 7, 1-11. https://doi.org/10.4236/oalib.1106081

[2]   Peng, J. (2020) Subdivide the Shape of Numbers and a Theorem of Ring. Open Access Library Journal, 7, 1-14. https://doi.org/10.4236/oalib.1106719

 
 
Top