badmephisto
Veteran
I call upon fellow computer scientists here, I think I came up with a proof of reducibility for division test by 6 for base 10 numbers up to 8 digits long to solving the Rubik's cube, in linear time. yes I was bored today. I wanted to double check my results here with someone before publishing. (ROFL yea right haha)
anyway, i thought it was pretty cool.
let D6 = {x| x is base10, up to 8 digits long and divisible by 6}
let C = {c| c encodes rubiks cube that is solvable}
claim: D6 <= C in linear time.
proof:
given x= d1,d2,d3...d8, a base 10 number up to 8 digits long, construct c as follows:
let c be the solved cube initially
for i = 1..8:
twist corner i di times in CW direction
if d8 is odd:
flip some edge on the cube
recall that x is divisible by 6 iff it is divisible by 2 AND it is divisible by 3.
a number is divisible by 2 iff last digit is even.
a number is divisible by 3 iff the sum of all of its digits is divisible by 3
rubiks cube is solvable iff flips of edges are even, and twists of corners % 3 = 0. (counting twists 0=normal, 1=CW, 2=CCW). (and of course the #swaps is even, but i dont change that)
The above reduction can be clearly accomplished in linear time on size of input.
It follows that x in D6 iff c in C.
QED?
so to determine divisibility of a base10 number by 6, I need a rubik's cube, linear time in size of the number, and up to 20 seconds thereafter.
if we assume that each twist or flip takes 2 seconds, then to test divisibility of an 8digit number I need 8x2+2+20=38 seconds using the cube?
Am I right or what?
EDIT:
The reduction above is actually constant time as Lucas pointed out. Originally I did not have the restriction to 8 digits, and the algorithm was instead
for i = 1...n:
twist a corner di times
then thats linear reduction, and works for arbitrarily large number of digits. But its boring because you are only twisting the same corner the whole time. pfft
anyway, i thought it was pretty cool.
let D6 = {x| x is base10, up to 8 digits long and divisible by 6}
let C = {c| c encodes rubiks cube that is solvable}
claim: D6 <= C in linear time.
proof:
given x= d1,d2,d3...d8, a base 10 number up to 8 digits long, construct c as follows:
let c be the solved cube initially
for i = 1..8:
twist corner i di times in CW direction
if d8 is odd:
flip some edge on the cube
recall that x is divisible by 6 iff it is divisible by 2 AND it is divisible by 3.
a number is divisible by 2 iff last digit is even.
a number is divisible by 3 iff the sum of all of its digits is divisible by 3
rubiks cube is solvable iff flips of edges are even, and twists of corners % 3 = 0. (counting twists 0=normal, 1=CW, 2=CCW). (and of course the #swaps is even, but i dont change that)
The above reduction can be clearly accomplished in linear time on size of input.
It follows that x in D6 iff c in C.
QED?
so to determine divisibility of a base10 number by 6, I need a rubik's cube, linear time in size of the number, and up to 20 seconds thereafter.
if we assume that each twist or flip takes 2 seconds, then to test divisibility of an 8digit number I need 8x2+2+20=38 seconds using the cube?
Am I right or what?
EDIT:
The reduction above is actually constant time as Lucas pointed out. Originally I did not have the restriction to 8 digits, and the algorithm was instead
for i = 1...n:
twist a corner di times
then thats linear reduction, and works for arbitrarily large number of digits. But its boring because you are only twisting the same corner the whole time. pfft
Last edited:
