Richard Guy has died

He lived to the prime old age of 103:

https://en.wikipedia.org/wiki/Richard_K._Guy

I believe this is Richard Guy of "Winning ways for your mathematical plays". It's definitely worth browsing if you're interested in game theory or recreational math.

professional and recreational mathematician, professor, and chessologist.

https://en.m.wikipedia.org/wiki/Richard_K._Guy

I once had a signal processing problem, for which I heard a rumor that Guy had solved (or at least investigated) in one of his books.

The problem reduces to finding the shortest ordered sequence of integers drawn from 1..N, whose content and pairwise differences contain a complete set of all the integers from 1..N.

Obviously the complete 1..N is a trivial solution, so the interesting solutions must be shorter than that.

Without loss of generality, from symmetry we always put an interval of 1 at beginning. We write the solution in a line, with the differences calculated below in a lattice. The aim is to get every integer up to N appearing in the triangle somewhere.

So the simplest non-trivial solution is:

  [1 3]
    2

Where [13] is the solution, and 2 is the distance 3-1.

The relative effectiveness of the solution can be measured as length/n, e.g. [13] is 2/3 = 0.66. The ratio must be less than 1 to be non-trivial and interesting.

The next solutions have the same length (is N odd or N even easier to achieve, due to symmetry arguments?):

  1 2 4       3/4 = 0.75
   1 2
    3
  
  1 3 5       3/5 = 0.6
   2 2
    4

There can be more than one non-symmetric solution, e.g. for N=6 even:

  1 2 3 6      4/6 = 0.66
   1 1 3
    2 4 
     5
    
  1 3 4 6      
   2 1 2
    3 3
     5

N=7 odd has symmetric solutions:

  1 3 6 7       4/7 = 0.57
   2 3 1
    5 4
     6

  1 2 5 7       
   1 3 2
    4 5
     6

These are equivalent, and we disambiguate by putting the shortest interval 12 first, so 1257 implies 1367 is also a solution.

The N=8 solution is the same length as N=7, and it has the lowest ratio of 0.5:

  1 2 5 8           4/8  = 0.5
   1 3 3
    4 6
     7

What are some non-trivial solutions for N > 8 ?

  1 2 3 7 9         5/9 = 0.56
   1 1 4 2
    2 5 6 
     6 7
      8
    
  1 2 3 5 8 10      6/10 = 0.6
   1 1 2 3 2
    2 3 5 5
     4 6 7
      7 8 
       9

  1 2 3 5 9 11      6/11 = 0.55
   1 1 2 4 2
    2 3 6 6 
     4 7 8
      8 9
       10

...

I never looked-up Guy's literature (this was long before the internet), and I have not returned to the problem until now.

Does anyone know the relevant reference by Guy?

In fact, there were many other engineering considerations, to do with simplicity, small cost difference, failures & replacements, variable operational lengths, and especially noise reduction, which rendered the mathematical problem moot.

Can anyone guess my original signal processing application :)

The easiest answer is pretty good in most operational respects, and so represents the preferred engineering solution: just use the complete sequence 1..N and forget the cute math.

However, there seems something beautiful about that compact N=8 sequence with ratio 0.5:

  1 2 5 8