# Message #1668

From: David Smith <djs314djs314@yahoo.com>

Subject: Re: [MC4D] Goldilock’s function (Some math discussion! Enter at your own risk! :)

Date: Sat, 07 May 2011 14:08:42 -0700

Hi everyone,

I apologize; I had to rush the end of my post. Something unexpected came up and

I had to quickly complete it.

Here are the counts again; there was a typo (7^3 cube):

2^3 cube: 11 moves

3^3 cube: 25 moves

4^3 cube: 43 moves (WCA: 40 moves)

5^3 cube: 63 moves (WCA: 60 moves)

6^3 cube: 85 moves (WCA: 80 moves)

7^3 cube: 108 moves (WCA: 100 moves)

Megaminx: 73 moves (WCA: 70 moves)

The AveNumTwists part of the formula is pretty much set in stone, unless I

someday figure out how to implement puzzles like the starminx. That’s not

high on my list of priorities, however, unless it is eventually needed. As I

mentioned, guesswork comes into play when deciding the factor by which to

multiply AveNumTwists. An intuitive argument suggests that one should add

one factor of AveNumTwists (remember, it estimates the average number of

moves it takes to move each piece once) each time the number of faces doubles

(as then each piece could theoretically travel to the newly created face it resides

next to). When I simply plugged the 3-dimensional puzzles into my formula,

I obtained results that were all what Melinda anticipated: each puzzle, including

the megaminx, was greater than the WCA counts, by about a factor of 1.4. The

megaminx had the greatest deviation from the rest, at 1.5. However, I then realized

that for 3 dimensions, I should adjust the vaule of my formula very slightly: The

final factor should be equal to 2 when the order-3 cube is considered, rather

than 3 as in four dimensions, and the rest of the values should proceed from there.

I performed this calculation, and plugged in the puzzles again. The results were

miraculous: All of the cubes were within a factor of 1.08 (my value divided by WCA’s)

of the values given by the WCA, and in an increasing progression! But, the

megaminx was at a factor of 1.16! This all seemed too remarkable to be a coincidence.

I realized that with the previous base-2 logarithm, I was going on intuition - I had no

sound data of what the values should be, except for our rough approximations with

the 3^4 cube and the 120-cell. What if this was not accurate enough? Then, I

studied my evidence (the WCA values) and realized that if I added 0.5 moves each

time the number of faces doubled (exactly half!), then boom - the megaminx’s value

immediately corresponded with the cubes. In fact, it corresponds as close as I

can possibly get:

4^3 cube: 43 moves (WCA: 40 moves)

5^3 cube: 63 moves (WCA: 60 moves)

Megaminx: 73 moves (WCA: 70 moves)

6^3 cube: 85 moves (WCA: 80 moves)

7^3 cube: 108 moves (WCA: 100 moves)

Incredible! Does anyone believe this is all a coincidence, or have I somehow

stumbled upon a very, very accurate formula?

My goal before was an approximation: I was attempting to find a formula that

gave good values, not worrying too much if I went over, for a reasonably scrambled

puzzle. Now, with this slight modification, I believe I may have found a formula

that gets it almost exactly right, just as Melinda wanted: a value that is not too high,

and not too low. I can’t prove that my new 120-cell count is not too low, but I believe

it is, based on all of the empirical data. I have adjusted for each dimension, so the

math suggests that I may have found the "sweet spot". On the other hand, this

modification was based mostly on the WCA’s counts. They may not be as

accurate as I would like, especially since they are linear and powers of 10. But

the fact that my formula gives values that are so close, even when we change the

shape of the puzzle, seems to be quite remarkable, and not automatically

coincidental. What do any of you think?

To summarize, AveNumTwists is based on established mathematics (but is of course

an approximation). The choice of the last factor is harder to establish with purely

mathematical methods, but appears to give remarkably accurate results in three

dimensions based on the data, and also good values in four dimensions.

And to clarify, I’m not surprised that my formula has worked, but am surprised

that when I simply doubled the logarithm, (not a logarithm with an irrational

base, but twice the value it was previously!) the megaminx fell into a virtually

exact pattern with the cubes. The degree of accuracy seems almost too good

to be true. :)

I look forward to hearing from Melinda and anyone else who wants to comment!

If you’ve read this far, thanks for listening; I appreciate your time and hopefully

was not too chatty today. :)

All the best,

David

— On Sat, 5/7/11, David Smith <djs314djs314@yahoo.com> wrote:

From: David Smith <djs314djs314@yahoo.com>

Subject: Re: [MC4D] Goldilock’s function

To: 4D_Cubing@yahoogroups.com

Date: Saturday, May 7, 2011, 2:30 PM

Hi Melinda and Matt,

Melinda, thanks so much for your positive words and encouragement that I am

an asset to this wonderful community of good people! It sounds like the Android

work is very interesting and fun; good luck with that. It’s certainly very impressive!

Matt, thanks for the welcome! I can explain why the formula did not work for the

starminx. I hadn’t even thought to mention this, which is my fault (and I apologize),

but the formula will only work for puzzles that are sliced ‘normally’. That is to say,

faces are cut evenly, all 1-colored pieces are on the inside of the face and spaced

evenly and according to the shape of the puzzle, etc. The reason why the starminx

is so much larger is that it is built into the formula that order-3 puzzles will have

one 1-colored piece per

face. The fact that there are six per face greatly increases

the first factor of AveNumTwists, which makes the entire count much larger than

it ought to be. My formula does work for all MagicCube4D, 5D and 7D puzzles

however.

Having said this, I did realize this morning that I had jumped to conclusions

when I said the formula works for puzzles of any dimension. I have improved the

formula to account for this, and it turns out to be remarkably accurate. I also

modified the last term, turning a base-2 logarithm into a base-4 logarithm. (I

would consider this an improvement rather than a correction, but anyone can feel

free to disagree! ;) ) I have to admit; which base to choose originally was a bit of

guesswork. It turns out that the base-2 logarithm formula, even when taking into

account the lower number of dimensions, did not work as well for the megaminx

as it did for the

cubes. I realized that if I doubled the base of the logarithm, the

megaminx almost automatically ‘snapped’ into place, again as if by magic. Here

is the revised formula:

__________________________________________________________________

```
<br> Npieces = number of pieces in the puzzle (including<br>
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<br> d = dimension of the puzzle
ln(x) = natural logarithm of x
log4(x) = base 4 logarithm of x = ln(x)/ln(4) =<br>
ln(x)/1.386
```

AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *

(0.577+ln(Npieces))

```
Number of Twists to Scramble (round to nearest integer) =
AveNumTwists * (d-1+log4(Nfaces/(2*d)))
```

__________________________________________________________________

The great thing about this new formula is that all of the 4-dimensional cubes

keep the same value. The simplex becomes 14 moves, and the 120-cell becomes

1783. I believe that both of these counts are accurate. My basis for the base-4

logarithm was from the 3D counts Melinda pointed out to me (thanks Melinda!)

Just see how accurate my formula is in 3 dimensions:

2^3 cube: 11 moves

3^3 cube: 25 moves

4^3 cube: 43 moves (WCA: 40 moves)

5^3 cube: 63 moves (WCA: 60 moves)

6^3 cube: 85 moves (WCA: 80 moves)

4^3 cube: 108 moves (WCA: 100 moves)

Megaminx: 73 moves (WCA: 70 moves)

These counts are remarkably close to the WCA counts, as you can see! I was

very surprised to see that.

I have to go now, but I’ll talk to you all later!

All the best,

David

— On Sat, 5/7/11, Melinda Green

<melinda@superliminal.com> wrote:

From: Melinda Green <melinda@superliminal.com>

Subject: Re: [MC4D] Goldilock’s function

To: 4D_Cubing@yahoogroups.com

Date: Saturday, May 7, 2011, 1:40 AM

```
<br>
<br>
<br>
```

Wow, what a great email, David!! I especially liked your signposts

showing where the scary math begins and ends.

