New sequences; comments on old; origin of problem?

[Richard Guy]

I'll also copy this to the editors, in
the hope that someone will get it into
proper OEIS shape, and even check the
hand calculation and copying.  But I'd
be glad to hear from anyone who can
locate the problem.     R.

Derek Kisman, a high school student who is
one of a group we're training for the Olympiad,
has recently produced a complete and elegant
solution to the following problem.

Given a square  n  by  n  array of dots,
what is the maximum number of edges in a
convex polygon whose vertices are members
of the array?

Here is the first not-immediately-obvious
case,  n = 5:

           . o o . .
           o . . o .
           o . . . .
           . o . . o
           . . . o o

Can anyone locate where I got the problem
from?  I read it somewhere in the case
n = 2004, so it was presumably used in, or
suggested for, some Olympiad competition
(possibly a British one) last year.  I
seem to recall it was quoted in an article
about problems in general.

Define the cost  c  of an edge joining
x1 y1  to  x2 y2  to be the Manhattan
metric   |x2 - x1| + |y2 - y1|
so that the total cost of a polygon is
at most   4(n - 1)

Optimal solutions contain  4k  edges
chosen with minimal cost

     1 2  3   4     5     6       7
c = 1 2 3 3 4 4 5 5 5 5 6 6 7 7 7 7 7 7 ...

where each value of  c  appears  phi(c)
times.  This is A038567, though its
connexion with this problem isn't mentioned.
The cumulative sum of this sequence,

1 3 6 9 13 17 22 27 32 37 43 49 56 63 ...

agrees with  A002815  as far as 56 63 70 77
but then continues 85 93 102 111 ...
instead of  70 77 84 91 99 107 115 123 132
141 150 159 168 177 187 197 207 217 228 239
250 261 272 283 294 305 316 327 339 351 363
375 388 401 414 427 440 453 466 479 492 505
518 531 545 559 573 587 601 615 630 645 660

so this is a new sequence.  The corresponding
values of  n  are one larger than these,
namely

2 4 7 10 14 18 23 28 33 38 44 50 57 64 71 78
85 92 100 108 116 124 133 142 151 169 178
188 198 208 229 240 251 262 273 284 295 306
317 328 340 352 364 376 389 402 415 428 441
454 467 480 493 506 519 532 546 560 574 588
602 616 631 646 661 676 691 706 721 726 742

and these are not in OEIS.  Important
subsequences of these two sequences are
obtained by accumulating  c * phi(c).

phi(c)  is  A000010, a very early specimen.

c * phi(c)  is  A002618, where it is
described as  phi(n^2) -- perhaps the
alternative form should be given and
maybe the connexion with the present
problem.

The accumulation 1 3 9 17 37 49 91 123
177 217 ... is  A011755. Should we
mention the connexion with this problem?

The corresponding values of  n  are one
larger, and don't appear in OEIS:

2 4 10 18 38 50 92 124 178 218 328 376
532 616 736 864 1136 1244 1586 1746 1998
2218 2724 2916 3416 3728 4214 4550 5362
5602 6532 7044 7704 8248 9088 9520 10852
11536 12472 13112 14752 ...

[Derek Kisman calculated as far as 1998
and was able to obtain the answer, 561
for  n = 2004, to the original problem]

So here is the real sequence: max no of
edges in a convex polygon on an  n by n
grid:

n = 0  1  2  3  4  5  6  7  8  9 10
     0? 1? 4  6  8  9 10 12 13 14 16

    11 12 13 14 15 16 17 18 19 20
    16 17 18 20 20 21 22 24 24 25

    21 22 23 24 25 26 27 28 29 30
    26 27 28 28 29 30 31 32 32 33

    31 32 33 34 35 36 37 38 39 40
    34 35 36 36 37 38 38 40 40 41

    41 42 43 44 45 46 47 48 49 50
    41 42 43 44 44 44 45 46 47 48 48 48

More terms can be calculated for
a reasonable fee, but we don't have
a slick way of getting them.  But
there probably aren't any more which
are as hard as showing that 45 edges
can't be attained for  n = 46.

I'll write this up and send a copy to
anyone who's interested.

   Best to all,   R.