Mind the gap

An interesting video on the gaps between consecutive primes:

What grabbed my attention most was what Conway dubbed Jumping Champions: the gap size or sizes which are most common among primes under some upper limit n. For the first few primes the most common gap size is 2, but then 4 starts to become as common or more common for a little while, and then above n = 179, 6 starts to be a contender; for n above 947, 6 is the undisputed jumping champion — up until about n = 1.74×1035, after which 30 is the new champion. Until 210 is, around n = 6.4×10425.

The way I like to think about it is this:

Consider six consecutive numbers starting with a multiple of 6: 6m, 6m+1, 6m+2, 6m+3, 6m+4, and 6m+5. Of these 6m, 6m+2, and 6m+4 are even, so cannot be prime, and 6m and 6m+3 are multiples of 3, so cannot be prime. Then the only ones that could be prime are the second and the sixth, 6m+1 and 6m+5. (We’re just doing the first two steps of the Sieve of Eratosthanes here, and using six consecutive numbers because 6=2×3.) Of course the next six numbers start with the next multiple of 6, so the second and sixth of them are also prime candidates, and so on. What this means is that for x to be a prime number (higher than 3), x must equal 1 or 5 modulo 6.

What you can see is that for two numbers to be primes differing by 2 (twin primes), the lower one must equal 5 modulo 6. For them to be primes differing by 4 (cousin primes), the lower one must equal 1 modulo 6. But to be primes differing by 6 (sexy primes), the lower one can equal either 1 or 5 modulo 6.

From that you’d expect, for a large enough upper bound, the number of twin and cousin primes should be about equal and the number of sexy primes should be about double that. And that’s true. For numbers up to 10000, there are 205 pairs of twin primes, 203 cousin prime pairs, and 411 sexy prime pairs.

Now, for the gap between two consecutive primes to be 2, the first must equal 5 modulo 6, and for it to be 4, the first must be 1 modulo 6, but for it to be 6, the first must be either 1 or 5 modulo 6, and there must not be another prime 2 or 4 above it. For numbers below a few hundred, if you have two primes differing by 6, there’s a good chance there’s another prime between them, so you don’t have that many gaps of 6 between consecutive primes. But as you go to larger and larger numbers, the density of primes drops until you get to a point where primes separated by 6 are unlikely to have a prime between them. Once that happens, the larger number of sexy prime pairs means gaps of 6 become more common than gaps of 2 or 4, so 6 becomes the jumping champion.

But you can play the same game with three steps of the Sieve. Look at 30m, 30m+1, 30m+2 … 30m+29, knock out the multiples of 2, 3 and 5 (we’re using 30 numbers because 2×3×5=30), and you’re left with eight prime candidates — equal to 1, 7, 11, 13, 17, 19, 23, or 29 modulo 30. Of those you find six with another prime candidate 6 higher, six with a prime candidate 12 higher, six again with 18 higher and six with 24 higher. But all eight have prime candidates 30 higher. (There seems to be no cute name for pairs of primes differing by 30.)

So, similarly to the above, you’d expect prime pairs differing by 30 to outnumber pairs differing by 6, 12, 18, or 24, by about a factor of 8/6 = 1.33 and again, that’s right: for numbers up to 10000, there are 411 primes differing by 6, 404 differing by 12, 417 differing by 18, 404 differing by 24, and 536 differing by 30 — just about exactly 1.33 times larger. And for small upper bounds the likelihood of two primes differing by 30 to have no primes between them is small, but for larger and larger numbers the density of primes drops and eventually most primes differing by 30 do not have any primes in between. And then 30 becomes the jumping champion. Unfortunately not until about 1.74×1035, though, and enumerating all primes to that point and verifying 30’s championship would be just a little infeasible.

Or a lot, really.

And then 210=2×3×5×7 takes over, by similar reasoning, but very much further up the number line. And so on and on.

Car and diamond

The latest Matt Parker’s Maths Puzzle is from James Grime and goes something like this: I have five items — a Car, a Diamond, a Goat, a pot of Bogies, and a Poke in the eye (or C, D, G, B, and P, as I will abbreviate them from here on). You can request one or more of these items, but for each item you request, I’ll instead give you two other items. Or rather, two other items will change hands, because if I’ve already given you an item I can’t give it to you again — instead you give it back to me. Each item you request results in two and only two items changing hands, and each item changes hands if either of two and only two items is requested.

So if requesting u gets you v and w, and requesting x gets you y and z, then requesting u and x gets you v, w, y, and z unless two of those items are the same, in which case you’ll just get the other two, or if two are the same and the other two also are the same, you’ll get nothing.

In particular, if you request C and G, you’ll get B and P. If you request C, B, and P, you’ll get C, B, and P, but also D.

What’s the shortest request you can make that will result in you getting C and D, but nothing else?

First, it’s easy to see that if you request G, B, and P, you’ll get C and D. Requesting C and G gets you B and P, and if you then go on to request C, B, and P, you’d get C, B, P, and D, but you already have B and P so you give those back and end up with C and D. But there’s no point in requesting C twice; the second request will just undo the first request. So if you drop the requests for C and just ask for G, B, and P, you’ll get C and D.

But are there shorter requests that will work? To answer that, let’s try to work out the complete set of rules that say what items are given for each item that is requested.

We can represent such a set of rules as a matrix. Rows represent requests and columns represent bequests. Each entry is 0 or 1. Each row must have exactly two 1s and so must each column. So for instance

\begin{matrix} & C & D & G & B & P \\ C & 0 & 0 & 1 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 1 & 0 & 0 & 0 & 1 \\ B & 0 & 1 & 0 & 0 & 1 \\ P & 0 & 1 & 0 & 1 & 0 \end{matrix}

would mean if you request C (first row) you get G and B; if you request D (second row) you get C and G, and so on. Notice that the main diagonal is all zeros, because you never get the item you request. And in this case if you ask for C and D, you end up with C and B, with the G from the C request canceling out the G from the D request. More generally if you ask for several items you end up with those items that appear an odd number of times in the corresponding rows.

There are, if the Python script I wrote is to be believed, 216 such matrices possible. Not something I’d want to do by hand, I’m sure I’d make mistakes. But how many of these result in BP if you request CG? That we can do by hand pretty easily. One of two things has to happen. The first is that if you request C you get B and something else, and if you request G you get P and the same something else. But that something else has to be D, because it can’t be C or G — you never get the thing you asked for. In that case we now have two rows, one column, and the main diagonal of the matrix:

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D &   & 0 &   &   &   \\ G & 0 & 1 & 0 & 0 & 1 \\ B &   & 0 &   & 0 &   \\ P &   & 0 &   &   & 0 \end{matrix}

Now consider the B and P columns. B must have a 1 in the D row and a 0 in the P row, or vice versa, and P must have a 1 in the D row and a 0 in the B row, or vice versa. So we have four possibilities:

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 &  & 1 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 0 \\ P & & 0 & & 0 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 1 \\ P & & 0 & & 0 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 0 \\ P & & 0 & & 1 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & & 0 & & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & & 0 & & 0 & 1 \\ P & & 0 & & 1 & 0 \end{matrix}

There’s only one way to complete the first of these matrices but two ways for each of the other three, for a total of seven:

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 0 & 1 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 1 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 0 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 0 & 0 & 1 & 0 & 1 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 1 & 0 & 0 & 1 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 1 & 0 & 0 & 0 & 1 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 1 & 0 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 0 & 1 & 0 \end{matrix}

The second possibility is that if you request C you get P and D, and if you request G you get B and D. That leads to seven more matrices, which you can get from the above seven by interchanging the B and P rows and columns.

Now we can inspect these matrices to see which give you CBPD if you request CBP. Only one of the first seven does:

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 1 & 0 \\ D & 1 & 0 & 0 & 1 & 0 \\ G & 0 & 1 & 0 & 0 & 1 \\ B & 0 & 0 & 1 & 0 & 1 \\ P & 1 & 0 & 1 & 0 & 0 \end{matrix}

as does its corresponding entry in the second seven:

\begin{matrix} & C & D & G & B & P \\ C & 0 & 1 & 0 & 0 & 1 \\ D & 1 & 0 & 0 & 0 & 1 \\ G & 0 & 1 & 0 & 1 & 0 \\ B & 1 & 0 & 1 & 0 & 0 \\ P & 0 & 0 & 1 & 1 & 0 \end{matrix}

(And Python confirms: 14 matrices give you the first result, of which 2 also give you the second.)

From the information given we can’t determine which of these two matrices is in use, but it doesn’t matter. Neither gives you CD if you request any single item, and both give you CD if you request GBP, as expected. But both also give you CD if you request… CD!

