Recursive Rosettes

Year: 2014 Authors: Paul Gailiunas

Core claim

The recursion R(n)=R(n-1)R(n-2)R(n-2) produces palindromic geometric paths that can close into many distinct rosettes, depending on turn angles and parameter choices.

Topics

recursive geometry, rosette patterns, palindromic strings, search methods

Domains

recurrence relations, discrete geometry, combinatorics, symmetry, generative art, turtle graphics, pattern design, visual complexity

Methods

recursion analysis, induction proof, parameter search, LOGO implementation

Media

LOGO, spreadsheet, turtle geometry, geometric diagrams

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Proceedings of Bridges 2014: Mathematics, Music, Art, Architecture, Culture

Recursive Rosettes

Paul Gailiunas

25 Hedley Terrace, Gosforth

Newcastle, NE3 1DP, England

email: paulgailiunas@yahoo.co.uk

Abstract

Recursively generated geometric structures are usually something like a fractal: generally in the limit they will be true fractals. At least one recursive function, which is actually very simple, can generate a wide range of nonfractal cyclical structures with various visual characters. There are infinitely many such rosette structures, and it is by no means certain that they have all been identified. (“Rosette” is used here in the general sense of a circular rose-like pattern, rather than referring to classical rosette curves, which are related to epicycloids.) After an analysis of the mathematical structure of the recursive function, methods of searching for the rosettes that it generates are discussed.

A Simple Recursive Function

Probably the best-known recursive function is the one that generates the Fibonacci numbers:

F (n) = F (n - 1) + F (n - 2),

but such functions need not relate to numbers only. For example the terms could indicate geometric operations (here indicated by a script font), just as algebraic expressions in group theory might refer to symmetry operations. Here the starting terms, $R (1)$ and $R (2)$ , will denote elementary operations in turtle geometry [1]: forward a step, turn an angle, and the recursion formula will concatenate these operations.

The formula $R (n) = R (n - 1)$ $R (n - 2)$ $R (n - 2)$ is just as simple as that which defines the Fibonacci numbers, and it is almost as rich in its outcomes. If $R (1)$ is a forward step then a $6 0^{\circ}$ right turn, and $R (2)$ is a forward step then a $6 0^{\circ}$ left turn, a fractal-like path is produced having a similar appearance to the Koch snowflake curve (figure 1). Notice that it is symmetrical about its mid-point, and the first and last segments are parallel; if $n$ is even, as in figure 1, they are collinear: properties which would not be immediately predictable from the recursion formula.

Figure 1: A simple application of the recursion formula $R (n) = R (n - 1)$ $R (n - 2)$ $R (n - 2)$ .

The algorithm can be easily implemented using LOGO [2]:

Gailiunas

to a	to b	to R :n	to rose :n :stepa :x :stepb :y
fd :stepa	fd :stepb	if :n = 1 [a stop]	cs
rt 360/:x	lt 360/:y	if :n = 2 [b stop]	R :n
end	end	R :n - 1 R :n - 2 R :n - 2	end
		end

Some insight into the geometric behaviour of this function can be gained simply by counting the terms, treating the formula in the usual way as a numerical relationship but keeping $R (1) = a$ and $R (2) = b$ separate, so that $a (n)$ counts the number of occurrences of right turns, $b (n)$ counts the number of occurrences of left turns, $a (1) = 1$ , $b (1) = 0$ , $a (2) = 0$ , $b (2) = 1$ . Of course the total number of terms, $R (n) = a (n) + b (n)$ .

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
a	1	0	2	2	6	10	22	42	86	170	342	682	1366	2730	5462	10922
b	0	1	1	3	5	11	21	43	85	171	341	683	1365	2731	5461	10923
R	1	1	3	5	11	21	43	85	171	341	683	1365	2731	5461	10923	21845

Table 1: The number of terms of each type at each level of recursion.

The table shows that $b (n) = R (n - 1)$ and $a (n + 1) = 2 \times b (n)$ , so that the number of terms approximately doubles at each iteration, and $b (n) = a (n) - (- 1)^{n}$ . There are standard ways to analyse numerical recursion relationships like these to derive explicit formulae. Suppose that a solution is of the form $R (n) = p r^{n}$ then:

p r^{n} = p r^{n - 1} + 2 p r^{n - 2}

r^{2} = r + 2

r^{2} - r - 2 = 0

r = 2 or - 1

R (n) = p 2^{n} + q (- 1)^{n}

R (1) = 1

a (1) = 1

b (1) = 0

R (2) = 1

a (2) = 0

b (2) = 1

2 p - q = 1

2 p - q = 0

4 p + q = 1

4 p + q = 0

4 p + q = 1

p = 1/3, q = - 1/3

p = 1/6, q = - 2/3

p = 1/6, q = 1/3

R (n) = \frac{2 ^{n} - ( - 1 ) ^{n}}{3}

a (n) = \frac{2 ^{n} - 4 ( - 1 ) ^{n}}{6}

b (n) = \frac{2 ^{n} + 2 ( - 1 ) ^{n}}{6}

Recursive Rosettes

