cp's OEIS Frontend

Start with an infinite square grid. Each cell has eight neighbors. Place n 1's anywhere. Now place the numbers 2, 3, ..., m in order, subject to the rule that when you place k, the sum of its neighbors must equal k. Then a(n) is the maximum m that can be achieved.

a(1) - a(4) were found by Thomas Ladouceur and Jeremy Rebenstock by considering all the possibilities (by computer - see link to Python program).

Note that a(n) always exists, by definition. But it is possible that it is infinity. One consequence of the following argument is that a(n) < oo. - N. J. A. Sloane, Oct 08 2020

From Robert Gerbicz, Oct 08 2020: (Start)

a(n) = O(n*log(n)^2). Proof:

Assume k > 1. Since the square containing k is the sum of its neighbors, one neighbor will be at most k/2. Continuing this (with the smallest term from the sum): if k < 2^(d+1) then one term within distance d from the square containing k will be at most 1, hence exactly one.

But n squares (containing ones) cover at most (2*d+1)^2*n squares within distance d. So for all d > 0, min(2^(d+1)-2, a(n)-1) <= (2*d+1)^2*n.

From this a(n) is finite because 2^d/d^2 is unbounded. Use the inequality for that d where 2^(d+1) < a(n) <= 2^(d+2), then (a(n)-4)/2 <= 2^(d+1)-2 = min(2^(d+1)-2, a(n)-1) <= (2*d+1)^2*n < 4*log_2(a(n))^2*n, and from a(n) < 4 + 8*log_2(a(n))^2*n it is easy to see that a(n) = O(n*log(n)^2). (End)

From Robert Gerbicz, Apr 26 2021: (Start)

a(n) < 714*n. Proof:

As above, assume k > 1; since the square containing k is the sum of its neighbors, one neighbor will be at most k/2. Continuing this in at most d=11 steps we get a square not larger than max(1, k/2048).

This means that the n ones and the integers in [2, k/2048] cover all integers from [2,k] within a distance of d=11. A single square covers at most (2*d+1)^2 squares, hence 23^2*(n + k/2048) >= k-1.

From this, k < 714*n, so a(n) is finite and a(n) < 714*n. (More precisely we got a(n) <= (1083392*n + 2048)/1519.) This idea works for any d > 8 steps, but gives the best upper bound for d=11. (End)

From N. J. A. Sloane, Aug 26 2022: (Start)

This entry has grown too long, so I have moved some of the comments to attached text files. At present these are, in chronological order:

- Charlotte Darroch, Jan 11 2022: a(n) <= 278*n. (See link)

- Charlotte Darroch, Jan 11 2022, and Robert Gerbicz, Jan 12 2022: a(n) <= 183*n. (See link)

- Tejo Vrush, Jan 22 2022: a(n) <= 155*n. (See link)

- Jonathan F. Waldmann, Aug 17 2022: a(n) < 86*n + 32. (See link)

- Jonathan F. Waldmann, Oct 01 2022: a(n) < 79*n + C. (See link)

- Robert Gerbicz, Oct 05 2022: lim inf a(n)/n > 6 (Probably a(n) > 6.0128*n-5621 for all n.) See link

- Skylark Xentha Murphy-Davies, a(n) >= 6*n for n >= 3 (see link)

(End)

Al Zimmermann has informed me that he is running a computer-programming competition (see link) in which contestants try to improve the lower bounds on a(n). This has already produced many improvements. Several contestants (the first was Mark Beyleveld) have shown that a(7) >= 71. Other lower bounds are a(8) >= 79, a(9) >= 89, a(10) >= 99, a(11) >= 109, a(12) >= 115. The full results will be announced when the competition ends in November 2022, and at that time the contestants may reveal that they also have proofs that some of these lower bounds are in fact the exact values. - N. J. A. Sloane, Aug 26 2022

See A350627 for several older problems that are similar to this, such as the Forest of Numbers (Bosque de Números) puzzle. - N. J. A. Sloane, Feb 05 2022

Start with an n X n square grid. Each cell has neighbors horizontally, vertically and diagonally. Place the numbers 1 to n anywhere. Now place the numbers n+1, n+2, ..., m in order, subject to the rule that when you place k, the sum of its neighbors must equal k. Then a(n) is the maximum m that can be achieved.

Start with an n X n square grid. Each cell has neighbors horizontally, vertically and diagonally. Place the numbers 1 and 2 anywhere. Now place the numbers 3, 4, ..., m in order, subject to the rule that when you place k, the sum of the numbers in the same row, column and diagonal must equal k. Then a(n) is the maximum m that can be achieved.

Start with an n X n square grid. Each cell has neighbors horizontally, vertically and diagonally. Place the numbers 1 and 2 anywhere. Now place the numbers 3, 4, ..., m in order, subject to the rule that when you place k, the sum of the numbers that a Chess Queen attack in the same row, column and diagonal must equal k. Then a(n) is the maximum m that can be achieved.

Start with an n X n square grid. Each cell has up to eight neighbors. Place the numbers 1 and 2 in any two cells of the grid. Then place a number in each remaining cell, in increasing order (not necessarily using consecutive integers), and with the rule that when you place the number k in a cell, the sum of the numbers in its neighboring cells must equal k. The goal is to fill the grid in such a way as to minimize the largest number placed.

This is similar to the Stepping Stones problem discussed in A337663, but predates it by more than 20 years.

Computer solutions by Dmitry Kamenetsky.

a(7) = 292, a(8) = 502, a(9) = 787 and a(10) 1391 not yet confirmed to be optimal.

Start with an n X n square grid. Each cell has neighbors horizontally and vertically. Place the numbers 1 and 2 anywhere. Now place the numbers 3, 4, ..., m in order, subject to the rule that when you place k, the sum of the numbers that a Chess Rook attack in the same row and column must equal k. Then a(n) is the maximum m that can be achieved.