You can find more details on where these challenges come from and how/why we will be approaching them in the original posting.
Challenge #1
Let's jump right in with the first challenge! You can find the original presentation of the challenge (in French!) here.
It goes as follows: a number is said to be a palindrome if the digits read left to right are the same as if read right to left. An example would be 151, or 70355307. The first question is simply to determine the number of palindrome numbers that have 351 digits. As a bonus question: what is the minimal difference between two palindrome numbers with 351 digits?
Naturally the first step is to get a better understanding of what we are dealing with, independently of how we want to tackle the problem.
Definitely seems like a small pattern is emerging! If we were to continue with the mathematical approach we would look at N = 4, possibly N = 5 to better understand the dynamics, and start separating the case of N even with N odd. Let's take the R route for now.
How can we generate/identify all palindromes with N digits?
One first approach is to generate all numbers of N digits, flip them, and keep those where the flip left the number unchanged:
PalindromesSlow <- function(n) {
numbers <- seq(10 ^ (n-1), 10 ^ n-1)
flipped <- as.numeric(sapply(
lapply(strsplit(as.character(numbers), split = ""), rev),
paste0, collapse = ""))
palindromes <- numbers[numbers == flipped]
return(palindromes)
}
Why the “Slow” in the name? While this function performs exactly as expected, it won’t scale well if we start looking at numbers 7-digit long and larger. The main reason is that we are generating every single potential number and only selecting an ever-decreasing fraction of those meeting our palindrome criteria. Why ever-decreasing? Let’s look at the trend for our first values of N:
- N = 1: 9 palindromes, 9 total numbers: 100%
- N = 2: 9 palindromes, 90 total numbers: 10%
- N = 3: 90 palindromes, 900 total numbers: 10%
- N = 4: 90 palindromes, 9000 total numbers: 1%
XYZT --> XYZTZYX.
length.firsthalf <- ceiling(n / 2)
digit.list <- rep(list(0 :9), length.firsthalf)
# remove 0 as option for first digit
digit.list[[1]] <- 1 : 9
# expand grid
eg <- expand.grid(digit.list)
A quick word on the expand.grid() function which has saved me on multiple occasions. It essentially generates all possible cross-combinations of arguments provided. Easier to see through a simple example:
expand.grid(c(1, 2, 3), c("a", "b"))
Var1 Var2
1 a
2 a
3 a
1 b
2 b
3 b
For our PalindromeQuick function it is incredibly valuable as we want something generic enough to adjust to any n. So we create a list of length n with all possible options at each position, and stick that into expand.grid and voila! No need for complicated nested for loops, especially as we wouldn't know how many for loops to nest in the first place!
We can then wrap that in a function to determine how many palindromes were found as well as minimal distance between consecutive palindromes. The only trick is carefully handling n being even or odd as discussed previously.
PalindromesQuick <- function(n) {
length.firsthalf <- ceiling(n / 2)
digit.list <- rep(list(0 :9), length.firsthalf)
# remove 0 as option for first digit
digit.list[[1]] <- 1 : 9
# expand grid
eg <- expand.grid(digit.list)
if (n %% 2 == 0) {
flipped.ending <- apply(eg, 1, function(row) {
paste0(rev(row), collapse = "")
})
} else {
flipped.ending <- apply(eg, 1, function(row) {
paste0(rev(row[- length(row)]), collapse = "")
})
}
eg$ending <- flipped.ending
palindromes <- sort(as.numeric(
apply(eg, 1, paste0, collapse = "")))
return(palindromes)
}
Having written a slow and quick function, we should pause to think about how much faster quick is, and talk about timing our R functions.
Timing in R
When I started using R, my trick for timing functions was simply to record the absolute time before and after execution and take the difference:
t1 <- Sys.time()
output.slow.7 <- PalindromesSlow(7)
t2 <- Sys.time()
t2 - t1
1.174394 mins
I later discovered it could all be done in one go with the built-in system.time() function:
system.time(output.slow.7 <- PalindromesSlow(7))
user system elapsed
68.348 0.544 69.016
They each have small caveats one should be aware of in how they track elapsed time, but for most timing purposes return exactly what you care about. system.time() has the advantage of being a one-liner, but the former solution is easier to use if you have multiple lines you want to time and also makes it easier to comment in/out of code.
From now on we'll solely focus on the Quick version, a 600X improvement is definitely something we'll take!
A quick comment on efficiency and speed: it's always important to weigh the pros and cons. While a function that runs faster always seems preferable on paper, one must also consider the necessity of speeding in the first place, as well as the additional complexity of speeding things up. Here the quick version was just a few lines longer and simple to understand and the increase in speed will allow us to explore numbers that are 14 digits long as quickly as the slow version took to explore 7-digit numbers. However, this is not always the case, we'll see this in challenge #3 where trying to be efficient is not going to be straightforward to implement and scale, and the gain might still be insufficient to explore the higher dimensions.
Results
Using our PalindromeQuick function, let's look at the number of palindromes and minimal distance between consecutive palindromes:
| N | Number of Palindromes | Minimum Difference |
|---|---|---|
| 1 | 9 | 1 |
| 2 | 9 | 11 |
| 3 | 90 | 10 |
| 4 | 90 | 11 |
| 5 | 900 | 11 |
| 6 | 900 | 11 |
| 7 | 9000 | 11 |
| 8 | 9000 | 11 |
| 9 | 90000 | 11 |
| 10 | 90000 | 11 |
| 11 | 900000 | 11 |
| 12 | 900000 | 11 |
| 13 | 9000000 | 11 |
| 14 | 9000000 | 11 |
Although we haven’t provided a formal mathematical proof, I think we at least have a good idea of the challenge's answers.
If n is even, we have as many palindromes as there are combinations of n / 2 digits with the first one not being a 0, that’s 9 * 10 ^ (n/2 - 1).
If n is odd, we have as many palindromes as there are combinations of (n + 1) / 2 digits with the first one not being a 0, that’s 9 * 10 ((n + 1) / 2 - 1).
Minimal difference is somewhat trickier...
Based on the simulations, minimal value fluctuates a bit at first, but definitely seems to quickly stabilize at 11 for numbers with 4 or more digits.
It’s an interesting problem: if we want to make a small change to an existing palindrome to create the next small palindrome, we would typically want to make small changes to the right hand side of the number (units, tens...). But because of the palindromic nature of our numbers, small changes to the right will lead to the same change on the far left and thus a huge delta between our two numbers. The obvious option is to aim for the middle, but that’s still an absolute change of the order of 10 ^ (n / 2).
If we look at examples with small n, we see we can do better when we have nine(s) in the middle: 393 and 404, 5995 and 6004. This is basically our initial trick of incrementing the “middle” but after 9 we can 0 and need to increment the digits to the immediate right and left: 37973 increments to 38983 (delta of 1010), but 39993 increments to 40004 (delta of 11).
So we've reached the point where we've proven the delta is no bigger than 11 as X99...99X (with X any digit between 1 and 8) and (X+1)00...00(X+1) will have a delta of 11.There will be 8 such instances, no matter the number of digit of the palindrome. Proving that 11 is actually the best we can do is a much tougher question.
Back to the challenge, we can quite confidently answer the first challenge that there are 9e175 351-digit palindromes, and that minimal difference will be 11.
Before we sign off, let’s finish with a small plot of the distribution of differences between consecutive palindromes. Given our previous comments and at a very high-level, we should expect a big spike around 10 ^ (n/2), then a spike about one-tenth of that for 10 ^ (n / 2 - 1) whenever the middle number is 9, then a spike one-hundredth smaller at 10 ^ (n / 2 - 2) whenever the middle number is 999 and so on. And as noted previously, 8 cases with a delta of 11.
Turns out we weren’t too far off !
For N = 13:
For N = 14:
For the graphs, despite the numerical nature of the x-axis, we naturally went for barplots instead of histograms given the very peculiar discrete distribution!
