The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A343992 Number of grid-filling curves of order n (on the square grid) with turns by +-90 degrees generated by folding morphisms that are perfect. 2
0, 1, 0, 1, 3, 0, 0, 6, 3, 20, 0, 0, 29, 0, 0, 56, 101, 108, 0, 392 (list; graph; refs; listen; history; text; internal format)



Curves of order n generated by folding morphisms are walks on the square grid, also coded by sequences (starting with D) of n-1 U's and D's starting with D, the Up and Down folds. These are also known as n-folds. In the square grid they uniquely correspond to folding morphisms, which are a special class of morphisms sigma on the alphabet {a,b,c,d}. (There is in particular the requirement that sigma(a) = ab...)). Here the letters a,b,c, and d correspond to the four possible steps of the walk. A curve C = C1 of order n generates curves Cj of order n^j by the process of iterated folding. Iterated folding corresponds to iterates of the folding morphism. Grid-filling or plane-filling means that all the points in arbitrary large balls of gridpoints are eventually visited by the Cj. Perfect means that four 90-degree rotated copies of the curves Cj started at the origin will pass exactly twice through all grid-points as j tends to infinity (except the origin itself).

It is a theorem that a(A022544(n)) = 0, and a(A001481(n)) > 0 for n>2.


Chandler Davis and Donald E. Knuth, Number Representations and Dragon Curves -- I and II, Journal of Recreational Mathematics, volume 3, number 2, April 1970, pages 66-81, and number 3, July 1970, pages 133-149. Reprinted and updated in Donald E. Knuth, Selected Papers on Fun and Games, CSLI Publications, 2010, pages 571-614.


Table of n, a(n) for n=1..20.

F. M. Dekking, Paperfolding Morphisms, Planefilling Curves, and Fractal Tiles, Theoretical Computer Science, volume 414, issue 1, January 2012, pages 20-37. Also arXiv:1011.5788 [math.CO], 2010-2011.


For n=2 one obtains Heighway's dragon curve, with folding morphism sigma:  a->ab, b->cb, c-> cd, d-> ad (see A105500 or A246960).


Cf. A296148, A343990, A343991.

Sequence in context: A135028 A325006 A325014 * A275689 A322015 A285311

Adjacent sequences:  A343989 A343990 A343991 * A343993 A343994 A343995




N. J. A. Sloane, May 06 2021


Renamed and rewritten by Michel Dekking, Jun 03 2021



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 12:01 EDT 2022. Contains 354033 sequences. (Running on oeis4.)