meditationatae

Just another WordPress.com site

Number partition problem discussed in sci.math

I recently got interested in the Number Partition Problem in complexity theory, in theoretical computer science.

The general case can be described in the following story:
Someone has five, ten, 15, 20 or more index cards, with each index card carrying an integer greater or equal to zero. Suppose the man or woman wants to separate the, say, 20 index cards into two piles called Pile A and Pile B, so a to get the total of the numbers on the index cards in Pile A as close as possible to the total of the numbers on the index cards in Pile B…
What are good ways to proceed?
The measure of “good fit” for an arrangement of the 20 cards into Piles A and Piles B is simply the difference between the total of the numbers on index cards in Pile A , and the total of the numbers on index cards in Pile B, in absolute value.

The particular problem I got interested in arises from considering the succesive blocks of 5 digits in the decimal expansion of pi, after the decimal point, as corresponding in an obvious way to a sequence of non-negative integers between 0 and 99,999 .
I asked: How many of these consecutive blocks do we need, starting with the block 14159 , so that we can make two columns A, and B from the numbers, using eahc block once and only once, so that the totals in Columns A and B are the same, for the right arrangement/partition?

I managed to do it using the first 20 blocks of 5 digits from pi, and the solution can be described by putting positive or negative signs in front of the 20 numbers; the result of this combination of additions and subtractions turns out to be zero:

Witness:

? 14159-26535+89793+23846-26433-83279+50288-41971+69399+37510+58209+74944-59230-78164+6286-20899-86280+34825+34211-70679

%4 = 0

// Computation done using the PARI gp Calculator.

For reference, the sci.math newsgroup discussion thread can be found at Drexel University’s Math Forum at the Url copied below:

http://mathforum.org/kb/message.jspa?messageID=9887564

In one of the sci.math articles in the discussion thread, Richard Tobin gave the number of essentialy different solutions using block counts N varying from 1 to close to 84. What is meant by essentially different is that by inverting all signs in a solution, we agree that the resulting solution is “essentially the same”. It turns out that for a block count of N = 20, there is essentially a unique solution (see PARI/gp input and output above).

Richard Tobin’s computational data is at the URL below:

http://mathforum.org/kb/message.jspa?messageID=9888284

I used the data provided by Richard Tobin to plot the number of solutions as a function of the block count N; values of the block count N for which no solution giving a total of zero exists are expurgated, so that we can put the number of solutions on a logarithmically scaled Y-axis.

Figure drawn based on Tobin’s computations appears below:

pipartRT

Number of solutions as a function of the block count N . Credit: Richard Tobin

 

====================================

added March 24 2016:

 

I used my computer and the PARI/gp calculator to find a solution for an analogous problem where, instead of 5-digit blocks from Pi, we use 7-digit blocks.

In the sci.math newsgroup thread I mentioned above in this blog post, Richard Tobin has already given a number of essentially different solutions using a block count of N = 28.

I’ll give the solution I found for 7-digit blocks and a block count of N = 28 both as a string of signed numbers on one line, and as a column of signed numbers:

1415926-5358979+3238462+6433832+7950288-4197169+3993751- 582097-4944592-3078164- 628620-8998628- 348253-4211706-7982148- 865132+8230664-7093844+6095505-8223172+5359408+1284811+1745028-4102701+9385211+ 555964-4622948+9549303

= 0.

 

 

and:

 

1415926

-5358979

+3238462

+6433832

+7950288

-4197169

+3993751

– 582097

-4944592

-3078164

– 628620

-8998628

– 348253

-4211706

-7982148

-865132

+8230664

-7093844

+6095505

-8223172

+5359408

+1284811

+1745028

-4102701

+9385211

+ 555964

-4622948

+9549303

=======================

0

Advertisements

Written by meditationatae

March 24, 2016 at 8:21 am

Posted in History

%d bloggers like this: