# Number-maze (1,...,560)

This is an entry to the 12th fortnightly challenge.

This maze is built out of the integers $1,\dots,560$. You may step from $k$ to $2k$, or from $3k+1$ to $5k+1$, or vice versa in each case, provided you don't step outside that range $1,\dots,560$. ($k$ is an integer.)

So here is a small part of the maze: $$\begin{array}{c} &&&&21& \longleftrightarrow &42& \longleftrightarrow &84&&176& \longleftrightarrow &352\\ && & & \updownarrow&&&&&&\updownarrow \\ 3 & \longleftrightarrow & 6 & & 13 & \longleftrightarrow & 26 & & 53 & \longleftrightarrow & 106& & 213 & \longleftrightarrow & 426 \\ & & \updownarrow & & & & \updownarrow & & & & \updownarrow & & & & \updownarrow \\ 2 & \longleftrightarrow & 4 &\longleftrightarrow& 8 & \longleftrightarrow & 16 & \longleftrightarrow & 32 & \longleftrightarrow & 64 & \longleftrightarrow & 128 & \longleftrightarrow & 256 & \longleftrightarrow & 512 \\ & & & & & & \updownarrow & & & & & & & & \updownarrow \\ & & & & 5 & \longleftrightarrow & 10 & \longleftrightarrow & 20 & \longleftrightarrow & 40 & & 77 & \longleftrightarrow & 154 & \longleftrightarrow & 308 \\ \end{array}$$

Your starting-position is a sexual one for two, and you finish where Bradbury's famous work catches fire.

Further (arithmetical) clues to those positions:

Their product is 31119 and their sum is 520.

Bonus: Why $560$, not $600$, say?

• Very interesting idea! But to clarify: as you only show a part of the maze: are we to built the maze as we step along, with the two optional types of steps being horizontal / vertical? Jul 22 '16 at 7:29
• @RosieF: Sorry about that! Didn't want to post it as an answer since it would be way too short.
– Deusovi
Jul 22 '16 at 7:41
• @BmyGuest: I think I've figured out both of them: rot13: fvkgl avar gb sbhe uhaqerq svsgl bar
– Deusovi
Jul 22 '16 at 7:43
• @Rosie: Now we don't even need to figure out the clues! The quadratic formula just tells us the answers.
– Deusovi
Jul 22 '16 at 8:05
• The answer to the bonus is not that allowing numbers up to (say) 600 would permit a much shorter path between the start and finish points. You need to go up to 1576 before the path gets shorter. I think the shortest path with no upper limit goes as high as 2176. Jul 22 '16 at 9:35

A favourite

position is the $69$

Books catch fire, somewhere around

$451$ Fahrenheit

Hint check

$451\times69=31,119$
$451+69=520$

My brute forcer, below, shows that

The 37 move path:

[69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 68, 34, 56, 28, 14, 7, 11, 22, 44, 88, 176, 106, 64, 32, 16, 26, 52, 86, 43, 71, 142, 236, 118, 196, 326, 163, 271, 451]
is the only path we may successfully take
(without revisiting numbers on which we already stepped).

With a maximum of greater than $575$, such as $600$

We can start to take a second route by deviating at $22$ to take an alternative path to $52$ via $576$:

[69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 68, 34, 56, 28, 14, 7, 11, 22, 36, 72, 144, 288, 576, 346, 208, 104, 52, 86, 43, 71, 142, 236, 118, 196, 326, 163, 271, 451]

The very simple Python code I wrote:

def iterNextNs(curN, minN=1, maxN=560):
if curN % 2 == 0:
v = curN // 2
if v >= minN:
yield v
v = 2 * curN
if v <= maxN:
yield v
m1 = curN - 1
v = 3 * m1
if v % 5 == 0:
v = v // 5 + 1
if v >= minN:
yield v
v = 5 * m1
if v % 3 == 0:
v = v // 3 + 1
if v <= maxN:
yield v

def routes(visited=[69], toN=451, minN=1, maxN=560):
for nextN in iterNextNs(visited[-1], minN, maxN):
if nextN == toN:
yield visited + [toN]
elif nextN not in visited:
for route in routes(visited + [nextN], toN, minN, maxN):
yield route

• Now, is there a simple way to show this without such an attack... Jul 22 '16 at 10:02
• Correct, including the bonus. Up to 575, each component of the maze is a tree. 576 creates the first cycle. Unfortunately, the path overlaps the cycle, so the puzzle fails to have a unique answer. Moreover, the path includes exactly half of the cycle, so even requiring a shortest route still fails to yield a unique answer. Jul 22 '16 at 10:03
• Although if we make the maximum $2176$ we can take a $21$ step route: [69, 138, 276, 166, 100, 50, 25, 41, 82, 136, 272, 544, 1088, 2176, 1306, 784, 392, 196, 326, 163, 271, 451] Jul 22 '16 at 10:25
• But if I'd chosen a different set of numbers, I'd have chosen different endpoints, e.g. 78 & 257 for {1,...,1576}. Jul 22 '16 at 10:36
• Oooo, I've never tried a $78$ :p Jul 22 '16 at 10:39

I believe the shortest route between

69 (I don't think I need to explain) and 451 (Ray Bradbury's Fahrenheit 451)

is

37 moves

using this route:

69 138 276 166 100 50 25 41 82 136 68 34 56 28 14 7 11 22 44 88 176 106 64 32 16 26 52 86 43 71 142 236 118 196 326 163 271 451.

I got this result from writing java code to implement a naiive breadth-first search.

import java.util.*;
import java.text.*;
import java.math.*;

public class bfs {

public static void main(String[] args) {
//processing
Cell[] board = new Cell[561];

for (int i = 1; i <= 560; i++){
board[i] = new Cell(i);
}

//bfs
board[69].setVisited(true);
while (!q.isEmpty()){
Cell curr = q.remove();
for (Integer e : curr.getAdjs()) {
if (board[e].getVisited() == false) {
board[e].setVisited(true);
board[e].setLevel(curr.getLevel()+1);
board[e].setParent(curr.getLabel());
}
}

int result = board[451].getLevel();
if (result == 0) {result = -1;}
//output
System.out.println(result);
System.out.print("451 ");
Cell parent = board[451];
while (parent.getLabel() != 69) {
parent = board[parent.getParent()];
System.out.print(parent.getLabel() + " ");

}
}
}

class Cell {
private int label;
private int level;
private boolean visited;
private ArrayList<Integer> adjacents = new ArrayList<Integer>();
private int parent;

public Cell(int i){
label = i;
level = 0;
visited = false;
parent = 0;
}

public int getLabel() {return label;}
public int getLevel() {return level;}
public void setLevel(int i) {level = i;}
public boolean getVisited() {return visited;}
public void setVisited(boolean b) {visited = b;}