Here’s a link to the problems and a link to the code on Github.

**Riddler Express**

Not much to explain here. I figured from previous “you-versus-other-Riddlers” questions, there’d around 2000 to 2500 submissions, with a fair percentage of them being trolls who will submit 1 just for the lolz. Given this, I threw game theory out of the window and prayed for luck-of-the-draw. I figured a mid-to-high two-digit prime number might be a winner; a bit more number crunching and coin flipping resulted in my final guess of **67**.

**Riddler Classic**

I could not think of an “elegant” solution off the top of my head, so I resorted to a brute-force approach. Our good old friend recursion becomes helpful here:

```
from __future__ import print_function
import math
import sys
def divs_and_mults(num, maxval):
valid = set()
# compute divisors
mid = math.ceil(math.sqrt(num))
for n in range(1, int(mid) + 1):
if num % n == 0:
valid.add(n)
div = num / n
if div != n:
valid.add(div)
# compute multiples
mult = 2 * num
while mult <= maxval:
valid.add(mult)
mult += num
return valid
def valid_next(chain, valid, maxval):
if len(chain) == 0:
return set(range(1, maxval + 1))
else:
return valid[chain[-1]] - set(chain)
def build_recursive(chain, valid, maxval):
longest = list(chain)
# loop through all valid next links
for n in valid_next(chain, valid, maxval):
chain.append(n)
result = build_recursive(chain, valid, maxval)
if len(result) > len(longest):
longest = result
chain.pop()
return longest
def longest_chain(maxval):
# compute valid "next" links for all values
valid = {}
for n in range(1, maxval + 1):
valid[n] = divs_and_mults(n, maxval)
return build_recursive([], valid, maxval)
if __name__ == "__main__":
if len(sys.argv) >= 2:
maxval = int(sys.argv[1])
else:
maxval = 100
assert maxval > 2, "invalid maximum value"
chain = longest_chain(maxval)
print("Found chain of length {0}.".format(len(chain)))
print(chain)
```

Allow me to explain my reasoning. As with any recursive program, I looked to minimize the amount of computation required within the actual recursive call. Thus, I precomputed all divisors and multiples for each number from 1 to 100 and used these precomputed values to create a set of “valid” next links during each recursive call. The rest was easy: maintain the longest known chain and remove links from the “current” chain once all possible links are exhausted. This brute-force method works, but is unfortunately incredibly inefficient: running this with `maxval = 30`

takes a whopping 2.5 minutes on a single 3.4GHz i7 core, with exponentially increasing runtime as `maxval`

grows bigger.

Following this debacle, I tried replacing the recursion with a single loop in an attempt to improve efficiency. This allowed me to collapse functions `valid_next`

, `build_recursive`

, and `longest_chain`

into a single function:

```
def longest_chain(maxval):
# compute valid "next" links for all values
valid = {}
for n in range(1, maxval + 1):
valid[n] = divs_and_mults(n, maxval)
# maintain a stack to store "recursive" data
longest = []
chain = []
stack = []
links = range(maxval, 0, -1)
while True:
# last set of links was exhausted, back up and try again
if not links:
if len(chain) > len(longest):
longest = list(chain)
if len(chain) == 0:
break
chain.pop()
links = stack.pop()
# add new link to chain
else:
chain.append(links.pop())
stack.append(links)
links = valid[chain[-1]] - set(chain)
return longest
```

Easy enough, but this still took way too long – around 1.5 minutes for `maxval = 30`

– to run, making the problem intractable for `maxval = 100`

(where’s a Hadoop cluster when you need one). Undeterred, I decided to run the program that I had written for a select set of lower `maxvals`

, hoping to see a pattern:

# result example chain
5 4 possibilities [2, 4, 1, 3]
10 9 possibilities [4, 8, 1, 5, 10, 2, 6, 3, 9]
15 13 possibilities [6, 12, 4, 8, 1, 7, 14, 2, 10, 5, 15, 3, 9]
20 17 possibilities [7, 14, 2, 8, 16, 4, 12, 6, 18, 9, 3, 15, 5, 10, 20, 1, 19]
25 21 possibilities [9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 1, 11, 22, 2, 14, 7, 21, 3, 15, 5, 25]
30 26 possibilities [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
31 26 possibilities [11, 22, 1, 13, 26, 2, 14, 28, 7, 21, 3, 27, 9, 18, 6, 12, 24, 8, 16, 4, 20, 10, 30, 15, 5, 25]
32 27 possibilities [11, 22, 1, 13, 26, 2, 32, 16, 8, 24, 12, 6, 18, 9, 27, 3, 21, 7, 14, 28, 4, 20, 10, 30, 15, 5, 25]
33 28 possibilities [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]
34 28 possibilities [13, 26, 1, 21, 7, 28, 14, 2, 22, 11, 33, 3, 27, 9, 18, 6, 12, 24, 8, 32, 16, 4, 20, 10, 30, 15, 5, 25]

One pattern jumps out very quickly: prime numbers greater than half of `maxval`

are nowhere to be found unless they are at the beginning or end of the chain. The reason for this becomes obvious once we treat each number as a node in a graph: its only possible link to the rest of the chain is the number 1. Once we reach `maxval = 34`

, our chain starts to miss 17 and 34 as well. These are missing for a similar reason: their only link to the rest of the chain is 1 and 2, and 2 has already been used to link other values. For `maxval = 100`

, a similar argument can be made for 31, 62, and 93 as well. Thus, our longest possible chain for `maxval = 100`

will exclude 31, 37, 41, 43, 47, 53, 59, 61, 62, 67, 71, 73, 74, 79, 82, 83, 86, 89, 93, 94, and 97, which gives us a longest possible length of **79**.

DISCLAIMER: This is very much an educated guess. Wish I had a bit more time to figure this one out – it’s an interesting Riddler and deserves a bit more attention.