From cube-lovers-errors@oolong.camellia.org Thu Jun 5 22:52:52 1997 Return-Path: cube-lovers-errors@oolong.camellia.org Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id WAA09134; Thu, 5 Jun 1997 22:52:52 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Date: Thu, 05 Jun 1997 22:50:09 -0400 (EDT) From: Jerry Bryan Subject: Some Face Turn Numbers To: Cube-Lovers Reply-to: Jerry Bryan Message-id: MIME-version: 1.0 Content-type: TEXT/PLAIN; charset=US-ASCII The fact that 10% of Rich Korf's random sample was 16f from Start seemed a little funny, so I did some calculations. At most, about 2.9% of the positions in G are 16f from Start. I am sure that the problem is no more than that the sample size is very small. Here is the calculation of the 2.9% figure. The following table gives the best known results for face turns. The results through depth 7 have been calculated (my message of 19 July 1994). The rest are based on Dan Hoey's recursion formula PH[n] = 6*2*PH[n-1] + 9*2*PH[n-2] for n>2, where PH[n] is the number of face turns which are n moves from Start (Dan's note of 16 Sep 1981). I think it would have been ok to use a branching factor of 13.231 from depth 8 on, but just to be safe I used Dan's formula (the results are essentially the same either way). Hence, we have PH[16] <= 1.47E+18, which is just about 2.9% of |G|. d # b Sigma # 0 1 1 1 18 18 19 2 243 13.500 262 3 3240 13.333 3502 4 43239 13.345 46741 5 574908 13.296 621649 6 7618438 13.252 8240087 7 100803036 13.231 109043123 8 1.35E+09 13.360 1.46E+09 9 1.80E+10 13.347 1.94E+10 10 2.40E+11 13.349 2.59E+11 11 3.20E+12 13.348 3.46E+12 12 4.28E+13 13.348 4.62E+13 13 5.71E+14 13.348 6.17E+14 14 7.62E+15 13.348 8.24E+15 15 1.02E+17 13.348 1.10E+17 16 1.36E+18 13.348 1.47E+18 17 1.81E+19 13.348 1.96E+19 18 2.42E+20 13.348 2.61E+20 Now, I am going to do something strange. I am going to assume as per Rich's results that the branching factor from 16f to 17f is 3, and from 17f to 18f is 2 (Rich found 1 position at 16f, 3 at 17f, and 6 at 18f). Doing so yields the following unhappy result (the total positions are less than |G| which is about 4.3E+19). 17 4.07E+18 3.000 5.54E+18 18 8.14E+18 2.000 1.37E+19 If we assume the 16f position was an accident (occurred more than three times too often, which is not surprising with the small sample size), we can suppose the branching factor does not break until going from 17f to 18f, and we get the following. 17 1.81E+19 13.348 1.96E+19 18 3.62E+19 2.000 4.23E+20 It's just totally a wild guess, but I would suspect that the correct numbers are closer to the following because I don't think the branching factor will collapse all at one depth. 17 6.79E+18 5.000 8.25E+18 18 3.39E+19 5.000 4.22E+19 I am a little shy of |G| with this guess, but I am not too far off. What we need is a larger sample. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us Pellissippi State (423) 539-7198 10915 Hardin Valley Road (423) 694-6435 (fax) P.O. Box 22990 Knoxville, TN 37933-0990