# Message #1663

From: David Smith <djs314djs314@yahoo.com>

Subject: Goldilock’s function

Date: Fri, 06 May 2011 19:45:21 -0700

Hi Melinda (and everyone else),

I spent most of today working on the Goldilocks function problem, and believe I

have found a good function that will work! It’s a bit detailed, so I hope that’s not a

problem. It’s the simplest one I could come up with that is very well mathematically

justified.

Here is the pseudocode:

Npieces = number of pieces in the puzzle (including 1-colored pieces)

Nfaces = number of faces in the puzzle

Nstickers = number of stickers in the puzzle

N1Cpieces = number of 1-colored pieces in the puzzle

ln(x) = natural logarithm of x

log2(x) = base 2 logarithm of x = ln(x)/ln(2) = ln(x)/0.693

__________________________________________________________________

AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) * (0.577+ln(Npieces))

Number of Twists to Scramble (round to nearest integer) =

AveNumTwists * log2(Nfaces)

__________________________________________________________________

Hopefully that’s complex enough! ;) I observed that you have all of the functions

required (by attempting to create the ordinary Rubik’s cube, which was apparently

BRILLIANT!) except possibly log2 and N1Cpieces. I gave you a conversion formula

for the former, and I’m betting you have the latter, but if not it shouldn’t be too difficult

to implement.

*** WARNING! MATHEMATICS CONTENT AHEAD! ***

I’ll give a brief explanation. It took some experimentation to arrive at this formula; I

tried many different approaches; this is the one that really worked. AveNumTwists

counts the average number of twists needed to move every piece of a puzzle at least

once. (Of course this number will in fact move many pieces more than once). It should

hopefully be clear that this average number of twists will provide a well-scrambled

puzzle when applied more than once. The second factor of AveNumTwists utilizes a

logarithm and the number 0.577, which some of you may recognize as the gamma

constant. This factor is an approximation of the nth harmonic number (sum of the

first n terms in the harmonic series) for n = Npieces.

The last term of the final calculation uses the insight I had that as the number of

faces of the puzzle doubles, we need to move every piece an additional time, by

adding AveNumTwists one more time. Of course, attempting to move every piece

across the entire puzzle, even via a direct path, would produce astronomical results

for the 120-cell and other puzzles with a large number of faces. For the 120-cell,

AveNumTwists is about 7, which sounds right, considering that even with 10,000

twists you will for all practical purposes never find a piece on the opposite side of

the puzzle from where it started. (An aside: I proved that my original idea that the

number of twists needed to randomize the 120-cell could be in the millions or higher

was correct.) So, I saw that AveNumTwists needs to be multiplied by the base 2

logarithm of the number of faces of the puzzle (there is no need to consider the

size of the puzzle here; the number of faces is the important factor to consider).

*** MATHEMATICS CONTENT HAS CEASED! ***

And as if by magic, when these calculations are performed we get the expected

values for the 3^4 cube and the 120-cell! Here are the values I have computed so

far:

3^4 cube: 46 twists

4^4 cube: 78 twists

5^4 cube: 115 twists

order-3 simplex: 16 twists

order-3 120-cell: 2487

Here are some interesting observations: The number of twists for the higher-order

cubes appears to be growing larger that your previous function was as the order

increases. Also, the number of twists for the order-3 simplex is just over half of the

previous number! I applied 16 twists to the puzzle (by doing a full scramble and

solving 14 moves), and it did look just as scrambled as the original 30 twists. The

number for the 120-cell agrees with Andrey’s analysis that 1000 twists is not enough

for a good scramble.

Well, what do you think Melinda? Do these numbers look too large? Hopefully the

calculation isn’t too complex; I don’t see any way to simplify it. I am very happy

with how my function turned out, and do believe it is matheamtically justified,

and so should work for every puzzle. Also, there is nothing special about 4

dimensions - this function should work for MagicCube5D and MagicCube7D as

well, if the programmers are interested. Just noting that!

Melinda, thanks for giving me this nice problem to work on, and I hope I was

helpful! It was a fun way to spend the day. :) I look froward to hearing from

you. Until then, have a great weekend everybody!

All the best,

David