```
I must say this looks *very* promising. The outputs you got for all<br>
the puzzles you tested do indeed sound ideal. I'm not surprised that<br>
the simplex needs fewer than my 1-minute formula gives, and that the<br>
120 Cell needs a lot more--as Andrey has recently shown us. It's<br>
also great that your inputs are values we should either have on hand<br>
or be able to produce without much trouble, and that your equations<br>
are simple enough that I think I can handle it. This is all exactly<br>
what I had hoped for, and if it is not, then I suspect you'll be<br>
able to modify it to be so. Once we've decided this is just right, I<br>
hope that you will describe how you generated your final formula.
Of course this all puts the ball in my court now. I did the Android<br>
port in order to learn Android graphics and to impress potential<br>
employers, but I have a new laptop and have not been looking forward<br>
to setting up source control to work on the desktop version, but I<br>
am now out of excuses and will simply have to just have to do it. <br>
:-D Luckily the timing is good as I've finished all the Android<br>
projects that I set out to build and am not working yet.
BTW, how does your formula do with the official numbers for the 3D<br>
puzzles that Nan referred us to? I imagine that they will err more<br>
on the side of safety than we need, but if your formula reproduces<br>
those numbers multiplied by some constant, that will be even more<br>
evidence that you've gotten it right. In fact that would mean that<br>
you could introduce yet another scalar parameter for that constant<br>
which represents the desired safety margin.
This is very cool, David. Thank you for putting substantial effort<br>
into this problem. Oh, and now do you see why we're glad to have you<br>
back? Actually, your enthusiasm is even more valuable than your math<br>
skills, but I'll very happily take both! :-)
-Melinda
On 5/6/2011 7:45 PM, David Smith wrote:<br>
<br>
<br>
<br>
<br>
<br>
<br>
Hi Melinda (and<br>
everyone else),
I spent most of today working on the Goldilocks function<br>
problem, and believe I
have found a good function that will work! It's a bit<br>
detailed, so I hope that's not a
problem. It's the simplest one I could come up with that<br>
is very well mathematically
justified.
Here is the pseudocode:
Npieces = number of pieces in the puzzle (including<br>
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) =<br>
ln(x)/0.693
```

__________________________________________________________________

```
AveNumTwists = (Npieces*Nfaces/(Nstickers - N1Cpieces)) *<br>
(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<br>
have all of the functions
required (by attempting to create the ordinary Rubik's<br>
cube, which was apparently
BRILLIANT!) except possibly log2 and N1Cpieces. I gave<br>
you a conversion formula
for the former, and I'm betting you have the latter, but<br>
if not it shouldn't be too difficult
to implement.
*** WARNING! MATHEMATICS CONTENT AHEAD! ***
I'll give a brief explanation. It took some<br>
experimentation to arrive at this formula; I
tried many different approaches; this is the one that<br>
really worked. AveNumTwists
counts the average number of twists needed to move every<br>
piece of a puzzle at least
once. (Of course this number will in fact move many pieces<br>
more than once). It should
hopefully be clear that this average number of twists will<br>
provide a well-scrambled
puzzle when applied more than once. The second factor of<br>
AveNumTwists utilizes a
logarithm and the number 0.577, which some of you may<br>
recognize as the gamma
constant. This factor is an approximation of the nth<br>
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<br>
had that as the number of
faces of the puzzle doubles, we need to move every piece<br>
an additional time, by
adding AveNumTwists one more time. Of course, attempting<br>
to move every piece
across the entire puzzle, even via a direct path, would<br>
produce astronomical results
for the 120-cell and other puzzles with a large number of<br>
faces. For the 120-cell,
AveNumTwists is about 7, which sounds right, considering<br>
that even with 10,000
twists you will for all practical purposes never find a<br>
piece on the opposite side of
the puzzle from where it started. (An aside: I proved that<br>
my original idea that the
number of twists needed to randomize the 120-cell could be<br>
in the millions or higher
was correct.) So, I saw that AveNumTwists needs to be<br>
multiplied by the base 2
logarithm of the number of faces of the puzzle (there is<br>
no need to consider the
size of the puzzle here; the number of faces is the<br>
important factor to consider).
*** MATHEMATICS CONTENT HAS CEASED! ***
And as if by magic, when these calculations are performed<br>
we get the expected
values for the 3^4 cube and the 120-cell! Here are the<br>
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<br>
twists for the higher-order
cubes appears to be growing larger that your previous<br>
function was as the order
increases. Also, the number of twists for the order-3<br>
simplex is just over half of the
previous number! I applied 16 twists to the puzzle (by<br>
doing a full scramble and
solving 14 moves), and it did look just as scrambled as<br>
the original 30 twists. The
number for the 120-cell agrees with Andrey's analysis that<br>
1000 twists is not enough
for a good scramble.
Well, what do you think Melinda? Do these numbers look<br>
too large? Hopefully the
calculation isn't too complex; I don't see any way to<br>
simplify it. I am very happy
with how my function turned out, and do believe it is<br>
matheamtically justified,
and so should work for every puzzle. Also, there is<br>
nothing special about 4
dimensions - this function should work for MagicCube5D and<br>
MagicCube7D as
well, if the programmers are interested. Just noting<br>
that!
Melinda, thanks for giving me this nice problem to work<br>
on, and I hope I was
helpful! It was a fun way to spend the day. :) I look<br>
froward to hearing from
you. Until then, have a great weekend everybody!
All the best,
David
```