There is a series of puzzle caches in the east of England with a great number of interesting abstract puzzles, some of which are R-able. Amongst this estimable collection is one which is itself a miniature collection of puzzles. I saw it yesterday and starting working on the fifteen small puzzles. As of writing this, I’ve finished 10 of them and, to congratulate myself, I’m taking time off to share one of them, since it’s lead to something of a discovery. First the puzzle:

The number 720 has no fewer than 29 divisors: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240 and 360. But 29 is not the “record”. Another three-digit number exists which has 31 divisors? Can you find it?

A heuristic method occurred to me: a way to produce a minimal product with maximal divisors, which popped into my head and took me quickly to a possible solution. The method then slipped into haze and I can no longer describe it well*, but even if it was sound, and I can’t be sure, it’s safest to check my answer methodically. Here’s a quick R programme to do that

library(tidyverse)
library(magrittr)
## a function to find the integer partitions of a given number
divisors <- function(x) {
  if (x < 4) return(1)
  tries <- 2:sqrt(x)
  exact <- (x / tries) %% 1
  c(1, tries[exact==0], x/tries[exact==0]) %>% unique() %>% sort()
}
## vectorising inputs to a given maximum
divisor_progress <- function(n) {
  sapply(1:n, function(q) {
    q %>% divisors() %>% length()
  }) %>% cbind(x=1:n, y=.)
}
## show the answer
divisor_progress(999) %>% as_tibble() %>% arrange(-y)

The answer I came up with was quickly confirmed. But I didn’t stop to go back to the other puzzlettes; I started to explore the pattern of the increasing number of divisors in the sequence of positive integers.

There is an incredible resource online called the Online Encyclopedia of Integer Sequences which you can see here. Beware, for a number nerd it is pure quicksand. I’ve seldom found a website that I could spend so long just browsing, and I really thought that they had everything in there that I could ever hope to come across. Wrong. The number sequence I discovered was not in there. A close cousin is, but not mine. I did the responsible thing and signed up for an account and submitted it. I’ll update this blog when I hear back about its acceptance or rejection.

* but I’ll try
Write down a grid of prime numbers and increasing exponents to their right (I’ve kept them all below 100 just to make it tidy):
2 4 8 16 32 64
3 9 27 81
5 25
7 49
11
13
Then, take the smallest number you can find and include its base in your product. So first up we take the 2 in the top row. Its base is 2, so our first term is simply 2. Now, take the lowest unused element from the table. That’s the 3 in the second line. Our product is now 2*3 = 6. Next is the 4 from the first line, whose base is 2 again. 2*3*2 = 12. Eventually we get to 2*3*2*5*7*2, which is our answer.
This method, which is the result of a flash of insight rather than a rigorous analysis, might be wholly flawed, but it did get me to the right answer in this case, and the intermediate steps (6, 12, 60, 420) each seem to be standout local maxima for their number of divisors. If anyone has any insight into why this works, or why it is flawed, is encouraged to let me know!