At which point insight strikes (it did me, anyway — maybe you got there quicker) and you realize there was an easier path to this solution.

We know requesting GBP gets you CD.

But that means out of G, B, and P an odd number of them (specifically 1, because the maximum would be 2) give you C. And an odd number give you D, while an even number (either 0 or 2) give you G, B, or P. 

However, we know an even number of all five items — specifically 2 — give you any of the five items. So if an odd number of G, B, and P give you an item, so do an odd number of C and D, and if an even number of G, B, and P give you an item, so do an even number of C and D. This means the result of GBP must be the same as the result of CD. More generally, the result of any set of requests must be the same as the result of the complementary set of requests.

So CD must give you CD.

Is there a single item you can request that would give you CD? No. Neither C nor D will: First, because requesting an item gives you two other items; second, because if C gives you CD then that means D gives you nothing, which is false, and vice versa. Nor will G, B, or P, because if one did, then the other two would have to give you the same two items out of G, B, P. But that again would require violating the rule that requesting an item does not give you that item.

Therefore CD is the smallest request that gives you CD.

One more thing: What if we relax the rule that requesting an item doesn’t give you that item? So, for instance, requesting C could give you CG. Then the above argument still holds, except for the part about none of G, B, or P giving you CD. But that’s still true. G cannot give you CD because then there would be no way for CG to give you BP. And if one of B and P gave you CD then G (as well as the other of B and P) would have to give you two of G, B, and P. If it gave you BP then C would have to give you nothing. If it gave you GB, C would have to give you GP and then CD could not give you CD. Likewise if it gave you GP, C would have to give you GB and again CD could not give you CD. So even without that rule, CD would be the smallest request that gives you CD. Python confirms it: With the relaxed rule, there are 2040 valid matrices, of which 90 satisfy CG gives you BP, 8 also satisfy CBP gives you CDBP, and all 8 have CD as the shortest request that gives CD.

Here’s a Google spreadsheet.

How odd

The new Matt Parker puzzle asks, How odd is Pascal’s triangle? Or more specifically, what percentage of the entries in the first 128 rows are odd?

Since we don’t care about the numbers themselves, just how odd they are, we can consider a modified triangle where the rule is: Each entry is the XOR (exclusive or) of the two above it. Using ones and zeroes, this triangle looks like:

Row 11
211
3101
41111
510001
6110011
71010101
811111111

An entry in this triangle is 1 if and only if the corresponding entry in Pascal’s triangle is odd. If you examine this and carry it forward, you realize this is starting to look like another famous mathematical triangle, the Sierpiński triangle. As you go to more and more rows, it gets closer to the Sierpiński triangle’s fractal nature.

In fact, what you notice is that at every row that’s a power of 2 (row 1, 2, 4, 8, 16, 32…) every entry in the row is 1. And at that point the uppermost half of the triangle is replicated twice in the lowermost half, with an “empty” triangle (all zeros) in between. For instance:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–2 have a triangle of size 2, composed of three 1s; rows 3-4 are two such triangles, with a “triangle” of size 1, composed of a single 0, in between. And then:

11
211
3101
41111
510001
6110011
71010101
811111111

Rows 1–4 have a triangle of size 4, composed of nine 1s and a 0; rows 3-4 are two such triangles, with a triangle of size 3, composed of six 0s, in between. And so on.

More generally, when you reach row 2^n, the first 2^{n-1} rows contain a triangle of size 2^{n-1} and the last 2^{n-1} rows contain two such triangles with an “empty” triangle of size 2^{n-1}-1 in between.

But that just means the number of 1s in the first 2^n rows is 3 times the number in the first 2^{n-1} rows. There’s one 1 in the first 1 rows, 3 in the first 2 rows, 9 in the first 4 rows, and so on: 3^n in the first 2^n rows. The total number of entries in m rows is T(m) = m(m+1)/2, and the percentage of odd entries is just the ratio of these two: P(n) = 2\times 3^n/(2^n(2^n+1)):

2^n3^nT(2^n)P(n)
233100%
491090%
8273675%
168113659.56%
3224352846.02%
64729208035.05%
1282187825626.49%

As you go to more and more rows, the percentage of odd entries gets smaller. For large n, the first 2^n rows contain a triangle of zeros filling up the middle one quarter (slightly less) of the triangle, and each of the other three quarters is a triangle containing a triangle of zeros filling up the middle one quarter, with the other three quarters being a triangle containing a triangle of zeros… well, turtles all the way down. As n approaches infinity, P(2^n) approaches equality with P(2^{n-1}). But the big triangle is a quarter empty and three quarters nonempty, so P(2^n) = 3P(2^n)/4, so in the limit, P(2^n) = 0.

