Can You Solve Middle-Square Madness?
Illustration by Guillaume Kurkdjian
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter or send me an email.
All good things …
Friday, June 30 will mark the final column for The Riddler here at FiveThirtyEight. But this isn’t quite the end. Next week, I will be running the Eighth and Final Battle for Riddler Nation, with results appearing in the ultimate column the following week. And after that … stay tuned!
And now, without further ado, back to the puzzles!
Riddler Express
With The Riddler nearing its end here at FiveThirtyEight, I can finally get something off my chest: Starting a competition with the flip of a coin (say, to determine possession of a ball) is so boring!
Instead, let’s give the captain of one team a fair coin and the captain of the other team a fair die. The captain with the coin will flip it at the same time the other captain rolls the die. They continue doing this until the coin is the same (whether heads or tails) for three consecutive flips or the number that comes face-up on the die is the same for two consecutive rolls.
On average, how many coin flips will it take to get three in a row? And how many die rolls will it take to get two in a row?
Extra credit: While the numbers of flips and rolls may often be the same, which team — the team with the coin or the team with the die — is more likely to win the toss/roll? (That is, which is more likely to happen sooner?)
Riddler Classic
Thanks to Twitter, I recently became aware of the “middle-square method” for generating pseudorandom numbers (numbers that appear random, but are derived in a deterministic sequence).
This week, let’s look at the middle-square method for generating pseudorandom four-digit numbers. First, we start with a four-digit number, such as 9,876. If we square it, we get the eight-digit number 97,535,376. Our next pseudorandom number is taken from the middle four digits of that square: 5,353. And to get the next pseudorandom number, we can square 5,353, which gives us 28,654,609, the middle four digits of which are 6,546.
Of course, many four-digit numbers have a square that’s seven digits rather than eight. And in a sequence of middle-square numbers, you also might encounter smaller numbers whose squares have six or fewer digits. In these cases, you can append zeros to the beginning of the square until you have eight total digits, and once again take the middle four digits.
No matter what initial four-digit number you pick, your sequence of pseudorandom numbers will eventually repeat itself in a loop. If you want the longest sequence of such numbers before any repetition occurs, what starting number should you pick? And how many unique numbers are in the sequence?
Solution to the last Riddler Express
Congratulations to ÐÐÐЯСÐÐÑ Brian Mercurio ÐÐÐЯСÐÐÑ of Binghamton, New York, winner of last week’s Riddler Express.
Last week, you were a mission commander for the Riddler Space Agency, which was engaged in a space race with a competing agency. Both agencies were trying to claim regions of a newly discovered, perfectly spherical moon that possessed a magnetic field. Everywhere on the surface of this moon the magnetic field lines pointed from the north pole to the south pole, parallel to the surface (i.e., the magnetic field did not point into or out of the moon’s volume).
While you knew your team would reach the moon first, the politicians in charge entered into a rather bizarre agreement with the competition. Wherever your team landed on the moon, all the points on the surface whose magnetic field lines pointed in the direction of your landing site — that is, where the magnetic field pointed more toward your landing site than away from it — would belong to Riddler Nation. All the remaining parts of the surface would go to the competing agency’s nation.
If your team landed on a random point on this moon’s surface, then what was the expected fraction of the moon’s surface area that would be claimed by Riddler Nation?
At first, this seemed to be a rather challenging puzzle. For some landing points, what happened was pretty clear. For example, if you landed on the magnetic north pole of the moon, Riddler Nation got nothing. But if you landed on the magnetic south pole, then the entire moon would be claimed by Riddler Nation. But for other landing spots, determining the locus of points whose field lines were oriented more toward A — or whose magnetic field vectors had a positive component in A’s direction, you might say — was trickier to determine.
Fortunately, most solvers recognized there was a way to navigate around this three-dimensional mess. It was true that the region claimed by landing at a point A could be hard to calculate. However, every point on the sphere’s surface had a field line that either pointed more toward A or more toward the antipode of A — that is, the point on the diametrically opposite side of the moon. (Yes, there were points whose lines didn’t point toward either A or the antipode of A, but when calculating probabilities, this one-dimensional set of points was negligible compared to the entire two-dimensional surface.)
And so, between a point A and its antipode, the entire surface of the moon was claimed. That meant the average area claimed by Riddler Nation between A and its antipode was half the surface (i.e., one whole surface divided by two points). And since the entire surface could be split up into pairs of antipodal points, that meant on average you claimed half the surface.
Solution to the last Riddler Classic
Congratulations to ÐÐÐЯСÐÐÑ Reid Price ÐÐÐЯСÐÐÑ of Palo Alto, California, winner of last week’s Riddler Classic.
Last week, you were stopped by a troll while trying to cross a bridge. The troll was willing to grant you passage to the other side, provided you could estimate the factorial of a number N. (The troll kindly reminded you that the factorial — written with an exclamation point — of a whole number is the product of all the whole numbers from 1 to that number. For example, 5! is the product of the whole numbers from 1 to 5, so it’s 120.)
That was no problem, you thought, as you whipped your calculator out of your pocket. In addition to the 10 digits and a decimal point, your calculator could add, subtract, multiply, divide and exponentiate. And it even had a factorial button. Or rather, it used to …
It appeared that the devious troll somehow magically removed the factorial button from your calculator, replacing it with a button labeled N, which loaded the value of N from the calculator’s memory whenever you pressed it. While you didn’t yet know the precise value of N, the troll informed you it was no more than 200.
To pass the bridge, you had to use your calculator to estimate N! to within two orders of magnitude — that is, your answer had to be within a factor of 100 of the exact value of N!.
What expression would you have typed into your calculator?
A few readers opted to multiply N by N−1, and then that product by N−2, and then that product by N−3, and so on. While it wasn’t entirely clear from the puzzle if you could actually read out the value of N from the calculator — and therefore stop multiplying when you reached N−(N−1) — multiplying all the numbers from 1 to N could easily have resulted in a mistake. Even if you didn’t make any mistakes, the troll might very well have grown impatient and simply tossed you off the bridge.
Rather than find the exact value of N!, this puzzle was really asking you to find a decent approximation — that is, to within a factor of 102 — that worked for all values of N from 1 to 200. Most solvers recalled that when it comes to factorial estimations, Stirling’s approximation is the go-to formula. The approximation is typically written in logarithmic form: ln(N!) ≈ Nln(N) − N. Here, ln is the natural logarithm function.
Raising e to both sides of the Stirling approximation and rearranging using a few exponential identities gave an equivalent form of the approximation: N! ≈ (N/e)N. Before moving further, I just want to point out how cool this approximation is. Multiplying every number from 1 to N can be approximated by multiplying a single number N times. But what is that number? It’s 1/e times N, or about 37 percent of N — no matter what value of N that is. Neat, right?
Anyway, since your calculator didn’t have a button for e, Reid (this week’s winner) used 2.7 instead. Indeed, for all N between 1 and 200, both (N/e)N and (N/2.7)N were within a factor of 100 of N!, although (N/2.7)N turned out to be a better approximation over this domain, as shown in the graph below. While there were multiple correct answers here, I have it on good authority that seeing you enter (N/2.7)N on your calculator particularly delighted the troll.
Of course, Stirling’s approximation is just an approximation, and can be further refined. Instead of submitting (N/e)N to the troll, you could have multiplied this by √(2ÐÐÐÐЬÐÐâºN) to get a very accurate approximation for N!, as shown in the graph. Solver Athena Hough similarly found that (N/e+1)N was a better approximation than (N/e)N over the domain of interest.
Finally, a few folks safely crossed the bridge without using or modifying Stirling’s approximation at all. In particular, solver Austin Shapiro picked five points spaced along the graph of log(N!) between 1 and 200, and found the unique quartic polynomial that passed through those five points. Austin’s approximation for N! was then 10 raised to this quartic polynomial, or 10^(0.000000119·N4 − 0.0000606·N3 + 0.0127·N2 + 0.82·N − 1.48). It was a noisier approximation, as shown by the wavy purple points in the graph, and it required more keystrokes. But how could the troll not appreciate Austin’s style?
Want more puzzles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at riddlercolumn@gmail.com.