A little experimentation reveals that concatenating strings of $a$ and $b$ according to the recursion relationship produces a palindrome with either an extra $b$ ( $n$ even) or $aa$ ( $n$ odd) at the end, corresponding with the $(- 1)^{n}$ term:

a b baa baabb baabbbaabaa baabbbaabaabaabbbaabb baabbbaabaabaabbbaabbbaabbbaabaabaabbbaabaa

A proof by induction shows how this happens: if is the empty string, the first term doubled can be written as aa, and the second term as b. The third term is then b aa. The second term doubled is bb, so the fourth term is baabb. Noting that the empty string is trivially a palindrome, and assuming that double the $(n - 2)^{th}$ term ( $n$ odd) is aa, and the $(n - 1)^{th}$ term is b, then the $n^{th}$ term is baa, which is a palindrome followed by aa. The $(n - 1)^{th}$ term doubled is bb, the same as the $n^{th}$ term with aa replaced by b, and the $(n + 1)^{th}$ term is another palindrome followed by b: baabb.

Different Angles

Writing the angle turned in $R (1)$ as A and that in $R (2)$ as B, if $A \neq = B$ the path will not finish with a segment collinear with the starting segment, and the result is, in general, a confused mess. Suppose, however, that the final segment is parallel to the first although drawn in the opposite direction. Now suppose that the iteration is continued to the next stage. The same path will be drawn almost twice, once in reverse since the concatenated operations are palindromic apart from an additional $b$ or $a a$ term. Since the path is (almost) symmetrical the reversal makes no difference, but the extra terms cause a change in direction. Apart from a few special cases, if the change in direction is a rational part of a complete turn there will be some stage when the path will close, and further iterations will just retrace the path already followed, generating a rosette. Exceptions occur when the effect of the repeated change in direction at some depth of recursion is equivalent to a whole number of turns, resulting in a net translation, rather than a rotation. The resulting path can be considered to be a rosette with infinite radius, just as a straight line can be seen as the limit as a circle increases in radius (figure 2, the numbers will be explained later).

Figure 2: A section of a rosette with infinite radius.

16/7 8

Gailiunas

After recursion to depth, $n$ , there have been $a (n)$ turns in one direction and $b (n)$ in the other, so the total angle turned is $a (n) A - b (n) B$ . The path will close (at some depth of recursion $> n$ ) whenever $a (n) A - b (n) B$ is $18 0^{\circ}$ , more conveniently expressed as $\frac{1}{2}$ turn, or some odd multiple, $m$ , of $\frac{1}{2}$ turn. Since there are several parameters in this relationship there is a large solution space, but solutions with large $n$ or small A or B will generally be drawn too densely to be very interesting visually, narrowing the search.

Low Depth of Recursion

One simple strategy to find interesting rosettes restricts the search to low depths of recursion and angles that are exact divisions of a complete turn. It will be convenient to put $A = 1/ x$ turn and $B = 1/ y$ turn. The condition for a closed path is then:

\frac{1}{x} a (n) - \frac{1}{y} b (n) = \frac{m}{2} \frac{2}{x} a (n) - \frac{2}{y} b (n) = m 2 a (n) - 2 b (n) \frac{x}{y} = m x

The lowest reasonable value of $n = 4$ so the condition becomes $4 - 6 x / y = m x$ . Restricting the solutions to positive values (actually not necessary) the divisors of 6 (hence possible integer values of $y$ ) are 2, 3, 6. Discounting the solution $x = 1$ (a full turn) this leaves $4 - 6 \times 1/3 = 2$ and $4 - 6 \times 1/6 = 3$ . Noting that the fractions need not be in lowest terms, the solutions are $x = 2$ , $y = 6$ and $x = 3$ , $y = 18$ (figure 3).

3 18 Figure 3: Rosettes (with $x, y$ integers) corresponding to the lowest feasible depth of recursion.

The alternative condition is $4 - 6 y / x = m y$ . Possible divisors of 4 are 2, 4, giving the solutions $x = 8$ , $y = 4$ ; $x = 20$ , $y = 5$ ; $x = 4$ , $y = 3$ (figure 4).

Recursive Rosettes

20 5

4 3

Figure 4: The alternative simple solutions from the lowest feasible level of recursion. Figure 5: A selection of rosettes with integral $x$ and $y$ from recursion level $n = 5$ .

Gailiunas

Even though this approach is limited to integer values of $x$ and $y$ it rapidly gets out of hand. The next level of recursion, $n = 5$ , produces 17 different possibilities. Figure 5 shows some of them.

Some Simple Rosettes

It is not always the case that a low value of $n$ will produce only simple rosettes as can be seen from figure 5, and not all simple rosettes have angles that are exact divisions of a whole turn. It is perhaps not surprising that there is a simple rosette with $A = 1/5$ and $B = 3/10$ (the internal angle of a pentagon), which is another solution of the case first considered ( $n = 4$ ).

Another very simple rosette has $x = 3$ and $y = 6$ . It is a solution in the $n = 6$ series with $m = 3$ :

10/3 10

20-22×(3/6)=9=3×3 5 10/3

24 12

3 6