Or, using the formula, \lim_{n \to \infty} P(2^n) = \lim_{n \to \infty} 2\times 3^n/(2^n(2^n+1)) = \lim_{n \to \infty} 2\times (3/4)^n = 0.

If the above triangle reminds you of a 1-dimensional cellular automaton, by the way, that’s because it is one. Specifically, you can think of it as a skewed version of Rule 60 or Rule 102 (with successive rows shifted half a cell left or right, respectively), or, if you regard adjacent numbers as actually having zeros between them, it’s Rule 90. These are the three rules in which the next state of a cell is the XOR of two of the three cells in its neighborhood.

The rise and/or fall

The latest Matt Parker’s Maths Puzzle is in fact by Zoe Griffiths and asks about increasing or decreasing sequences of length m within permutations of n cards (or numbers). So for example, with n=4, the permutation

1 3 2 4

contains the two increasing sequences of length m=3:

1 3 4
1 2 4

as well as two length 3 sequences that do not increase or decrease:

1 3 2
3 2 4

and no length 3 sequences that decrease. For n=4, how many of the 24 permutations contain no sequences of length 3 that decrease or increase? (That’s an awkward phrase, so from here on let’s call a sequence that either decreases or increases a run, and one of length 3 a 3-run. So we’re asking how many permutations contain no 3-runs. Answer below:)

Continue reading “The rise and/or fall”

Metric’s furlong

No, metrology isn’t math, but let’s not let that stop us.

The International System of Units, or SI, justifiably prides itself on being easier and more logical than Imperial units (in which 12 inches are a foot, 3 feet are a yard, 5.5 yards are a rod, 4 rods are a chain, 10 chains are a furlong, and 8 furlongs are a mile). But have you ever looked closely at SI prefixes? I’ve used SI units most of my life but the prefixes hecto-, deka-, and deci- rarely, which is part of why I didn’t know the prefix for deka- until I came across it today. Here are the prefixes:

Factor Name Symbol |Factor Name Symbol
1024 yotta Y |10-1 deci d
1021 zetta Z |10-2 centi c
1018 exa E |10-3 milli m
1015 peta P |10-6 micro µ
1012 tera T |10-9 nano n
109 giga G |10-12 pico p
106 mega M |10-15 femto f
103 kilo k |10-18 atto a
102 hecto h |10-21 zepto z
101 deka da |10-24 yocto y

If you take a look at the first and last, they’re for the factors 10^{24} and 10^{-24}, a complementary pair one might say, and the names “yotta” and “yocto” are related, and the symbols are an uppercase and lowercase Y respectively. Similarly zetta, Z, and zepto, z. Nice pattern. Be a shame if something happened to it.

So next we have exa, E, and atto, a. Wait, what happened?

Well, at least we have the pattern that the large prefixes are uppercase and the small ones are lowercase. That holds strictly true, except that the division between “large” and “small” isn’t in the middle of the system, between 10^1 and 10^{-1}; it’s between 10^6 and 10^3. There’s two more pairs of prefixes using upper/lowercase versions of the same letter: peta (10^{15}) and pico (10^{-12}), which are not complementary factors, and mega (10^{6}) and milli (10^{-3}), likewise. Chaos!

Every prefix is a single Roman letter.

Well, except for micro, which is Greek, µ.

And except for deka, which is two letters, da. No wonder no one likes you, deka.

Well, logically, there shouldn’t even be a deka, or hecto, deci, or centi, since they’re the only prefixes not corresponding to a power of 1000, but look, that’s a feature, not a bug, okay?

Imperial has furlongs, and it has teaspoons, tablespoons, ounces, cups, pints, quarts, gallons, here’s good luck to the half barrel, and so on, and it’s a mess which SI avoids with factors of 10 and prefixes. Except the prefixes are a mess. Can we start over? Is it too late to start over? It is, isn’t it?

Round the ellipse and back again

Here’s my best approximation of the perimeter of an ellipse.

One thing you might notice is most of the approximations Matt presents get progressively worse as a/b increases. Matt’s best one’s percent error does bounce around for a bit but then it takes off too for a/b > 3.6.

