Amount of permutations on an NxNxN Rubik's Cube

Question

Introduction:

A 3x3x3 Rubik's Cube has \$43,252,003,274,489,856,000\$ possible permutations, which is approximately 43 quintillion. You may have heard about this number before, but how is it actually calculated?

A 3x3x3 Rubik's Cube has six sides, each with nine stickers. Looking at the (external) pieces instead of stickers however, we have six center pieces; eight corners pieces; and twelve edge pieces. Since the centers can't be moved, we can ignore those in the calculations. As for the corners and edges:

• There are \$8!\$ (\$40,320\$) ways to arrange the eight corners. Each corner has three possible orientations, although only seven (of the eight) can be oriented independently; the orientation of the eighth/final corner depends on the preceding seven, given \$3^7\$ (\$2,187\$) possibilities.
• There are \$\frac{12!}{2}\$ (\$239,500,800\$) ways to arrange the twelve edges. The halve from \$12!\$ is because edges must always be in an even permutation exactly when the corners are. Eleven edges can be flipped independently, with the flip of the twelfth/final edge depending on the preceding eleven, given \$2^{11}\$ (\$2,048\$) possibilities.

Putting this together, we have the following formula:

$$8!×3^7×\frac{12!}{2}×2^{11} = 43,252,003,274,489,856,000$$

