Project Euler/62

Problem Statement

Cubes that permute to other cubes: find the smallest cube for which exactly 5 permutations of the cube are also cubes.

Link: https://projecteuler.net/problem=62

Solution Technique

We are looking for the smallest cube that permutes with N other cubes.

The key idea here is that, for a particular cube permuting to other cubes, the cubes must all have the same number of digits - which provides a lower and upper bound on the numbers that need to be examined for a particular cube. This means we can break the problems into chunks, each increasing in size by an order of magnitude, and tackle the problem that way. (For reference, the final result is 12 digits!)

The core data structure to do this task quickly is the hash map - we proceed by computing a round of $10^{N-1}$ to $10^{N}$ perfect cubes, and sort their digits. These form the hash map keys, and we store the cube that results in a list so that we can cross-reference it in our search for permuted digits.

Code

The core of the method, where we proceed through the problem in chunks and assemble a hash map to store all of the cubes with N digits:

		Map<String,List<BigInteger>> m = new HashMap<String,List<BigInteger>>();

		int MAX = 10000;
		int ceil = 10;
		while(ceil<MAX) { 
			// Consider another order of magnitude
			ceil *= 10;
			for(int p=ceil/10; p<ceil; p++) { 

				BigInteger cube = BigInteger.ONE;
				// Cube it
				for(int j=0; j<3; j++) { 
					cube = cube.multiply( BigInteger.valueOf(p) );
				}

				// This is a bit messy.
				char[] cubeArr = cube.toString().toCharArray();
				Arrays.sort(cubeArr);
				String sortedCubeString = new String(cubeArr);

				if(m.keySet().contains(sortedCubeString)) {
					// If this permutation already exists in the map,
					// add this cube to the list and check if it's the nperms^th case.
					List<BigInteger> list = m.get(sortedCubeString);
					list.add(cube);
					if(list.size()==nperms) {
						// Someone in list is a winner.
						return Collections.min(list);
					}
				} else {
					// Start a new list
					List<BigInteger> list = new ArrayList<BigInteger>();
					list.add(cube);
					m.put(sortedCubeString,list);
				}
			}
		}
		System.out.println("Search for a cube that permutes "+nperms+" times failed. Search stopped at "+MAX+".");
		return null;

Link: https://git.charlesreid1.com/cs/euler/src/master/scratch/Round2_050-070/062/Problem062.java