Round and Transform

When you round numbers, interesting things can happen.  For example, consider the fraction 6/11, 0.54545454…  When rounded to the nearest whole number, it rounds up to 1.  But when rounded to the nearest tenth, it rounds down to 0.5.  Nearest hundredth?  Up.  Nearest thousandth?  Down.  And so on.  Of course, numbers can be rounded in other ways.  Say, for example, 1/3, 0.33333…  It rounds down to the nearest whole number (0), up to the nearest half (0.5), down to the nearest quarter (0.25), up to the nearest eighth (0.375), etc.

The program Ultra Fractal, which I use for almost all of my fractal work, uses complex numbers and has a rounding function.  It rounds each part of the complex number (real and imaginary) to the nearest integer (positive, negative, or zero).  This can be used to round to any other number (say, nearest 2, nearest 0.5, or nearest π) by:

1. Decide on a rounding base.  For example, 1 for the nearest integer, 0.5 for the nearest half, or 3.14159... for the nearest π.
2. Multiply the number to be rounded by the rounding base.
3. Find the nearest complex integer for the scaled number found in step 2.
4. Divide the integer in step 3 by the rounding base.

To keep things interesting, I multiply the rounding base by a number each time.  For example, if I started with 1 and multiplied the base by 10 each iteration, then that would have the effect of rounding the number to the nearest 1, then to the nearest 10, then to the nearest 100, etc.  Also, I transform the rounded number in some fashion (say, rotate it and translate it) so that there’s something new to round in the next iteration.

Given all this goodness, there are lots of ways to create an image.  If the rounded number is different from the unrounded number, then there’s a rounding error at each iteration.  These can be accumulated and the image drawn according to some aspect of that total.  Larger rounding bases will generally have larger rounding errors (rounding 47 to the nearest 100 will have an error of 5, but rounding to the nearest 100 will have an error of -47), so the errors can be scaled by the rounding base before adding up.  You could just keep track of the direction of the rounding, say by adding 1 to a total if the number were rounded up and subtracting 1 if the number were rounded down.  Or, just color by the final rounded and transformed number, irrespective of what happened along the way.

The image at the top of the page begins with a rounding base of 0.0000152587890625 (2^-16) and doubles the base every iteration.  After rounding, the complex number is rotated by 31 degrees (not 30 or 32—31 is just right).

In the image above, the same rounding parameters are used, but this image is colored according to the relative rounding error (the image at the top uses the adding/subtracting 1 method).  And for this image, the complex number was rotated by 1 radian (about 57.3 degrees) each iteration.

This final example (above) uses the scaled increments and transforms the rounded number using the Mandelbrot set formula (z = z² + c).  This gives rise to the appearance of low-iteration Mandelbrot set fractal structures.

Fun with Modular Multiplicative Inverses

A regular multiplicative inverse (or just “inverse”) is the reciprocal of a number—the inverse of 2 is 1/2 and the inverse of 1/2 is 2.  The key property is that a number times its inverse equals 1.

Modular multiplicative inverses involve modular arithmetic, which involves the remainders of (typically whole) numbers when divided by a given base.  For example, 15 divided by 7 leaves a remainder of 1, so 15 = 1 modulo 7.  The phrase “modulo 7” means the remainder when divided by 7, and is often abbreviated “mod 7.”  Likewise, 22 = 6 mod 8 (remainder of 6 when 22 is divided by 8) and 143 = 3 mod 10 (remainder of 3 when 143 is divided by 10).

So modular multiplicative inverses combine the ideas of two numbers multiplying to 1 with the notion of the remainder, or mod.  The modular multiplicative inverse of a number is (the smallest) number such that the product of the two is 1, modulo some base.  For example, 3 x 5 = 15 and 15 = 1 mod 7.  So 3 and 5 are modular multiplicative inverses, for the base of 7.  For the base of 7, here are the modular multiplicative inverses:

Number	Inverse	Notes
0	none	Anything × 0 is 0, so the product will never have a remainder of 1.
1	1	1 × 1 = 1, for any base.
2	4	2 × 4 = 8, or 1 × 7 with a remainder of 1.
3	5	3 × 5 = 15, or 2 × 7 with a remainder of 1.
4	2	4 and 2 are inverses for base 7.
5	3	5 and 3 are inverses for base 7.
6	6	6 × 6 = 36, or 5 × 7 with a remainder of 1.
7	none	Anything × 7 will be a multiple of 7 and will have a remainder of 0.

The inverses depend on the base and some numbers will not have an inverse.  For example, with base 8:

Number	Inverse	Notes
0	none	Anything × 0 is 0, so the product will never have a remainder of 1.
1	1	1 × 1 = 1, for any base.
2	none	Anything × 2 will be even and will never have a remainder of 1.
3	3	3 × 3 = 9, or 1 × 8 with a remainder of 1.
4	none	Same as for 2.
5	5	5 × 5 = 25, or 3 × 8 with a remainder of 1.
6	none	Same as for 2.
7	7	7 × 7 = 48, or 6 × 8 with a remainder of 1.
8	none	Anything × 8 will be a multiple of 8 and will have a remainder of 0.

So what has this to do with the image?  Here are graphical representations of the modular multiplicative inverses for bases from 2 to 8.  In each image, the number and its inverse are plotted as squares in the (x, y) plane, where x is the number and y is its inverse.

  

The next image combines the previous seven by using the differences in colors of the corresponding pixels.  Black minus black is black, white minus white is black, and black minus white or white minus black is white.

Now, that image is combined with the one for mod 7, yielding this:

   

Finally, the one at the top of the page is a similar one, only using modulo bases 11 and 13.

Ratios of Subsequent Terms in Generalized Fibonacci Sequences

The Fibonacci sequence begins 0, 1, 1, 2, 3, 5, 8, etc.  Each subsequent term is the sum of the previous two.  As the terms get larger and larger, the ratio of two subsequent terms approaches a limit, the golden ratio or Φ, (1 + sqrt(5))/2, or about 1.6180339.  To see this, assume that each term is r times the previous term:  F_n+1 = r F_n, and F_n = r F_n-1.  Then, the Fibonacci recurrence equation

F_n+1 = F_n + F_n-1

becomes

r² F_n-1 = r F_n-1 + F_n-1, or
r² = r + 1.

The last equation is easily solved by the quadratic formula to give r = Φ.

This process can be extended to variations on the Fibonacci sequence by letting the new term be a weighted sum of the previous two terms:

F_n+1 = a F_n + b F_n-1

for some numbers a and b.  Then, by the same analysis, the ratio of subsequent terms will approach a limit r, r = (a + sqrt(a² + 4b))/2.  Here are some values of the ratio r for various a's and b's:

a	b	r
1	1	1.618
2	1	2.414
3	1	3.303
1	2	2
2	2	2.732
3	2	3.562
1	3	3
2	3	2.303
3	3	3.791

This table can be extended indefinitely.  Then, sort it by increasing values of r (when there is a tie, sort by increasing values of sqrt(a² + b²)).  This generates two sequences, A, the sequence of the a values, and B, the sequence of the b values.  The A sequence begins:

1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 3, 1, 2, 1, 3, 2, 1, 3, 2, 1, 3, 2, 1, 1, 2, 3, 4, 1, 2, 3, 1, 4, 2, 1, 3, 2, 4, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 5, 3, 1, 4, 2, 1, 3, 5, 2, 4, 1, 3, 2, 5, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 1, 2, 3, 4, …

and the B sequence begins:

1, 2, 3, 1, 4, 2, 5, 3, 6, 7, 4, 1, 8, 5, 9, 2, 6, 10, 3, 7, 11, 4, 8, 12, 13, 9, 5, 1, 14, 10, 6, 15, 2, 11, 16, 7, 12, 3, 17, 8, 13, 18, 4, 9, 14, 19, 5, 10, 15, 20, 21, 16, 11, 6, 1, 22, 17, 12, 7, 23, 18, 2, 13, 24, 8, 19, 25, 14, 3, 20, 9, 26, 15, 21, 4, 27, 10, 16, 22, 28, 5, 11, 17, 23, 29, 6, 12, 18, 24, 30, 31, 25, 19, 13, 7, 1, 32, 26, 20, 14, …

These sequences count each other--the terms in B count up how many times each number in A has shown up.  The first three terms of A are 1 and the first three terms of B count up the number of 1s in A.  Then, the fourth term of B is 1, indicating that the 2 that is the fourth term in A is the first time that a 2 shows up in A.  The fifth term of A is 1, which is the fourth 1 in A, and the fifth term of B is 4, to reflect that.  Likewise, the terms in A count up how many times each number is B has occurred.

All this relates to the image at the top of the page by considering the terms in A and B to be coordinates in the (x, y) plane and drawing segments from one point to the next.  The line begins in one corner, at point (1,1), then continues to (1,2), (1,3), (2,1), etc.  The image at the top has been rotated and flipped for aesthetic considerations; here is a blowup of the beginning of the curve oriented normally so you can follow it from point to point.

This post has been concerned with the principal solution of the quadratic equation, r = (a + sqrt(a² + 4b))/2.  But there is a second solution, r = (a - sqrt(a² + 4b))/2.  Here is the image corresponding to those values of r.