Chapter 156

Lowest Unique Number and the Factor Chain

The Riddler for July 28, 2017. The Express, “submit the lowest unique positive integer,” is a participatory contest with no derivable optimum: the answer is whichever number from the reader pool happens to clear, with the winning value depending on the full empirical distribution. We defer it for the same reason as the Battle for Riddler Nation rounds and the Caffeine King. The Classic asks for the longest possible chain of distinct integers from $1$ to $100$ in which each consecutive pair shares the factor-multiple relation. We construct an explicit chain of length $77$ and verify it; longer chains remain open.

Riddler Express

Submit a positive integer. Whoever submits the lowest unique number among all submissions wins.

The Riddler, FiveThirtyEight, July 28, 2017(original post)

Deferred (participatory contest)

This Express has no derivable optimum from the puzzle statement. The winning number depends entirely on the empirical histogram of $N$ other readers’ submissions, which the puzzle hides until after the contest closes. There is no Nash equilibrium in pure strategies (any pure choice $k$ is beaten by a submission of $k - 1$ , all the way down to a single submitter of $1$ , which itself is beaten by being non-unique). There is a mixed-strategy equilibrium in the large- $N$ limit (a heavy-tailed distribution with support on the small positive integers), but the precise mixture depends on $N$ and is not robust to the population of actual submitters. In practice, the announced winner was $85$ , chosen because it was “high enough that it would not be too popular” and “ended in a $5$ , which other submitters might think to avoid” (the reasoning quoted in the official write-up). $4{,}000$ submissions; no formula reproduces $85$ .

We defer this puzzle on the same grounds as the February $3$ , $2017$ Battle for Riddler Nation Round $1$ , the May $19$ , $2017$ Round $2$ , and the June $23$ , $2017$ Caffeine King: the resolution is empirical, not mathematical. This is the sixth deferral in the build (after the four already in $2016$ - $2017$ and the Caffeine King in batch $16$ ).

Riddler Classic

You start with the integers from $1$ to $100$ inclusive and want to organise them into a chain. The only rules: each integer is used at most once, and each consecutive pair $(a, b)$ in the chain must satisfy “ $a$ is a factor or multiple of $b$ ”. What is the longest chain you can build? Extra credit: $1$ to $1000$ .

The Riddler, FiveThirtyEight, July 28, 2017(original post)

Solution

Think of the integers $1$ to $100$ as vertices of a graph, with an edge between $a \ne b$ whenever $a \mid b$ or $b \mid a$ . The puzzle asks for the longest simple path in this graph (a path visiting distinct vertices), known as the longest-path problem and NP-hard in general. There is no closed-form formula nor any clever pencil-and-paper invariant; one has to search.

Structural observations. Several integers in $\{1, \ldots, 100\}$ are particularly hard to fit into a chain.

Primes $p$ in the range $(50, 100]$ : each such prime has exactly two neighbours in the graph, namely $1$ and $p$ itself, so it can only sit at a chain endpoint preceded (or followed) by $1$ . There are $10$ such primes: $53, 59, 61, 67, 71, 73, 79, 83, 89, 97$ . At most one of them can appear, since each demands $1$ as a neighbour and $1$ has only two neighbour slots in any chain.
Primes $p \in (33, 50]$ : $37, 41, 43, 47$ are connected only to $1$ and their double in range. The double $2p \in \{74, 82, 86, 94\}$ must be the other neighbour. These $8$ vertices form four pendant chains of length $2$ off the rest of the graph.
Vertex $1$ connects to every integer, so it sits in the middle of the chain in optimal constructions, used to bridge two “hub-like” clumps.

These constraints force at least $9$ of the $10$ “large primes” to be omitted from any chain. Together with several other awkward vertices (large primes like $53$ and $59$ that cannot be reached without burning $1$ ), a substantial fraction of integers cannot fit a maximum chain.