^{Source: Wikipedia - Rubik's Cube Permutations}

Although this may already look pretty complex, it's still rather straight-forward for a 3x3x3 Cube. For even cubes the formula is slightly different; this is the formula for a 4x4x4 Cube for example:

$$\frac{8!×3^7×24!^2}{24^7} = 7,401,196,841,564,901,869,874,093,974,498,574,336,000,000,000$$

Which is approximately 7.40 quattuordecillion on the short scale.

And for larger NxNxN Cubes (i.e. the current World Record 33x33x33) the formula will be extended quite a bit. To not make this introduction too long however, I put these links here instead, where the permutations of the 4x4x4 Cube and some other sized NxNxN Cubes are explained with a resulting formula:

• 2x2x2
• 4x4x4
• 5x5x5
• 6x6x6
• 7x7x7
• 33x33x33

You may be wondering by now: is there a general formula based on \$N\$ for any \$N\$x\$N\$x\$N\$ Cube? There certainly is. Here are three completely different algorithms, all giving the exact same results based on \$N\$:

1: Chris Hardwick's Formula:

$$\frac{(24×2^{10}×12!)^{N\pmod2}×(7!×3^6)×(24!)^{\lfloor{\frac{1}{4}×(N^2-2×N)}\rfloor}}{(4!)^{6×\lfloor{\frac{1}{4}×(N-2)^2}\rfloor}}$$

Try it on WolframAlpha.

2: Christopher Mowla's trig Formula:

$$8!×3^7×\left(\frac{24!}{(4!)^6}\right)^{\frac{1}{4}×((N-1)×(N-3)+\cos^2(\frac{N×\pi}{2}))}×(24!)^{\frac{1}{2}×(N-2-\sin^2(\frac{N×\pi}{2}))}×(12!×2^{10})^{\sin^2(\frac{N×\pi}{2})}×\frac{1}{24^{\cos^2(\frac{N×\pi}{2})}}$$

Try it on WolframAlpha.

3: Christopher Mowla's primes Formula:

$$2^{\frac{1}{2}×(2×N×(N+7)-17-11×(-1)^N)}×3^{N×(N+1)+2}×5^{\frac{1}{2}×(2×N×(N-2)+1+(-1)^N)}×7^{\frac{1}{8}×(6×N×(N-2)+3+5×(-1)^N)}×11^{\frac{1}{4}×(2×N×(N-2)-1+(-1)^N)}×96577^{\frac{1}{8}×(2×N×(N-2)-3+3×(-1)^N)}$$

where \$96577\$ is \$(13×17×19×23)\$.

Try it on WolframAlpha.

^{Source: Cubers-reddit - Mathematical Counting Formulas of Number of Positions, God's Number, etc.}

Challenge:

Choose and implement one of these three formulas (or your own derivative), which given an input-integer \$N\$ in the range \$[2,100]\$, outputs the correct result.

Challenge rules:

• You are free to use another formula besides these three, but keep in mind that these three are proven to be correct. If you use another formula, please add a link of where you got it from (or if you come up with it yourself add an in-depth explanation). And I will check for all integers in the range if the output is correct. Perhaps inspiration could be found in the oeis for this sequence: A075152.
• If your language automatically outputs a scientific output (i.e. \$1.401...×10^{45}\$ instead of the number after the 4x4x4 formula) this is allowed. But please add additional code to your answer to convert this scientific rounding to an exact output so the results can be verified, since rounding errors due to floating point precision during the execution of the formula in your code is not allowed - the actual result should be exact.
• Your program/function should be correct for at least the inputs in the range \$[2,100]\$ (although, since \$N=100\$ already results in a huge-ass number, any larger \$N\$ will probably work as well if you're able to output this one correctly).
• You are not allowed to loop over all possible permutations with a counter, since that would never output anything in a reasonable amount of time. Only the implementation of a formula (either one of the three provided, a derivative of one of those, or a completely new formula), or another method that will give the correct results in a reasonable amount of time (without hard-coding of course) is allowed. I thought about adding a restricted-time to enforce this, but I'm personally against restricted-time in combination with code-golf, so I won't. Still, please make sure your program gives the answers, and if it's too slow for TIO for some reason, add some screenshots with the output from your local machine as verification.

General rules:

• This is code-golf, so shortest answer in bytes wins.
  Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
• Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
• Default Loopholes are forbidden.
• If possible, please add a link with a test for your code (i.e. TIO).
• Also, adding an explanation for your answer is highly recommended.

Test cases:

Here the test cases for \$N\$ in the range \$[2,10]\$ (feel free to use the WolframAlpha links above for larger test cases):

n=2
3674160

n=3
43252003274489856000

n=4
7401196841564901869874093974498574336000000000

n=5
282870942277741856536180333107150328293127731985672134721536000000000000000

n=6
157152858401024063281013959519483771508510790313968742344694684829502629887168573442107637760000000000000000000000000

n=7
19500551183731307835329126754019748794904992692043434567152132912323232706135469180065278712755853360682328551719137311299993600000000000000000000000000000000000

n=8
35173780923109452777509592367006557398539936328978098352427605879843998663990903628634874024098344287402504043608416113016679717941937308041012307368528117622006727311360000000000000000000000000000000000000000000000000

n=9
14170392390542612915246393916889970752732946384514830589276833655387444667609821068034079045039617216635075219765012566330942990302517903971787699783519265329288048603083134861573075573092224082416866010882486829056000000000000000000000000000000000000000000000000000000000000000

n=10
82983598512782362708769381780036344745129162094677382883567691311764021348095163778336143207042993152056079271030423741110902768732457008486832096777758106509177169197894747758859723340177608764906985646389382047319811227549112086753524742719830990076805422479380054016000000000000000000000000000000000000000000000000000000000000000000000000000000000

NOTE: Since this is a code-golf challenge, it basically boils down to: implement one of these three formulas (or a derivative / your own method that still produces the correct results) as short as possible.

Answer 1

Wolfram Language (Mathematica), 59 bytes

f@n_:=(s=24^6)(24!/s)^(m=n-2)f@m
f@2=7!3^6
f@3=4!12!2^10f@2

Try it online!

uses Herbert Kociemba's algorithm found in OEIS page

here is the recursive formula:
a(1)=1; a(2)=7!*3^6; a(3)=8!*3^7*12!*2^10; a(n)=a(n-2)*24^6*(24!/24^6)^(n-2)

6 bytes saved by @Peter Taylor

one more byte saved by @Expired Data

Answer 2

x86 machine code, 119 bytes

Hexdump:

60 c6 02 02 33 db be 25 01 10 00 f6 c1 01 74 05
be 26 2a b2 36 33 ed 51 b1 06 33 ff 53 8a 04 1a
f6 e1 03 c7 b5 0a f6 f5 88 64 1a 02 66 98 8b f8
4b 79 ea 5b 43 43 f6 f5 66 89 02 84 c0 75 0c 60
8b fa 8d 72 01 8b cb f3 a4 61 4b 41 d1 ee 72 ca
75 f9 be 1d d4 0d 10 4d 79 be 59 49 49 8b e9 be
06 02 02 22 83 f9 02 73 ae c6 44 1a 01 00 80 0c
1a 30 4b 79 f9 61 c3

The function receives the number n in ecx, and a pointer to a string to fill in edx (i.e. fastcall convention).

Before I show the source code, some explanations on how it does the thing. It uses the recursive formula, which I wrote in the following way:

init = 2
m1 = 24^6 = 6*8*9*16*24*32*36
m2 = 24!/24^6 = 6*7*9*10*11*17*19*21*22*23*25*26*35
num(2) = init * 6*7*9*12*15*27
num(3) = init * 6*8*9*12*16*18*20*24*27*28*30*32*33*35*36
num(n+2) = num(n) * m1 * m2^n

So all the code should do is multiplication by small numbers. The numbers are in the range 6...36, which is small enough to be represented in a 32-bit bitmap. I actually don't store the bit which represents multiplication by 6 - this lets me arrange the code in a do-while loop, starting with unconditional multiplication by 6.

The big numbers are represented using decimal form - each byte is a value in the range 0...9, starting from the MSB.

The multiplication is performed from LSB to MSB; it assumes that the number of digits will grow by 2 for each multiplication. After doing multiplication by a small factor like 6, the number of digits may grow by only 1. So if MSB = 0, it moves the whole intermediate result left. It can actually happen that the number of digits doesn't grow at all, and then MSB will still be 0, but this problem will fix itself as the code proceeds to greater factors.

Because the multiplication code is large, I don't want to put it twice. I don't want to move it to a function either, because the machine code for calling a function is large. So I rearranged the outer loops in such a way that the multiplying code is needed only once.

C code:

void num(int n, char* x)
{
    *x = 2;
    int len = 1;
    int exp_i;
    uint32_t m32_1;
    int m1;
    int carry;
    int temp;
    int str_i;
    bool cf;

    if (n % 2 == 0)
    {
        m32_1 = 0x100125; // 6*7*9*12*15*27
    }
    else
    {
        m32_1 = 0x36b22a26; // 6*8*9*12*16*18*20*24*27*28*30*32*33*35*36
    }

    exp_i = 0;
    while (true)
    {
        for (; exp_i >= 0; --exp_i)
        {
            m1 = 6;
            cf = true;
        do_mult:
            carry = 0;
            for (str_i = len - 1; str_i >= 0; --str_i)
            {
                temp = x[str_i] * m1 + carry;
                x[str_i + 2] = temp % 10;
                carry = temp / 10;
            }
            len += 2;
            x[1] = carry % 10;
            carry /= 10;
            x[0] = carry;
            if (carry == 0)
            {
                --len;
                for (str_i = 0; str_i < len; ++str_i)
                    x[str_i] = x[str_i + 1];
            }

        shift_m1:
            ++m1;
            cf = m32_1 & 1;
            m32_1 >>= 1;
            if (cf)
                goto do_mult;
            if (m32_1)
                goto shift_m1;

            m32_1 = 0x100dd41d; // 24!/24^6 = 6*7*9*10*11*17*19*21*22*23*25*26*35
        }
        --n;
        --n;
        exp_i = n;
        if (n < 2)
            break;
        m32_1 = 0x22020206; // 24^6

    }
    x[len] = 0;
    for (str_i = len - 1; str_i >= 0; --str_i)
    {
        x[str_i] += '0';
    }
}

Disassembly:

60                     pushad;
C6 02 02               mov byte ptr [edx], 2; // edx = x
33 DB                  xor ebx, ebx; // ebx = len - 1
BE 25 01 10 00         mov esi, 0x100125; // esi = m32_1
F6 C1 01               test cl, 1;
74 05                  jz skip1;
BE 26 2A B2 36         mov esi, 0x36b22a26; // esi = m32_1
                   skip1:
33 ED                  xor ebp, ebp; // ebp = exp_i

                   loop_n:

51                     push ecx;
                   loop_exp_i:
B1 06                  mov cl, 6; // cl = m1
                   do_mult:
33 FF                  xor edi, edi; // edi = carry
53                     push ebx; // ebx = str_i
                   loop_str_i:
8A 04 1A               mov al, [edx + ebx];
F6 E1                  mul cl;
03 C7                  add eax, edi;
B5 0A                  mov ch, 10;
F6 F5                  div ch;
88 64 1A 02            mov [edx + ebx + 2], ah;
66 98                  cbw;
8B F8                  mov edi, eax;
4B                     dec ebx;
79 EA                  jns loop_str_i;

5B                     pop ebx; // ebx = len - 1
43                     inc ebx;
43                     inc ebx;
F6 F5                  div ch;
66 89 02               mov [edx], ax;

84 C0                  test al, al;
75 0C                  jnz skip2;

60                     pushad;
8B FA                  mov edi, edx;
8D 72 01               lea esi, [edx + 1];
8B CB                  mov ecx, ebx;
F3 A4                  rep movsb;
61                     popad;
4B                     dec ebx;
                   skip2:

                   shift_m1:
41                     inc ecx;
D1 EE                  shr esi, 1;
72 CA                  jc do_mult;
75 F9                  jnz shift_m1;

BE 1D D4 0D 10         mov esi, 0x100dd41d;

4D                     dec ebp;
79 BE                  jns loop_exp_i;

59                     pop ecx; // ecx = n
49                     dec ecx;
49                     dec ecx;
8B E9                  mov ebp, ecx;
BE 06 02 02 22         mov esi, 0x22020206;
83 F9 02               cmp ecx, 2;
73 AE                  jae loop_n;

C6 44 1A 01 00         mov byte ptr [edx + ebx + 1], 0;
                   loop_to_ascii:
80 0C 1A 30            or byte ptr [edx + ebx], '0';
4B                     dec ebx;
                       dec         ebx  
79 F9                  jns loop_to_ascii;

61                     popad;
C3                     ret;

The running time for n = 100 is about 4 seconds, and the result is a number with 38416 digits:

23491019577617 (many digits here) ... (many zeros here) 0000000000000000

Answer 3

05AB1E, 38 bytes

Initial attempt.
Uses Chris Hardwick's Formula.
Will attempt to golf further and explain when I have time.

24©To12!PIÉm7!729®!InI·-4÷mP®IÍn4÷6*m÷

Try it online!

Answer 4

Julia 1.0, 83 76 bytes

n->^(24576*~12,n%2)*3^6*~7(~24)^((m=n-2)n÷4)/24^(m^2÷4*6)
~n=prod(big,1:n)

Try it online!

Uses Chris Hardwick's Formula. Takes input as Big integer.

Thanks to H.PWiz for -7 bytes

Answer 5

Python 2, 72 bytes

lambda n:3674160*61600**(n%2)*24**(~-n/2*6)*0xb88d4641131f0**(n*(n-2)/4)

Try it online!

Saved 4 bytes by copying n*(n-2)/4 from Neil.

Answer 6

Wolfram Language (Mathematica), 67 bytes

Using Chris Hardwick's Formula.

(12!24576)^Mod[#,2]7!729(24!)^⌊#(#-2)/4⌋/24^(6⌊(#-2)^2/4⌋)&

Try it online!

Answer 7

JavaScript (Node.js), 81 bytes

Herbert Kociemba's recursive formula. Takes a BigInt as input.

f=n=>[1n,3674160n,322252536375n<<27n][--n]||f(--n)*0xb640000n*0xb88d4641131f0n**n

Try it online!

---

JavaScript (Node.js),  102 98  96 bytes

Chris Hardwick's formula. Takes a BigInt as input.

n=>(n&1n?1403325n<<25n:4n)*918540n*0x83629343d3dcd1c00000n**(n*n-n-n>>2n)/24n**(6n*(n*n/4n-~-n))

Try it online!

Answer 8

JavaScript (Node.js), 77 75 73 bytes

n=>0xb88d4641131f0n**(n*(n-2n)/4n)*13824n**n*851558400n**(n%2n)*315n>>14n

Try it online! Based on Christopher Mowla's formula. Takes a BigInt as input. Test harness shamelessly stolen from @Arnauld. 0xb88d4641131f0n is 3246670537110000n in decimal. Explanation: I started with the last prime exponent and simplified it to n*(n-2n)/4n (this is integer division, so I don't need the adjustment for odd numbers). I then examined the other primes to see whether their exponents were related to this value (which I shall refer to as o), and found that they were after a fashion, if I allowed the use of the parity of n (which I shall refer to as p). The formulae for the exponents are as follows:

23:       o
19:       o
17:       o
13:       o
11:      2o +   p
 7:      3o +   p +  1
 5:      4o +  2p +  1
 3: 3n + 4o +  3p +  2
 2: 9n + 4o + 14p - 14

The powers can then be grouped by exponent so for example p is the exponent of 11*7*5**2*3**3*2**14.

Answer 9

Racket, 151 141 bytes

-7 bytes thanks to fede s.!

(λ(n[e expt])(/(*(e 11771943321600(modulo n 2))3674160(e 620448401733239439360000(floor(/(*(- n 2)n)4))))(e 24(*(floor(/(sqr(- n 2))4))6))))

Try it online!

The longest answer using Chris Hardwick's Formula :)

Answer 10

Python 2, 122 bytes

import math
f=math.factorial
x=lambda n:(1,f(7)*729,f(8)*3**7*f(12)*1024)[n-1]if n<4else x(n-2)*24**6*(f(24)/24**6)**(n-2)

Try it online!

Uses the Herbert Kociemba recursive method.

-2 bytes thanks to Herman L

Answer 11

Jelly,  39  38 bytes

^{I feel like I've missed some golfs, but...}

12!×⁽^K*Ḃɓ_2×ṭ¥⁸:4×1,6“ð¥‘!¤*:/ד9Ḟɠ’×

A monadic Link implementing Chris Hardwick's Formula.

Try it online! Or see the test-suite (n=[1..33]).

Answer 12

CJam (47 bytes)

qi[1_7m!Z6#*_3*Cm!*2D#*]{2-_j24_m!\6#:P/@#*P*}j

Online demo

This implements Herbert Kociemba's recursion from OEIS: $$a(n) = \begin{cases} 1 & \textrm{ if } n \in \{0,1\} \\ 7! \times 3^6 & \textrm{ if } n=2 \\ a(n-1) \times 3\times 12!\times 2^{13} & \textrm{ if } n=3 \\ a(n-2) \times \left(\frac{24!}{24^6}\right)^{n-2} \times 24^6 & \textrm{ if } n>3 \end{cases}$$ using CJam's memoised recursion operator j. I've ordered the terms in the MathJax block in the same order as in the code to make the correspondence easy to verify for those who read CJam: any further dissection is not going to shed more light.

Answer 13

Icon, 125 110 bytes

procedure f(n)
q:=1;every q*:=1 to 24
return 11771943321600^(n%2)*5040*3^6*q^(n*(t:=n-2)/4)/24^(6*(t^2/4))
end

Try it online!

Answer 14

Jelly, 43 bytes

_2²:4×6*@24
²_Ḥ:4;ḂU
“€ð‘!×⁽^K,1*ÇPד9Ḟɠ’:Ñ

Try it online!

Answer 15

C (gcc) -lgmp, 279 bytes

#include "gmp.h"
#define s mpz_init_set_str
#define m(X)mpz_##X
f(int N,m(t)_){m(t)x;m(init)(x);m(init_set_str)(_,N&1?"3LFbOUwC":"1",62);m(mul_si)(_,_,3674160);m(fac_ui)(x,24);m(pow_ui)(x,x,(N*N-2*N)/4);m(mul)(_,_,x);m(set_si)(x,24);N-=2;m(pow_ui)(x,x,6*N*N/4);m(tdiv_q)(_,_,x);}

Try it online!

Answer 16

Perl 6, 85 bytes

{0xAB4DE800000**($_%2)*3674160*([*] 1..24)**($_*($_-2)div 4)/24**(($_-2)**2 div 4*6)}

Try it online!

Answer 17

Haskell, 86 85 74 bytes

^{-1 byte saved thanks to H.PWiz
-11 bytes saved thanks to Max Yekhlakov}

a=24^6
r 2=3674160
r 3=r 2*a*61600
r n=r(n-2)*a*div(product[2..24])a^(n-2)

Try it online!

Answer 18

TI-BASIC, 63 62 bytes, (noncompeting)

{fPart(.5Ans),1,1,-6}int(4⁻¹{8,4,Ans²-2Ans,(Ans-2)²:prod({9*11!2^15,7!3^6,24!,24}^Ans

Expression which takes input as an integer on Ans. Implementation of Chris Hardwick's formula. Noncompeting because the hardware it runs on will only store up to 16 decimal places, so the answer will never be 100% accurate.

Explanation:

{fPart(.5Ans),1,1,-6}              # the list {(N (mod 2))/2,1,1,-6}
                                   # implicitly multiplied by
int(4⁻¹{8,4,Ans²-2Ans,(Ans-2)²     # the list {2,1,⌊¼(N²-2N)⌋,⌊¼(N-2)²⌋}
:                                  # store this list of the formula's exponents as Ans
     {9*11!2^15,7!3^6,24!,24}      # list of the formula's bases
                             ^Ans  # raised to their exponents
prod(                              # multiplied together
                                   # implicit print

Answer 19

Python 2, 92 bytes

lambda n:0xab4de800000**(n%2)*3674160*0x83629343d3dcd1c00000**(n*(n-2)/4)/24**((n-2)**2/4*6)

Try it online!

Answer 20

Husk, 51 48 44 bytes

-4 bytes thanks to H.PWiz

÷^*6÷4□-2⁰Π4*^÷4-D⁰□⁰Π24*729*Π7^%2⁰*24576Π12

Try it online!

This is Chris Hardwick's Formula. Also, this is my first husk program, so any tips would be well appreciated.

Answer 21

C++, 187 185 180 176 195(there was a bug) 193 175 bytes (with help from ceiling cat)

This uses the GMP C++ wrapper (GNU multi-precision library), and the formula used by @J42161217 (https://codegolf.stackexchange.com/a/183381/55953).

Use g++ -g rubix.cpp -lgmp -lgmpxx to compile and link

#include <gmpxx.h>
#define R return
using z=mpz_class;z p(z a,z b){z c=1;while(b--)c*=a;R c;}z r(z n){if(n==2)R 3674160;if(n==3)R z("pX4dIaR7jDk",62);R r(n-2)*p(24,6)*p(z("ErvSErbeq",62),n-2);}

ungolfed, with test code

#include <gmpxx.h>
#include <iostream>
mpz_class p(mpz_class a, mpz_class b) // returns a to power of b. Only works for b  = positive integer
{
    mpz_class c=1;

    while(b--)
        c*=a;

    return c;
}


mpz_class r(mpz_class n) // returns the rubix permutations for a cube of size n
{
    if(n==2)
        return 3674160; // 7!*3^6;

    if(n==3)
        return z("pX4dIaR7jDk",62); // 43252003274489856000 = 8!*3^7*12!*2^10

    return r(n-2) * p(24,6) * p(z("ErvSErbeq", 62), n-2);

    // "ErvSErbeq"base 62 = 3246670537110000 = (24!/24^6)        
}    

main()
{
    for(int i=2; i<34; i++)
        std::cout<<i<<'\t'<<r(i) << std::endl;
}

https://tio.run/##PZAxb4MwEIV3foWVDrETqBpARMImWZqha7t0iFQZ4xC3xrg2tJERf73UIVXfcE937zvpdEzrqGZsmu6EYrKvOKkbfbncn3dBb4WqgSsa7d6YpNZiBzR0gIYOlGhwgBUb/H0WksMyihBbFRQb3vVGAYZHB4xnFRr@Rqoo4n2SbdNN9pD7Jtk7uNCvafVEn7fvjx@LMItRbqCKYrTSME7D7OoeOpivl4Mp@eeMhFcAj//3AiJa2xlOm13QUKEgCoYAeJ1aA4XqgChiDARJUl/XazRnXrar8py1fUeIIGR57JaE@AUECLllXFUSB2Mw/bCTpLWdIjm/5ua/