login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A319018 Number of ON cells after n generations of two-dimensional automaton based on knight moves (see Comments for definition). 9

%I

%S 0,1,9,17,57,65,121,145,265,273,329,377,617,657,865,921,1201,1209,

%T 1265,1313,1553,1617,2001,2121,2689,2745,3009,3153,3841,3953,4513,

%U 4649,5297,5305,5361,5409,5649,5713,6097,6233,6881,6953,7353,7585,8713,8913,9961

%N Number of ON cells after n generations of two-dimensional automaton based on knight moves (see Comments for definition).

%C The cells are the squares of the standard square grid.

%C Cells are either OFF or ON, once they are ON they stay ON forever.

%C Each cell has 8 neighbors, the cells that are a knight's move away.

%C We begin in generation 1 with a single ON cell.

%C A cell is turned ON at generation n+1 if it has exactly one ON neighbor at generation n.

%C (Since cells stay ON, an equivalent definition is that a cell is turned ON at generation n+1 if it has exactly one neighbor that has been turned ON at some earlier generation. - _N. J. A. Sloane_, Dec 19 2018)

%C This sequence has similarities with A151725: here we use knight moves, there we use king moves.

%C This is a knight's-move version of the Ulam-Warburton cellular automaton (see A147562). - _N. J. A. Sloane_, Dec 21 2018

%C The structure has dihedral D_8 symmetry (quarter-turn rotations plus reflections, which generate the dihedral group D_8 of order 8), so A319019 is a multiple of 8 (compare A322050). - _N. J. A. Sloane_, Dec 16 2018

%C From _Omar E. Pol_, Dec 16 2018: (Start)

%C For n >> 1 (for example: n = 257) the structure of this sequence is similar to the structure of both A194270 and of A220500, the D-toothpick cellular automata of the second kind and of the third kind respectively. The animations of both CAs are in the Applegate's movie version.

%C Also, the graph of A319018 is a bit similar to the graph of A245540, which is essentially a 45-degree-3D-wedge of A245542 (a pyramid) which is the partial sums of A160239 (Fredkin's replicator). See "Plot 2": A319018 vs. A245540. (End)

%C The conjecture that A322050(2^k+1)=1 also suggests a fractal geometry. Let P_k be the associated set of eight points. It appears that P_k may be written as the intersection of four fixed lines, y = +-2*x and x = +-2*y, with a circle, x^2 + y^2 = 5*4^k (see linked image "Log-Periodic Coloring"). - _Bradley Klee_, Dec 16 2018

%C In many of these toothpick or cellular automata sequences it is common to see graphs which look like some version of the famous blancmange curve (also known as the Takagi curve). I expect that is what we are seeing when we look at the graph of A322049, although we probably need to go a lot further out before the true shape becomes apparent. - _N. J. A. Sloane_, Dec 17 2018

%C The graph of A322049 (related to first differences of this sequence) appears to have rather a self-similar structure which repeats at powers of 2, and more specifically at 2^10 = 1024. There is no central symmetry or continuity, which are characteristic properties of the blancmange curve. - _M. F. Hasler_, Dec 28 2018

%C The 8 points added in generation n = 2^k + 1 are P_k = 2^k*K where K = {(+-2, +-1), (+-1, +-2)} is the set of the initial 8 knight moves. So P_k is indeed the intersection of the rays of slope +-1/2 resp. +-2 and a circle of radius 2^k*sqrt(5). In the subsequent generation n = 2^k + 2, the new cells switched on are exactly the 7 "new" knight move neighbors of these 8 cells, (P_k + K) \ (2^k - 1)*K. The 8th neighbor, lying one knight move closer to the origin, has been switched on in generation 2^k, together with an octagonal "wall" consisting in every other cell on horizontal and vertical segments between these points (2^k - 1)*K, and all cells on the diagonal segments between these points, as well as 2 more diagonals just next to these (on the inner side) and shorter by 2 cells (so they are empty for k = 1). This yields 4*(2 + (2^k - 2)*(1+3)) new ON cells in generation 2^k, plus 8*(2^(k-1) - 2) more new ON cells on horizontal, vertical and diagonal lines 4 units closer to the origin for k > 2, and similar additional terms for k > 4 etc. - _M. F. Hasler_, Dec 28 2018

%H Rémy Sigrist, <a href="/A319018/b319018.txt">Table of n, a(n) for n = 0..2049</a>

%H David Applegate, <a href="/A139250/a139250.anim.html">The movie version</a>.

%H Nathan Epstein, <a href="https://giant.gfycat.com/OblongNextCalf.webm">Gfycat animation of sequence</a>.

%H M. F. Hasler, <a href="/A319019/a319019.html">Interactive illustration of A319018 and A319019</a>, Dec. 2018.

%H Bradley Klee, <a href="/A322050/a322050_1.png">Log-Periodic Coloring at stage 257</a>.

%H Bradley Klee, <a href="/A319018/a319018_3.png">Log-periodic coloring of the first quadrant, over the chair tiling</a>.

%H Rémy Sigrist, <a href="/A319018/a319018_2.png">Illustration of the structure at stage 7</a>

%H Rémy Sigrist, <a href="/A319018/a319018.png">Illustration of the structure at stage 257</a>

%H Rémy Sigrist, <a href="/A319018/a319018_1.png">Colored illustration of the structure at stage 257</a> (where the hue is a function of the stage)

%H Rémy Sigrist, <a href="/A319018/a319018.gp.txt">PARI program for A319018</a>

%H N. J. A. Sloane, <a href="/A319019/a319019.png">Hand-drawn sketch showing terms through about the eighth shell</a>, but using offset a(0)=1. Illustrates the octagonal "castle walls".

%H N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, <a href="https://vimeo.com/314786942">Part I</a>, <a href="https://vimeo.com/314790822">Part 2</a>, <a href="https://oeis.org/A320487/a320487.pdf">Slides.</a> (Mentions this sequence)

%H <a href="/index/Ce#cell">Index entries for sequences related to cellular automata</a>

%H <a href="/index/To#toothpick">Index entries for sequences related to toothpick sequences</a>

%F No formula or recurrence is presently known. See A322049 for a promising attack. - _N. J. A. Sloane_, Dec 16 2018

%F a(n) = Sum_{k=1..n} A319019(n) = 1 + 8*Sum_{k=2..n} A322050(n) for n >= 1. In particular, a(n) - 1 is divisible by 8 for all n >= 1. - _M. F. Hasler_, Dec 28 2018

%o (PARI) A319018(n)=sum(i=1,n,A319019[i]) \\ with array A319019=A319019_upto(N) precomputed with sufficiently large N. - _M. F. Hasler_, Dec 28 2018

%Y Cf. A151725, A319019 (first differences).

%Y For further analysis see A322048, A322049, A322050, A322051.

%Y See A322055, A322056 for a variation.

%Y See also A139250, A147562, A194270, A220500.

%K nonn

%O 0,3

%A _Rémy Sigrist_, Sep 08 2018

%E Deleted an incorrect illustration. - _N. J. A. Sloane_, Dec 17 2018

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 24 13:48 EDT 2019. Contains 326279 sequences. (Running on oeis4.)