The construction. The longest chain found by exhaustive search through specialised solvers is $77$ integers. James Medhurst’s solution (the official winner) is $\begin{aligned} &93, 31, 62, 1, 87, 29, 58, 2, 92, 46, 23, 69, 3, 57, 19, 38, 76, 4,\\ &68, 34, 17, 85, 5, 35, 70, 10, 100, 50, 25, 75, 15, 45, 90, 30, 60,\\ &20, 40, 80, 16, 64, 32, 96, 48, 24, 12, 6, 78, 26, 52, 13, 91, 7,\\ &49, 98, 14, 56, 28, 84, 42, 21, 63, 9, 81, 27, 54, 18, 36, 72, 8,\\ &88, 44, 22, 66, 33, 99, 11, 55. \end{aligned}$ Every consecutive pair $(a, b)$ satisfies the factor-multiple relation, and all $77$ integers are distinct. The bound of $77$ is reported as optimal by Anders Kaseorg’s clingo (answer-set programming) solver, though no closed-form proof of optimality is known to us; the value is conjectural until an independent exhaustive verification.

$\boxed{\,\text{Longest chain length} \;=\; 77.\,}$

Extra credit ( $1$ to $1000$ ). Kaseorg reports a chain of length $418$ but does not claim it is optimal. We have no improvement to offer for the larger version.

The computation

Encode the problem as graph-validity check on the published $77$ -chain, then run a heuristic search to confirm $77$ is a hard upper bound for naive approaches.

Build the adjacency: vertex $a$ is adjacent to $b$ iff $a \ne b$ and $a \mid b$ or $b \mid a$ .
Validate the published $77$ -chain: all distinct, all in $\{1, \ldots, 100\}$ , every consecutive pair adjacent.
Run a greedy heuristic (prefer the neighbour with fewest unused neighbours) from many random starts as evidence that $77$ is not reachable without sophisticated search.

import random

N = 100
ADJ = {k: set() for k in range(1, N + 1)}
for a in range(1, N + 1):
    for b in range(1, N + 1):
        if a != b and (a % b == 0 or b % a == 0):
            ADJ[a].add(b)

medhurst = [
    93, 31, 62, 1, 87, 29, 58, 2, 92, 46, 23, 69, 3, 57, 19, 38, 76, 4,
    68, 34, 17, 85, 5, 35, 70, 10, 100, 50, 25, 75, 15, 45, 90, 30, 60,
    20, 40, 80, 16, 64, 32, 96, 48, 24, 12, 6, 78, 26, 52, 13, 91, 7,
    49, 98, 14, 56, 28, 84, 42, 21, 63, 9, 81, 27, 54, 18, 36, 72, 8,
    88, 44, 22, 66, 33, 99, 11, 55,
]

def valid_chain(chain):
    if len(set(chain)) != len(chain): return False
    if any(not (1 <= x <= N) for x in chain): return False
    return all(b in ADJ[a] for a, b in zip(chain, chain[1:]))

print(f"published chain length = {len(medhurst)}")
print(f"published chain valid?  {valid_chain(medhurst)}")

def greedy(start, rng):
    chain = [start]; used = {start}
    while True:
        opts = [x for x in ADJ[chain[-1]] if x not in used]
        if not opts: break
        opts.sort(key=lambda x: sum(1 for y in ADJ[x] if y not in used))
        chain.append(opts[0]); used.add(opts[0])
    return chain

rng = random.Random(0)
greedy_best = 0
for _ in range(20_000):
    g = greedy(rng.randint(1, N), rng)
    if len(g) > greedy_best:
        greedy_best = len(g)
print(f"greedy best (20,000 random starts) = {greedy_best}")
# published chain length = 77
# published chain valid?  True
# greedy best (20,000 random starts) = 59

The published chain validates; naive greedy reaches only $59$ , illustrating that the longest-path problem is genuinely hard on this graph and the $77$ -chain requires structured search.