Skip to content

Prime Factorizations Are Fractals (sort of)

Posted in Life

For more on this project, click here.

My Weird Hobby

A good hobby needs to be something you could do forever. But things tend to get boring after a while. So a good hobby needs to be something you could do forever that would stay interesting.

Hunting for patterns in the prime numbers fits the bill perfectly. What you want probably doesn’t exist (at least, not in the way you want it), so your search will likely never end. And yet! Little hints of pattern are always turning up, so it keeps things interesting along the way.

The “hint of pattern” that I’m particularly interested in at the moment has to do with prime factorizations. Granted, prime factorizations are most relevant to non-prime numbers (“composite numbers”), so trying to find a pattern in the primes by looking at the non-primes is a bit indirect.

However, since every integer (every “whole number”) either is prime or isn’t, if you could find a pattern in the ones that aren’t, you’d just need to invert that pattern to find the ones that are.

Even more importantly, the non-primes are “made out of primes.” Well, at least all integers larger than 1 are. Each can be broken down — “factorized” — into a unique combination of prime numbers. So, if you’re looking for a pattern in the non-prime numbers, what you’re really looking for is a pattern in their prime factorizations. That is, you’re not looking for a pattern in the primes themselves, but you are looking for a pattern in the way that primes can be combined to make non-prime numbers.

Is There a Pattern?

Here’s the sequence of numbers we want to find a pattern in:

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28, 30, . . .

Unfortunately, “Count by 2s, but then by 1s randomly” isn’t really what we want.

However, if we write out the prime factorizations, we get this:

22, 21 x 31, 23, 32, 21 x 51, 22 x 31, 21 x 71, 31 x 51, 24, 21 x 32, . . .

That has a lot more repetition in it. And where there’s repetition, you might hope to find a pattern.

To actually see the pattern, though, we need to write things out in a table. And, perhaps ironically, it will help to add the primes back into our sequence. What we’ll do is list the positive integers along the top, and the primes along the side:

Ints:12345678910111213
Primes:2
3
5
7
11
13

Then, we need to fill in how many of each prime are in the prime factorization of each integer.

Ints:12345678910111213
Primes:20102010301020
30010010020010
50000100001000
70000001000000
110000000000100
130000000000001

How to Read Those Tables

Using this kind of table, you can read off the prime factorization for any positive integer. All you do is find the number along the top, and check the numbers in the column below. Each number in that column tells you how many of the corresponding prime number to include in the prime factorization you’re building.

For example, if I want the prime factorization of 10, I find “10” in the top row, then scan down the column below it. The first number below “10” is “1,” and that “1” is in the “2” row. So, that tells us that the prime factorization of 10 contains one 2, or 21.

There’s also a “1” in the 10 column in the row for the prime number “5.” So, that tells us that the prime factorization will also contain one 5, or 51.

All the other numbers in the column below 10 are 0s, so that tells us that none of the other primes will show up in the prime factorization for 10. In other words, 10’s prime factorization will just be 21 x 51.

The Missing Primes

But I think it’s helpful to think of all the missing prime numbers as still being there. So, if I had my druthers, we’d list 2, 3, 5, 7, 11, 13, etc. in every prime factorization.

I know. That would create a problem. If we multiply a number by 7 or 13, it will become seven or thirteen times larger. And if we include every prime number in a factorization, we’d be multiplying it by an infinite number of primes. But that would make every integer infinitely large. Instead of counting, “0, 1, 2, 3, 4, 5, . . .” you’d have to count “0, 1, infinity, infinity, infinity, . . .” And that’s not how numbers work.

The solution to this conundrum is to remember that the numbers in each column in the table above give us the exponents for the primes. Most of those numbers are 0, so what I’m saying is that most of the primes in each prime factorization should should have an exponent of 0. For example, 10 would be 21 x 30 x 51 x 70 x 110 x 130 x . . . . If you multiply those all together, you would still get only 10.

The Magic of 0

The reason this works is that any number with an exponent of 0 is equal to 1. For example, 20 = 1. Also, 52670 = 1. Even 00 = 1. So, if you multiply a number by some other number to the 0th power, you’re just multiplying by 1. And multiplying a number by 1 doesn’t change it.

To get 1, we’ll set all the primes’ exponents to 0 and multiply them together. To get 2, we’ll set all the primes’ exponents to 0 except 2, whose exponent we’ll set to 1. To get 3, we’ll set all the primes’ exponents to 0 except 3, whose exponent we’ll set to 1. To get 4, we’ll set all the primes’ exponents to 0 except 2, whose exponent we’ll set to 2. Etc.

