Today is the $72^{nd}$ day of the year.

$72 = 13 + 17 + 19 + 23$ which means it is the sum of four consecutive primes, see A034963.

$72$ is a member of the following primitive Pythagorean triples:

$(65, 72, 97 )$

$(1295, 72, 1297)$

$72 = 2^3 \times 3^2$

The factorisation of $72$ above has a nice symmetry to it. It is of the form $n^{n+1} \times (n+1)^n$.

The first seven numbers of such a sequence are as follows:

$0^1 \times 1^0 = 0$

$1^2 \times 2^1 = 2$

$2^3 \times 3^2 = 72$

$3^4 \times 4^3 = 5184$

$4^5 \times 5^4 = 640000$

$5^6 \times 6^5 = 121500000$

$6^7 \times 7^6 = 32934190464$

Surely nobody has thought of putting that into the On-Line Encyclopedia of Integer Sequences?

Of course they have, it is A051443.

Imagine a ruler that instead of having marks at regular intervals only had them at irregular intervals but in a specific irregular way. One specific irregular way would be to have the marks at integer intervals but in such a way that no two pairs of marks are the same distance apart. An example of a ruler of this type would be one which had marks at $2, 3$ and $6$. The distances between the pairs are all different:

$3 - 2 = 1$

$6 - 2 = 4$

$6 - 3 = 3$

A ruler like this is called a Golomb Ruler for Solomon W. Golomb, see A003022.

Now consider a ruler with marks at $0, 1, 4$ and $6$. the distances between all the pairs of marks on this ruler are

$1 - 0 = 1$

$4 - 0 = 4$

$6 - 0 = 6$

$4 - 1 = 3$

$6 - 1 = 5$

$6 - 4 = 2$

Inspection shows that all possible distances up to the length of the ruler can be measured with this arrangement. A ruler like this is called a perfect Golomb ruler.

The number of marks on a Golomb ruler is referred to as its Order and the largest number is referred to as its Length$^*$. Which leads us to the definition of an Optimal Golomb ruler:

A Golomb Ruler is Optimal if there exists no shorter Golomb ruler of the same Order.

A003022 is a list of length of the optimal rulers for each value of $n$. From the relevant page in Wikipedia we can see that the Optimal ruler for eleven marks is $72$ units and has marks at either:

$0, 1, 4, 13, 28, 33, 47, 54, 64, 70, 72$

or

$0, 1, 9, 19, 24, 31, 52, 56, 58, 69, 72$

Consider calculating the distances between all these marks for the first arrangement.

0 | 1 | 4 | 13 | 28 | 33 | 47 | 54 | 64 | 70 | 72 | |

0 | 1 | 4 | 13 | 28 | 33 | 47 | 54 | 64 | 70 | 72 | |

1 | 3 | 12 | 27 | 32 | 46 | 53 | 63 | 69 | 71 | ||

4 | 9 | 24 | 29 | 43 | 50 | 60 | 66 | 68 | |||

13 | 15 | 20 | 34 | 41 | 51 | 57 | 59 | ||||

28 | 5 | 19 | 26 | 36 | 42 | 44 | |||||

33 | 14 | 21 | 31 | 37 | 39 | ||||||

47 | 7 | 17 | 23 | 25 | |||||||

54 | 10 | 16 | 18 | ||||||||

64 | 6 | 8 | |||||||||

70 | 2 | ||||||||||

72 |

A quick count shows that there are $10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 55$ values. We know that they are all different because this is the definition of a Golomb ruler. However, $55 < 72$ so there cannot be all possible distances between $1$ and $72$ represented on this ruler. We can conclude, therefore, that this is not a perfect Golomb ruler.

$^*$ Assuming it starts at zero. More technically the length is the difference between the largest and smallest number.

## No comments:

Post a Comment