But that’s sort of the nature of approximations, when what you’re trying to approximate increases without bound: If your approximation doesn’t capture the exact behavior (and if it does, it’s not really an approximation, is it?) then it’ll necessarily diverge from the correct value by more and more. Really the best you can hope for is to get a good approximation within some bounds, knowing it’ll go increasingly bad once you’re far enough outside those bounds.

So I thought I’d see if I could get the divergence to occur much further out than a/b > 3.6, and it seemed to me if I wanted a better (in the sense of more accurate, not more beautiful) formula than Ramanujan’s, I should start with Ramanujan’s and fix it up.

Ramanujan’s approximation is:

p_{ram} = \pi(3(a+b)-\sqrt{(3a+b)(a+3b)})

I cracked open a spreadsheet and found that if \delta = p_{true}-p_{ram} then for b = 1 and 3 < a < 20, \delta^{0.62} is approximately linear in a. After a bunch of manipulation I got the corrected approximation

p_{corr} = \pi(3(a+b)-\sqrt{(3a+b)(a+3b)} + qb(a/b-3)^r)

where q = 0.0004714 and r = 1.6156.

This formula doesn’t work for a/b < 3, but if my numbers for the “exact” perimeter (series sum to 20 terms) are correct, then for 3 \le a/b < 17.5, the average absolute percent error is about 0.0012%. Beyond that it starts to diverge. Here’s the percent error, in red, along with the percent error for Ramanujan’s formula, in blue.

And here’s a Python function to calculate the corrected approximation (for a/b > 3, otherwise it returns Ramanujan’s approximation):

#!/usr/bin/python

from sys import argv
from math import pi

def ellper (a, b):
    q = 0.0004714
    r = 1.6156

    pram = pi*(3*(a+b)-((3*a+b)*(a+3*b))**0.5)
    return pram + pi*(q*b*(a/b-3)**r) if a/b >= 3 else pram

    
a = float(argv[1])
b = float(argv[2])

print ellper (a, b)

Two, three, four

Last year was a big year for the sum of three cubes problem, which asks whether all numbers not of the form 9k+4 or 9k+5 can be written as the sum of the cubes of three (positive, negative, or zero) integers, a^3+b^3+c^3. It’s a hard problem. The smallest solution for 42 is

42 = (-80\ 538\ 738\ 812\ 075\ 974)^3 + 80\ 435\ 758\ 145\ 817\ 515^3 + 12\ 602\ 123\ 297\ 335\ 631^3

A superficially similar problem is to find ways to write an integer N as the sum of a square, a cube, and a fourth power: N = a^2+b^3+c^4. As with the three cubes problem, we allow b to be negative, though obviously there’s nothing to be gained by considering negative values for a or c.

It’s not at all obvious all numbers can be so written, or that they can’t, or which numbers can’t if there are any, or whether it’s harder or easier to find such representations than it is to find sums of three cubes. Of course any number that is itself a square, cube, or fourth power has a solution using zero for the other two powers, and any number that is one or two more than a square, a cube, or a fourth power is trivial as well, as is any number that is one less than a square or a fourth power. And compared to the three cubes problem, the search space here is in some sense smaller since we require 0 \le a^2 \le (N-b^3) and 0 \le c^4 \le (N-b^3).

In fact all positive numbers up to 100 except for one have solutions with relatively small numbers: the worst of them, in the sense of having a large minimum value for W = a^2+|b|^3+c^4, is 75 = 171^2+(-31)^3+5^4. The exception is this one:

67 = (213\ 662)^2+(-6\ 337)^3+676^4

It’s reminiscent of the three cubes problem in that you have this much harder number embedded among much easier ones. But it’s nowhere near as hard as 42 as a sum of three cubes.

For the numbers -10 000 through 10 000 a brute force Python script quickly turns up solutions for all. The one with largest W (3 times the next largest) is -8\ 357 = (3\ 303\ 433)^2 + (-22\ 183)^3 + 239^4.

Is there a proof all numbers have solutions? Maybe. There is an easy (to follow) proof that every integer is a sum of two squares and a cube of an integer, and a proof (paywalled) that almost all positive integers are sums of a square, a positive cube, and a fourth power. Not having shelled out to read it — the paper’s ten pages long, so I infer it’s not an easy proof — I don’t know if it identifies all the exceptions; if it does, then finding solutions with negative b for those would prove our puzzle for positive N. In 71 years you’d think it would have been done by now, and perhaps extended to negative N, and maybe it has. But that’s all I’ve found so far. Finally, for expressing N as a^2+b^3+c^3, this paper reports no proof but there are solutions for all -4\ 000\ 000 \le N \le 2\ 000\ 000.

