|
%I #364 Oct 24 2023 22:58:04
%S 1,16,28,38,49,60
%N Solution to stepping stone puzzle if we start with n 1's (see Comments).
%C 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.
%C a(1) - a(4) were found by _Thomas Ladouceur_ and _Jeremy Rebenstock_ by considering all the possibilities (by computer - see link to Python program).
%C 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
%C From _Robert Gerbicz_, Oct 08 2020: (Start)
%C a(n) = O(n*log(n)^2). Proof:
%C 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.
%C 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.
%C 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)
%C From _Robert Gerbicz_, Apr 26 2021: (Start)
%C a(n) < 714*n. Proof:
%C 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).
%C 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.
%C 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)
%C From _N. J. A. Sloane_, Aug 26 2022: (Start)
%C 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:
%C - Daniel Darroch, Jan 11 2022: a(n) <= 278*n. (See link)
%C - Daniel Darroch, Jan 11 2022, and _Robert Gerbicz_, Jan 12 2022: a(n) <= 183*n. (See link)
%C - _Tejo Vrush_, Jan 22 2022: a(n) <= 155*n. (See link)
%C - _Jonathan F. Waldmann_, Aug 17 2022: a(n) < 86*n + 32. (See link)
%C - _Jonathan F. Waldmann_, Oct 01 2022: a(n) < 79*n + C. (See link)
%C - _Robert Gerbicz_, Oct 05 2022: lim inf a(n)/n > 6 (Probably a(n) > 6.0128*n-5621 for all n.) See link
%C - _Skylark Xentha Murphy-Davies_, a(n) >= 6*n for n >= 3 (see link)
%C (End)
%C _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
%C 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
%H Daniel Darroch and Robert Gerbicz, <a href="/A337663/a337663_6.txt">a(n) <= 278*n and a(n) <= 183*n</a>
%H Robert Gerbicz, <a href="/A337663/a337663_10.txt">Proof that lim inf a(n)/n > 6</a>
%H Robert Gerbicz, <a href="/A337663/a337663.c.txt">C++ program to accompany above proof</a>
%H Andrew Howroyd, <a href="/A337663/a337663.txt">Illustration for a(5) = 49</a>
%H Peter Kagey and others, <a href="https://codegolf.stackexchange.com/q/212160">Extend the most recent "nice" OEIS sequence: stepping stone puzzle on a grid</a>, Code Golf Stack Exchange, October 2020.
%H Dmitry Kamenetsky, <a href="/A337663/a337663_1.txt">Some lower bounds for 7 <= n <= 9.</a> [Shows a(7) >= 67, a(8) >= 74, a(9) >= 81.]
%H Thomas Ladouceur, <a href="/A337663/a337663.jpg">Illustration for a(2) = 16</a>
%H Thomas Ladouceur, <a href="https://github.com/ladouce7/Stepping-Stones">Python (Jupyter) notebook for A337663</a> on Github.
%H Skylark Xentha Murphy-Davies, <a href="https://docs.google.com/spreadsheets/d/11IJKRH3hcWmT7eiNgRCZ6HEnCdWKFsUghECgpTSCYkw/edit#gid=0">Stones on an Infinite Chessboard in a Finite Spreadsheet</a> [Many lower bounds, including a(n) >= 6*n for n >= 3]
%H Hugo van der Sanden, <a href="https://github.com/hvds/seq/tree/master/A337663">Implementations in C and Perl</a>
%H N. J. A. Sloane, <a href="/A337663/a337663.gif">A lower bound of 6*n+3 for n >= 3</a>, based on the optimal construction for n=2 (black) and continuing the obvious pattern of the red squares. Discovered by Menno Verhoeven, Jan 10 2022, and mentioned in a comment on the "Stones on an Infinite Chessboard" video.
%H N. J. A. Sloane, <a href="https://youtu.be/9ogbsh8KuEM?t=692">Exciting New Numbers Sequences</a> (video of talk), Mar 05 2021.
%H N. J. A. Sloane, Brady Haran and Pete McPartlan, <a href="https://www.youtube.com/watch?v=m4Uth-EaTZ8">Stones on an Infinite Chessboard</a>, Numberphile video (2022).
%H N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, pp. 16-18.
%H Mihael Tunik, <a href="/A337663/a337663_8.txt">Lower bound for n = 7</a> [Shows a(7) >= 69.]
%H Tejo Vrush, <a href="/A337663/a337663_4.txt">a(n) <= 155*n</a>
%H Jonathan F. Waldmann, <a href="/A337663/a337663_3.txt">a(n) < 86*n + 32</a>
%H Jonathan F. Waldmann, <a href="/A337663/a337663_7.txt">a(n) < 79*n + C</a>
%H Mattias de Zalenski, <a href="/A337663/a337663_2.txt">Some lower bounds for 7 <= n <= 9.</a> [Shows a(7) >= 68, a(8) >= 76, a(9) >= 82.]
%H Al Zimmermann, <a href="http://azspcs.com/Contest/SteppingStones">Stepping Stones Programming Contest</a>, August, 2022.
%H Al Zimmermann, <a href="/A337663/a337663_11.txt">12 solutions showing that a(7) >= 71.</a> [Results from his programming contest, added by _N. J. A. Sloane_, Jan 07 2023]
%H Al Zimmermann, <a href="/A337663/a337663_12.txt">Results from Programming Contest listing lower bounds 71, 80, 90, 99, 109, 118 for n = 7...12</a>
%F From _Andrew Howroyd_, Oct 08 2020: (Start)
%F a(n) >= 5*n - 4.
%F Proof: This follows by continuing the following simple construction:
%F +----+----+----+----+----+----+----+----+----+----+
%F | | | 4 | | | | | | 14 | |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | 3 | 1 | 5 | | | | 13 | 1 | 15 |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | 2 | | 6 | | | | 12 | | 16 |
%F +----+----+----+----+----+----+----+----+----+----+
%F | 1 | | | | 7 | | 11 | | | |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | | | | 8 | 1 | 10 | | | |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | | | | | 9 | | | | |
%F +----+----+----+----+----+----+----+----+----+----+
%F (End)
%F From _Skylark Xentha Murphy-Davies_, Jan 10 2022, added by _N. J. A. Sloane_: (Start)
%F a(n) >= 6*n - 6. [This has since been strengthened to a(n) >= 6*n for n >= 3 - see Comments and Link. - _N. J. A. Sloane_, Sep 14 2022]
%F Proof: This follows by continuing the following simple construction:
%F +----+----+----+----+----+----+----+----+----+----+
%F | 1 | | | | | | | | | |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | | 1 | | | 1 | | | 1 | 10 |
%F +----+----+----+----+----+----+----+----+----+----+
%F | | 18 | 17 | 16 | 15 | 14 | 13 | 12 | 11 | |
%F +----+----+----+----+----+----+----+----+----+----+
%F (End)
%F Menno Verhoeven, Jan 10 2022, has shown that a(n) >= 6*n+3 for n >= 3. See my "Lower bound of 6n+3" link. This is obtained by starting from the a(2)=16 configuration. He remarks that by starting from a larger configuration one can improve the constant term 3, although not the multiplier 6. For example, starting from the a(6) configuration gives a(n) >= 6n+24 for n >= 6. - _N. J. A. Sloane_, Jan 10 2022
%e Starting with n = 2 cells containing 1's the following strategy achieves a(2) = 16 (this is also shown in the link):
%e +----+----+----+----+----+----+
%e | 9 | 5 | 10 | 11 | | |
%e +----+----+----+----+----+----+
%e | | 4 | 1 | | | |
%e +----+----+----+----+----+----+
%e | 12 | 8 | 3 | 2 | | 16 |
%e +----+----+----+----+----+----+
%e | | | | 6 | 1 | 15 |
%e +----+----+----+----+----+----+
%e | | | 13 | 7 | 14 | |
%e +----+----+----+----+----+----+
%e Illustration for a(3) = 28 from _Fakih Karademir_, Aug 30 2022: (Start)
%e . 24 . . . . .
%e . 8 16 17 . . .
%e 15 7 1 . 19 . .
%e 22 . 6 2 . 20 .
%e . 28 . 3 1 . 25
%e . . . . 4 5 .
%e . . 21 . 9 18 23
%e . . 11 10 . . .
%e . 12 1 . . . .
%e . 26 13 14 . . .
%e . . . 27 . . . (End)
%e Illustration for a(4) = 38 from Arnauld Chevallier:
%e . . . . . . . . . . . . . . .
%e . 35 18 36 . 23 . 21 . 32 . . . . .
%e . . 17 1 . 14 9 . 12 20 . . . . .
%e . . 34 16 15 . 5 4 8 . . 26 27 . .
%e . . . . 31 . 10 1 3 19 25 . 1 28 .
%e . . . . . . 11 . 2 6 . 33 . 29 .
%e . . . . . . 24 13 22 1 7 . . . .
%e . . . . . . 37 . . 30 38 . . . .
%e . . . . . . . . . . . . . . .
%e From _Bert Dobbelaere_, Nov 01 2020: (Start)
%e Illustration for a(6) = 60:
%e . . . . . . . . . . . . . 47 24 48 .
%e . . . . . . . . . . . . . . 23 1 49
%e . . . . . . . . . . . . 41 . 22 . 50
%e . . . . . . . . 51 . 36 . 20 21 43 . .
%e . . . . . . . . 34 17 . 19 1 . . . .
%e . . . . . . . . 16 1 18 38 58 59 . . .
%e . . . . . 37 30 15 40 . 57 . . . . . .
%e . . . . . . 7 8 . . . . . . . . .
%e . . . 35 46 6 1 25 33 . . . . . . . .
%e . 60 32 . 3 2 9 . . . . . . . . . .
%e . . 28 4 1 31 11 45 . 52 . . . . . . .
%e . 42 14 10 5 . . 12 13 39 . . . . . . .
%e . 56 . 29 44 . . 1 26 . . . . . . . .
%e . . . . . . 55 54 27 53 . . . . . . .
%e (End)
%Y Cf. A340000, A342431, A342434, A350764, A350785, A350627.
%Y See A355903 for another version of the problem.
%K nonn,more,nice
%O 1,2
%A _N. J. A. Sloane_, Oct 07 2020, based on an email from _Thomas Ladouceur_ and _Jeremy Rebenstock_, Oct 06 2020
%E a(1)-a(4) confirmed by Arnauld Chevallier
%E a(5) from Code Golf user xash (see Code Golf Stack Exchange link). - _Peter Kagey_, Oct 08 2020
%E a(5) independently confirmed by _Andrew Howroyd_, Oct 08 2020
%E a(6) from _Bert Dobbelaere_, Nov 01 2020
%E a(6) independently confirmed by _Hugo van der Sanden_, Nov 05 2020
%E Deleted an unproved upper bound. - _N. J. A. Sloane_, Jan 14 2022
%E a(7) >= 71 was found by Mark Beyleveld, Aug 07 2023 (see Links). - _Al Zimmermann_, Jan 02 2023
%E The programming contest also produced the lower bounds 80, 90, 99, 109, 118 for n = 8, ..., 12, respectively (see Links). _Al Zimmermann_, Jan 05 2023
| 