Wednesday 13 March 2013

WEDNESDAY, 13 MARCH 2013


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: