Matt Parker's "Share the Power" Puzzle

In response to Matt Parker's "Share the Power" puzzle video: https://www.youtube.com/watch?v=E5-pgBnGyzw

The problem is as follows: Sort integers 0 through 31 into two sets of 16 numbers so that each pile, when totalled, results in the same value. Not just for the base numbers, though. They also have to result in the same total if you power every number by 2, 3, and 4. (Watch the video, because Matt Parker's entertaining!)I like mathematics. So I watched this video, and decided I was going to solve it the best way possible: by making a program that randomly checks answers to the problem until it finds the correct solution. Because nothing I do makes sense.

Here is my program. It's made in GameMaker 7, because retro. Here's the entire code, found in one object:

Create event:

//Initialise a list holding values 0 through 31
global.Checklist=ds_list_create();
for(i=0; i<=31; i+=1) ds_list_add(global.Checklist,i);

//Initialise five "report" lists:
//0 = the string of numbers being tested on a given iteration;
//1-4 = the true or false status of the total of n to that power
for(i=0; i<=4; i+=1) {global.Testlist[i]=ds_list_create(); Found[i]=0;}
Iteration=0;

//Turns true if an answer is found
Ended=false;

Step event:

//Stop testing if we found the answer
if( Ended ) exit;

repeat( 200 ){Iteration+=1;

//Clears the top value of the reports when there's over 10 of them
if( ds_list_size(global.Testlist[1])>=10 ){for(j=0; j<=4; j+=1)

//Shuffle the values so we're trying a new one
ds_list_shuffle(global.Checklist);

//Report the actual values from group 1 that we're checking
var str; str="";for(i=0; i<=30; i+=2){str+=string(ds_list_find_value(global.Checklist,i));if( i<30 ) str+=", ";}ds_list_add(global.Testlist[0],str);

//Check the totals for each of n^1 to n^4
p[0]=true; p[1]=true; p[2]=true; p[3]=true; p[4]=true;

for(j=1; j<=4; j+=1) {var pile1; pile1=0; var pile2; pile2=0;for(i=0; i<=30; i+=2)if( pile1!=pile2 ) p[j]=false;

var str;str="FALSE";
if( p[j] ) {str="TRUE"; Found[j]+=1}ds_list_add(global.Testlist[j],str);}

//Terminate the checking next step if we've found the answer

if( p[1]==true && p[2]==true && p[3]==true && p[4]==true )

Draw event:

draw_set_font(font0);
draw_set_halign(fa_left);
draw_set_valign(fa_top);
draw_set_color(c_black);

//Draw the results
for(i=0; i<ds_list_size(global.Testlist[0]); i+=1){draw_text(20,10+(i*50),ds_list_find_value(global.Testlist[0],i));for(j=1; j<=4; j+=1)

draw_text(20+(120),10+(11*50) ,"Iteration")draw_text(20+(120),10+(11*50)+20,string(Iteration))

for(j=1; j<=4; j+=1)
{draw_text(20+((j-1)*120),10+(12*50) ,"n^"+string(j)+" Found")
draw_text(20+((j-1)*120),10+(12*50)+20,string(Found[j]))}

Untitled-25.fw.png

 And that's it! 200 times per step (should be 12,000 per second but it lags because it's compiled with an old GameMaker) it shuffles the numbers into two piles, checks each of n^1 through n^4, and if all four return true for a single set of numbers, bam! Winner!

Well, it would have been if I hadn't, impatiently waiting for my program to spit out the answer in mere minutes, I hadn't googled 32 factorial. If there is only one ordering of the numbers that results in a pass in all four categories and my program was doing one check per second, turns out I'd be sitting here for a few quadrillion millennia  waiting for my mythical answer.

So I altered the code a bit to up the count to 5,000 60 times per second (which is laggy, but y'know...), with it dropping that number if the FPS is too low (which it is).

And as I sit here writing this, the new program is on iteration 5,500,000. It has found a total of 83,000 combinations that work for n^1, but only 8 for n^4. And of course, none that work for all four.Optimisation time!

First, I made the code early-out if any of the tests fail. I then reversed the testing order, so n^4 goes first - since n^4 fails significantly more often, it means less redundant code is run.

And then I realised there was another nice optimisation I'd entirely ignored.If each of the two half-piles of numbers have to total the same, then the total of BOTH piles would be twice that. And since all of the numbers in both piles are set, I could work out this total! So I chucked Excel open and found that:

0^1 through 31^1 = 496;
0^2 through 31^2 = 10416;
0^3 through 31^3 = 246016;
0^4 through 31^4 = 6197520.

So for a valid solution, I only have to check one of the two piles for half of the above values (248, 5208, 123008, 3098760).

By now, the new program is checking over 100 iterations in the time it takes the original to check 1. I was figuring this might be my special way of solving a problem - turns out the profoundly lazy way is also the ridiculously lengthy way!

While it's running, I decide to rewatch the video just in case something lurches out at me. It's at this point I see this:In both of Matt's previous examples, for each eight numbers, the first, fourth, sixth and seventh go into pile one; the other four go into pile two.

Please don't let it be this easy.

I repeated the pattern... n^1 passed, n^2 passed... but n^3 and n^4 were slightly off.That was doing: unnuunnu (assuming in the screen caps above, the upper is "un" and the lower is "unnu"). uunnnnuu made n^3 pass as well, but n^4 still failed.

A real mathematician, at this point, would probably be laughing in my face. I should probably be working this out for real.

But then I found unnunuun.

And all the numbers aligned.

So Matt Parker, if you happen to be reading this,

Set 1: 0, 3, 5, 6, 9, 10, 12, 15, 17, 18, 20, 23, 24, 27, 29, 30
Set 2: 1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31.

I didn't see the pattern you laid out in plain sight. And as a result, I made a piece of software. A piece of software that is both ridiculous and redundant. A piece of software that has gone through 47 million iterations checking random groups of numbers for a solution, and has yet to find a group that satisfies n^4 and n^3, let alone n^2 and n^1.Thank you.And damn you.

ADDENDUM!

I'm still looking at this trying to work out what's going on. I did notice one thing though:

unnunuun

The Us are in positions 0, 3, 5 and 6, and the Ns are in positions 1, 2, 4 and 7, in the final "pattern".

This is exactly the same as the alignment of numbers in the sets themselves. Which is pretty... FRACTAL

Maybe for 0-127 and n^1 to n^6, the answer is unnunuun, where every U is itself an unnunuun and every N is an nuununnu?

My brain hurts.