Number-maze (1,…,560)

Question

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?

Answer 1

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

Answer 2

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);
            if (i*2 <= 560) {board[i].addAdj(i*2);}
            if (i%2 == 0) {board[i].addAdj(i/2);}
            if ((i-1)%5 == 0) {board[i].addAdj((i/5*3)+1);}
            if ((i-1)%3 == 0 && (i/3*5)+1 <= 560) {board[i].addAdj(i/3*5+1);}
        }

        //bfs
        Queue<Cell> q = new LinkedList<Cell>();
        board[69].setVisited(true);
        q.add(board[69]);
        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());
                    q.add(board[e]);}
            }
        }

        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;
        adjacents = new ArrayList<Integer>();
        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;}
    public ArrayList<Integer> getAdjs() {return adjacents;}
    public void addAdj(int i) {
        adjacents.add(i);
    }
    public int getParent(){return parent;}
    public void setParent(int i) {parent = i;}
}