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.