Take Away Triangles

Matt Parker calls his latest puzzle Take Away Triangles, though really it has nothing to do with geometry; it’s purely about numbers.

Consider a triple of integers (Parker doesn’t say they have to be positive, but he doesn’t say they don’t): (a, b, c). Without loss of generality, herein I’m going to require all such triples to be in nondecreasing order: a \le b \le c. Now make a new triple out of it using the three differences b-a, c-b, and c-a. These all are nonnegative, and of them c-a is the largest (in fact c-a = (b-a) + (c-b)), so the new triple is either (b-a, c-b, c-a) or (c-b, b-a, c-a). We’ll call this new triple the successor of the first, and the first is a predecessor of the second. Now of course we can find the successor of the successor, and the successor of the successor of the successor, and so on.

For instance, starting with (5, 7, 12), we get as its successors (2, 5, 7), then (2, 3, 5), then (1, 2, 3), and so on.

The basic puzzle is this: Find a triple whose members do not sum to 14, whose successor does sum to 14, as do all the successors in the chain after that.

Let’s approach this in three steps:

  1. Find all triples that do sum to 14 whose successor also sums to 14
  2. Identify all whose second and following successors also sum to 14
  3. Find all predecessors of those triples

All right. We want to find a triple (a, b, c) such that a+b+c = 2s (s is 7, but let’s keep it symbolic for now, and you’ll see why I put a factor of 2 there). Its successor has members b-a, c-b, and c-a, and we want them to sum to 2s too: b-a+c-b+c-a = 2c-2a = 2s, so c-a = s or a = c-s. We have b = 2s - a - c = 2s-(c-s)-c = 3s-2c. So triples of the form (c-s, 3s-2c, c) will work.

What values can we use for c? We need a \le b so c-s \le 3s-2c \implies c \le 4s/3, and b \le c so 3s-2c \le c \implies c \ge s. For s=7 that means 7 \le c \le 9. The only triples that sum to 14 whose successors also sum to 14 are:

  • (0, 7, 7), whose successor is (0, 7, 7)
  • (1, 5, 8), whose successor is (3, 4, 7)
  • (2, 3, 9), whose successor is (1, 6, 7)

Next step is easy. The second and third of these have second successors which do not sum to 14. The first is its own successor, and therefore all of its successors: It and all its successors sum to 14, and that’s the only triple with that property.

Now we just need a predecessor for (0, 7, 7), or better yet, all predecessors. Any that don’t sum to 14 will answer the puzzle. So we want (e, f, g) such that either

  • f-e = 0
  • g-f = 7 and
  • g-e = 7

or

  • f-e = 7
  • g-f = 0 and
  • g-e = 7

In the first case, e=f and f = g-7 so we have predecessors of the form (g-7, g-7, g). The second case works out to (g-7, g, g). So predecessors of the first kind include (-2, -2, 5), (-1, -1, 6), (0, 0, 7), (1, 1, 8), and (2, 2, 9). Predecessors of the second kind include (-2, 5, 5), (-1, 6, 6), (0, 7, 7), (1, 8, 8), and (2, 9, 9). Only (0, 7, 7) sums to 14. Any other triple of one of these forms solves the puzzle.

Now let’s consider some wider aspects.

First, given a triple (a, b, c) with a, b, c \ge 0, what are its predecessors? We want (e, f, g) such that either

  • f-e = a
  • g-f = b and
  • g-e = c

or

  • g-f = a
  • f-e = b and
  • g-e = c

In either case, a+b must equal c, so only triples for which that is true have predecessors. Then in the first case: f = a+e, g = b+f = a+b+e = c+e, and e is unconstrained, so the predecessors are (e, a+e, c+e) for all e. In the second case we get (e, b+e, c+e).

Second, given a starting triple, what’s the behavior of its successors? Can they go indefinitely without repeating? If they do repeat, what’s the period of the repetition?

A triple that is the successor of another triple must be of the form (x, y, x+y). The successor of that successor must be either ((y-x), (x+y)-y, (x+y)-x) or ((x+y)-y, (y-x), (x+y)-x). But these simplify to (y-x, x, y) or (x, y-x, y). In either case two of the second successor’s members are the first two members of the first successor. In particular, the third member of the second successor is the second member of the first successor.

What that means is the chain cannot continue indefinitely without repeating, because the third member cannot increase (except in the successor to the starting triple, and that only if the starting triple’s first member is negative). It’s bounded from above in all successors by its value in the starting triple’s successor and from below by zero, and the first and second members must be no larger and nonnegative, so there is only a finite number of triples that can occur in the successor chain, and eventually it must repeat.

We’ve seen the repetition period can be 1. If that is the case — if we reach a triple (x, y, x+y) which is its own successor — then the third member of its successor, (x+y)-x = y, must be equal to x+y implying x = 0. So the only self-succeeding triples are of the form (0, y, y).

Can the period be longer? The largest member cannot increase, so if it is x+y in the first triple in the repeating cycle and is to be x+y in some later triple in the cycle, it must be x+y in every triple in the cycle. In particular it must be x+y in the successor to the first triple of the cycle, so again x=0, the cycle’s first triple must be (0, y, y), and that is self-succeeding. So the period must be 1.

For any starting triple, then, the chain of successors after a finite number of steps reaches a triple of the form (0, y, y) and repeats that triple from there on.

Distancing uniquely

The latest Maths Puzzle from Matt Parker concerns itself with distancing, not socially but uniquely. Can you put three markers in a 3 by 3 square such that no two marker-to-marker distances are the same? You can:

Here A and B are 1 unit apart, B and C are √5 units apart, and A and C are 2√2 units apart. Not counting reflections and rotations, there are 5 distinct ways to put three markers in a size 3 square at unique distances:

Parker asks for a solution for six markers in a 6 by 6 square. I very quickly convinced myself that if there’s an intelligent, elegant way to get such a solution by pencil and paper, I wasn’t going to find it. Instead I wrote a Python script to find all solutions for any size square. Any size to a point, anyway.

How many ways are there to put n markers in an n by n square? If you number the positions 1 through n^2 then selecting n positions to receive markers amounts to choosing n out of n^2; the number of ways of doing so is \binom{n^2}{n} = n^2!/(n!(n^2-n)!). For 3 markers in a 3 by 3 square there are 84 ways. For 6 markers in a 6 by 6 square there are 1,947,792 ways. My Python script gets very slow very fast.

The way it works is this: There’s a subroutine that takes a string pattern like “*.*……” which is the concatenation of “*.*”, “…”, and “…” corresponding to:

The subroutine does nothing if it finds non-unique distances within the pattern. If the distances are unique and the number of markers is equal to the largest number previously seen with unique distances it adds the pattern to a list of solutions; if the number of markers exceeds the largest number previously seen, it erases the list of solutions and starts a new list with this pattern. Then it calls itself recursively to investigate patterns made by taking the original one and adding a marker at each of the rightmost empty positions. (In this case it checks “*.**…..”, “*.*.*….”, “*.*..*…”, “*.*…*..”, “*.*….*.”, and “*.*…..*”)

Actually it does the above only after looking at the eight possible rotations and reflections of the pattern and seeing whether it’s the lexicographically smallest of the eight.

In a 2 by 2 square you can put 2 markers, 2 different ways. (Adjacent to one another orthogonally or diagonally. Of course there is only one distance either way, so it’s unique.) In a 3 by 3 square you can put 3 markers 5 ways, as seen above. For 4 by 4: 4 markers, 23 ways. For 5 by 5: 5 markers, 35 ways.

So it looks as though the number of ways to put n markers in an n by n square just keeps increasing. Until you try it with 6. You can put 6 markers in a 6 by 6 square… only 2 ways. 7 markers in a 7 by 7 square — only 1 way. When you get to 8 markers in an 8 by 8 square, it can’t be done. At best you can put 7 markers, but there are 3350 different ways!

Having done that for squares, I modified the script to do other dimensions: Rows of n positions or cubes of n^3 positions. Rows are easy — the number of combinations grows slowly. Cubes grow very fast. Worse yet, checking all 48 possible rotations and reflections in three dimensions gets complicated, and once I finally got that code working, I discovered that even though checking for rotations and reflections cut way down on the number of positions it needed to examine, it was slower than examining all positions, because the reflection and rotation checking took so much time! Then I realized it’d make more sense to check for duplicate distances first, then check for rotations and reflections before doing the recursive calls, and that did speed things up somewhat, but not enough to make a lot of difference. There are probably smarter ways to do it in Python, and probably even smarter ways in C, but I’ll leave those to someone else to work out.

