GC5GRBF RR175 – Polymath

[This article was first published on geocacheR, and kindly contributed to R-bloggers]. (You can report issue about the content on this page here)
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

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

## 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
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!

To leave a comment for the author, please follow the link and comment on their blog: geocacheR.

R-bloggers.com offers daily e-mail updates about R news and tutorials about learning R and many other topics. Click here if you're looking to post or find an R/data-science job.
Want to share your content on R-bloggers? click here if you have a blog, or here if you don't.

Never miss an update!
Subscribe to R-bloggers to receive
e-mails with the latest R posts.
(You will not see this message again.)

Click here to close (This popup will not appear again)