9 6 Figure 7: Some very ornate examples.

Figure 6: Some simple rosettes. 9 18/7

Recursive Rosettes

More Elaborate Rosettes

Figure 7 shows further possibilities. The left hand example comes from the set of solutions in the $n = 8$ series ( $m = 5$ ), but that on the right was discovered in a completely different way. Noting that the (5, 10/3) example, in figure 6, has angles that are supplementary ( $7 2^{\circ}$ and $10 8^{\circ}$ ) further such solutions were sought, essentially by trial and error, using a spreadsheet to carry out the calculations. The next value of $x$ (which is 9) that produces such a solution has $n = 9$ and $m = 47$ , generating the rosette illustrated.

Calculating More Solutions

Probably the most obvious way to find further solutions is by straightforward algebraic manipulation of the basic condition to include in a spreadsheet:

\frac{a}{x} - \frac{b}{y} = \frac{m}{2} \frac{b}{y} = \frac{a}{x} - \frac{m}{2} = \frac{2 a - m x}{2 x} \frac{y}{b} = \frac{2 x}{2 a - m x} y = \frac{2 b x}{2 a - m x}

\frac{a}{x} - \frac{b}{y} = \frac{m}{2} \frac{a}{x} = \frac{b}{y} - \frac{m}{2} = \frac{2 b - m y}{2 y} \frac{x}{a} = \frac{2 y}{2 b - m y} x = \frac{2 a y}{2 b - m y}

Tabulate integer values of $x$ for various values of $n$ and $m$ to determine candidate fractional values of $y$ . Similarly tabulate integer values of $y$ to find fractional values of $x$ . Negative values of $m$ will also work.

Typically a rosette will be completed at a recursive depth of about 12, but often some parts of the path that is generated by recursion are retraced before the rosette finally closes, and values of about 16 are not unusual in such examples. As a consequence the angles must be specified with considerable accuracy otherwise the accumulated errors become significant by the time the path closes, and the spreadsheet should be programmed to output values as fractions (in lowest form) rather than decimal approximations. Apart from anything else, fractions with small numerators, which are more likely to produce interesting rosettes, are more easily identified.

If fractional values of both $x$ and $y$ are considered the search space becomes even larger, but by starting with known examples that are not too visually dense the chances of finding further visually interesting rosettes are increased: if $a / x - b / y = m /2$ then multiplying by any odd number will give another solution, so $x / q$ , $y / q$ ( $q$ odd) are feasible candidates. It could be possible to simplify the fraction if $q$ divides either $x$ or $y$ . If either $x$ or $y$ is a fraction it is possible that $x / q$ or $y / q < 1$ , and in this case, because these are fractions of a turn, it is possible to simplify to the reciprocal of $q / x - 1$ or $q / y - 1$ , for example $x = 8$ , $y = 20/9$ produces an interesting rosette; another is produced by $x = 8/3$ , $y = 20/27 \equiv 20/7$ .

Gailiunas

8 20/9 Figure 8: One rosette solution can be derived from another.

8/3 20/7

What Affects the Appearance of a Rosette?

Generally it is not obvious which calculated solutions will be interesting, and most generate a path that is visually too dense. Examples like that in figure 8 with $m = 47$ and a non-integral $y$ ( $= 18/7$ ) would not seem immediately very promising, and are not easily found by a simple trial and error search among the multitude of possibilities. The values of the parameters $x, y, n$ , and $m$ provide some clues about how the rosette will appear.

The symmetry of the rosette is related to the numerators of $x$ or $y$ , as the examples show, but not in a simple way. For example the two in figure 2 are as might be expected, with orders of symmetry equal to the 6 and 18 respectively, but 8 20 (figure 5) and 24 12 (figure 6) have lower orders than might be expected, and 8 4 (figure 4) is possibly even more surprising. As already indicated if either of the numerators is large it is likely that the rosette will be visually dense, but this is not an invariable rule.

If $n$ is large the segment of path that repeats around the rosette is more complex, and few rosettes with $n > 7$ are very pleasing. That in figure 8, with $n = 9$ , is very unusual. The same figure also shows the effect of a high value of $m$ : the path has many loops, although the looping is not always so obvious.

Given the very large search space, even with these insights, finding new visually interesting rosettes is a tedious exercise, but one which can be rewarded by some unexpected discoveries. It is not difficult to show that any recursion of the form $R (n) = (R (n - 1))^{t} (R (n - 2))^{t - 1}$ will generate palindromic strings, so the search space is actually even larger, although most examples with $t > 1$ are generally too complex to have much visual appeal.

References

[1] Abelson H. and diSessa A., Turtle Geometry, MIT, 1980. [2] Harvey B., Computer Science Logo Style, MIT, 1986.

Jusur / Bridges Research Atlas

Explorer

Recursive Rosettes

Recursive Rosettes

Core claim

Topics

Domains

Methods

Media

Paper text

Recursive Rosettes

Abstract

A Simple Recursive Function

Different Angles

16/7 8

Low Depth of Recursion

Some Simple Rosettes

More Elaborate Rosettes

Calculating More Solutions

What Affects the Appearance of a Rosette?

References