For rows I looked at sizes up to an arbitrary limit of 20. For squares and cubes I stopped when I got to a size that took more than about three hours. Successive size squares took about ten times as long, and successive size cubes about 200 times as long! The results:

dimensions ->123
size vmaxsolutionsmaxsolutionsmaxsolutions
2212231
32235420
431423636
53353574223
63762
74171
84573350
94138547
10430952
11455
1252
13511
14534
15578
165160
175292
1864
19612
20640

For instance, in a row of 5 positions, there are 3 ways to put 3 markers at unique distances. In a 5 by 5 square, there are, as said above, 35 ways to put 5 markers. In a 5 by 5 by 5 cube, there are 4223 ways to put 7 markers, and so forth.

The two solutions for 6 markers in 6 by 6 are:

Greeks and Romans and cards

Take the aces and face cards from a deck; you can arrange those sixteen cards in a square. But can you arrange them in a square in such a way that every rank and every suit appears in every row, every column, and both diagonals? You can. (Go try it, it’s not that hard.) How many ways? (That’s harder!)

A simpler problem is to ignore the suits and just have every row, column, and diagonal contain all four ranks. You can do that easily enough by trial and error, but how many ways can you do it?

Let’s suppose you make the top row A K Q J and see what solutions that leads to. Every other row, column, and diagonal has to be some permutation of A K Q J. In particular, the first column must be one of the permutations that begins with A. There are six such permutations:

A K Q J
A K J Q
A Q K J
A Q J K
A J K Q
A J Q K

But it can’t be A K Q J or A Q K J, because that would put two Js on one of the diagonals. So for the first row and column there are four possibilities:

A K Q J   A K Q J   A K Q J   A K Q J
K         Q         J         J
J         J         K         Q
Q         K         Q         K

Now, what goes in the third row, third column for the first of these? It shares a diagonal with an A, a row with a J, and a column with a Q, so it has to be a K:

A K Q J
K
J   K
Q     ?

Now what do you put in the fourth row, fourth column? Not an A or a K, because it shares a diagonal with them; not a Q, because it shares a row with that, and not a J, because it shares a column with that. There’s nothing you can put there. So the first column can’t be A K J Q.

In similar fashion you can eliminate A J Q K. The second row, second column must be Q, and then once again the fourth row, fourth column can’t be filled.

Try the second possibility:

A K Q J
Q ? 
J   ?
K     ?

The second row, second column has to be a J; the third row, third column must be a K; and the fourth row, fourth column is a Q.

A K Q J
Q J
J   K
K     Q

Then the remaining positions are similarly forced: A in row 2, column 3; then K in row 2, column 4; then A in row 3, column 4, and so on:

A K Q J
Q J A K
J Q K A
K A J Q

Likewise the third possibility allows only one completion:

A K Q J
J Q K A
K A J Q
Q J A K

So that’s it, those are the only two ways to do it with A K Q J in the first row. Any other solution then will have to be what you get if you take one of the A-K-Q-J solutions and permute the ranks. There are 24 such permutations, so there are 48 solutions.

This is an example of a Latin square. In fact the requirement that the diagonals contain all four suits is extra. A Latin square needs only to have all four in each row and column. Or all five or whatever — you can do Latin squares of any size.

Now if you pay attention to both rank and suit, and require each row and each column to contain all four of each, that’s a Graeco-Latin square. Again, that says nothing about the diagonals, but you can extend the requirement to them and still get solutions for squares of size 4.

The ranks have to form a Latin square and so do the suits. Replace A, K, Q, J with H, C, D, S (hearts, clubs, diamonds, spades) in the above squares and those are your possibilities for the suits. There are just two that have H, C, D, S in the top row:

H C D S   H C D S
D S H C   S D C H
S D C H   C H S D
C H S D   D S H C

But you can’t use the first possibility for both the ranks and the suits. Otherwise all the As will be Hs, all the Ks will be Cs, and so on. Likewise you can’t use the second possibility for both. But you can use the first for one and the second for the other, either way around:

AH KC QD JS   AH KC QD JS
QS JD AC KH   JD QS KH AC
JC QH KS AD   KS AD JC QH
KD AS JH QC   QC JG AS KD

And again, any other solutions have to be obtainable from these two by permuting the suits and permuting the ranks. There are 24 × 24 = 576 such permutations, so in total there are 1152 solutions.