To recap: we can think of all the primes as strategically working together to produce the integer sequence from 1 to infinity by setting their exponents to the appropriate values at the right time. Only if each prime’s exponent shifts from 0 to 1, 1 to 0, 0 to 2, etc. at the right times, like instruments playing a symphony, will we get our lovely positive integer sequence.

Finally Fractals

Now, what does this have to do with fractals?

The sequence of 0s, 1s, 2s, etc. that each prime’s exponent will “play” is a fractal. We usually think of fractals as shapes, but a sequence of numbers can also be a fractal insofar as it can contain infinite copies of itself.

For example, here is the sequence of exponents for the prime number 2:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, . . .

And here’s the sequence of exponents for the prime number 3:

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, . . .

And here’s the sequence of exponents for the prime number 5:

0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, . . .

In general, the exponent sequence for a given prime number can be constructed by the following algorithm:

  1. Start with a sequence that consists of a single 0.
  2. Duplicate the sequence you have so far, till you have p copies of the sequence (where p is whatever your prime number is).
  3. Append the copies end-to-end. That is your new sequence.
  4. Add 1 to the final number in the sequence.
  5. Go to step 2 and repeat.

Example Constructions

For the prime number 2, for example, we start with a single 0:

0

Then duplicate it till we have 2 copies of the sequence so far:

0, 0

Then add 1 to the final number in the sequence:

0, 1

Then duplicate that till we have two copies of the sequence:

0, 1, 0, 1

Then add 1 to the final number:

0, 1, 0, 2

Then duplicate that:

0, 1, 0, 2, 0, 1, 0, 2

And add 1:

0, 1, 0, 2, 0, 1, 0, 3

Etc.

To get the exponent sequence for the prime number 3, we again start with 0:

0

Then duplicate it till we have 3 copies:

0, 0, 0

Then add 1 to the final number:

0, 0, 1

Then duplicate it till we have three copies:

0, 0, 1, 0, 0, 1, 0, 0, 1

Then add 1 to the final number:

0, 0, 1, 0, 0, 1, 0, 0, 2

Then duplicate it till we have three copies:

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2

Then add 1 to the final number:

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3

To get the exponent sequence for the prime number 5, we’d do the same thing again, but this time creating five copies of the sequence each time. And so on.

Proof that Those Are Fractals

To see that each of these is a fractal, what you have to do is show that each contains an infinite number of copies of itself. And to do that, all you have to do is follow the following steps:

  1. Get the full sequence for a given number p
  2. Go to the first number in that sequence
  3. Delete p2 numbers from the sequence
  4. Skip the next p numbers
  5. Go to step 3.

Here’s an example using the sequence of exponents from the prime number 2. We’ll delete 22 numbers, skip 2, delete the next 22 numbers, skip 2, etc. Then we’ll see what sequence we end up with (hint: it will be identical to the one we started with).

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, . . .

Delete the first 22 (i.e., four) numbers, skip the next 2, delete the next 22, etc.

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, . . .

That leaves us with:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, . . .

And compare that to the original sequence:

0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, . . .

Because the starting sequence is infinitely long, the resulting sequence will still be infinitely long even after deleting all those numbers from it. And that resulting sequence will be identical to the starting sequence.

This shows that the sequence contains itself. And if you do the same thing on the resulting sequence, you’ll see that the resulting sequence still contains itself.

Another Example

We can do the same thing with the other prime numbers’ sequences as well. Here’s the sequence for 3:

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, . . .

So, we’ll delete 32 (i.e., nine) numbers, skip 3, delete 32 more, skip 3, etc.

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 3, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 4, . . .

That leaves us with:

0, 0, 1, 0, 0, 1, 0, 0, 2, 0, 0, 1, 0, 0, 1, 0, 0, 2, . . .

And that, you will note, is identical to the sequence we started with. So, the sequence contains itself.

Summary

In other words, the series of positive integers (1, 2, 3, 4, etc.) is produced by the series of prime factorizations, and the exponents of each prime (the number of copies of that prime) in each factorization is determined by an infinite number of fractal sequences.

For more on these sequences, see the On-line Encyclopedia of Integer Sequences. They are called the “p-adic valuations of n”:

  1. The 2-adic sequence
  2. The 3-adic sequence
  3. The 5-adic sequence

And if you still don’t believe me that these sequences are fractals, I offer visual proof:

A catalogue of the fractals and patterns produced by the 2-adic sequence.

And videos:

And if you want to explore the number line for yourself, the app is now available for all to use for free here:

https://micahtillman.com/numberlineapp/