## Factorization diagrams

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700:

It’s easy to see (I hope), just by looking at the arrangement of dots, that there are $7 \times 5 \times 5 \times 2 \times 2$ in total.

Here’s how I did it. First, a few imports: a function to do factorization of integers, and a library to draw pictures (yes, this is the library I wrote myself; I promise to write more about it soon!).

> module Factorization where
>
> import Math.NumberTheory.Primes.Factorisation (factorise)
>
> import Diagrams.Prelude
> import Diagrams.Backend.Cairo.CmdLine
>
> type Picture = Diagram Cairo R2


The primeLayout function takes an integer n (assumed to be a prime number) and some sort of picture, and symmetrically arranges n copies of the picture.

> primeLayout :: Integer -> Picture -> Picture


There is a special case for 2: if the picture is wider than tall, then we put the two copies one above the other; otherwise, we put them next to each other. In both cases we also add some space in between the copies (equal to half the height or width, respectively).

> primeLayout 2 d
>   | width d > height d = d === strutY (height d / 2) === d
>   | otherwise          = d ||| strutX (width d / 2)  ||| d


This means when there are multiple factors of two and we call primeLayout repeatedly, we end up with things like

If we always put the two copies (say) next to each other, we would get

which is much clunkier and harder to understand at a glance.

For other primes, we create a regular polygon of the appropriate size (using some trig I worked out on a napkin, don’t ask me to explain it) and position copies of the picture at the polygon’s vertices.

> primeLayout p d = decoratePath pts (repeat d)
>   where pts = polygon with { polyType   = PolyRegular (fromIntegral p) r
>                            , polyOrient = OrientH
>                            }
>         w = max (width d) (height d)
>         r = w * c / sin (tau / (2 * fromIntegral p))
>         c = 0.75


For example, here’s primeLayout 5 applied to a green square:

Now, given a list of prime factors, we recursively generate an entire picture as follows. First, if the list of prime factors is empty, that represents the number 1, so we just draw a black dot.

> factorDiagram' :: [Integer] -> Diagram Cairo R2
> factorDiagram' []     = circle 1 # fc black


Otherwise, if the first prime is called p and the rest are ps, we recursively generate a picture from the rest of the primes ps, and then lay out p copies of that picture using the primeLayout function.

> factorDiagram' (p:ps) = primeLayout p (factorDiagram' ps) # centerXY


Finally, to turn a number into its factorization diagram, we factorize it, normalize the returned factorization into a list of primes, reverse it so the bigger primes come first, and call factorDiagram'.

> factorDiagram :: Integer -> Diagram Cairo R2
> factorDiagram = factorDiagram'
>               . reverse
>               . concatMap (uncurry \$ flip replicate)
>               . factorise


And voila! Of course, this really only works well for numbers with prime factors drawn from the set $\{2,3,5,7\}$ (and perhaps $11$). For example, here’s 121:

Are there 11 dots in those circles? 13? I can’t really tell at a glance. And here’s 611:

Uhh… well, at least it’s pretty!

Here are the factorization diagrams for all the integers from 1 to 36:

Powers of three are especially fun, since their factorization diagrams are Sierpinski triangles! For example, here’s $3^5 = 243$:

Powers of two are also fun. Here’s $2^{10} = 1024$:

[ETA: as anon points out, this fractal has a name too: Cantor dust!]

One last one: 104.

I wish I knew how to make a website where you could enter a number and have it show you the factorization diagram… maybe eventually.

(In case you were wondering, $611 = 13 \times 47$.)

Assistant Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.
This entry was posted in arithmetic, pictures, primes, programming, recursion and tagged , , . Bookmark the permalink.

### 72 Responses to Factorization diagrams

1. Andrew says:

I know what I’m doing this weekend. This is great!

2. Joseph Nebus says:

Reblogged this on nebusresearch and commented:
The Math Less Traveled over here shows off a lovely way of visualizing the factoring of integers by putting them into patterns inspired by the regular polygons. Some numbers factor into wonderfully obvious patterns; some turn into muddles of dots because integers just work that way. They’re all attractive ways to look at numbers, though.

3. anon says:
• Exactly, I also thought about fractals with the powers of 3.

• kjk says:
• Maxime says:

The Sierpinski fractals are connected; the fractals the program gives aren’t. (They are merely Sierpinski-looking embeddings of the Cantor space). There even exists a homeomorphism of R^2 sending the Cantor dust to them.

• Brent says:

Can you elaborate? What does that homeomorphism do?

4. Magnus says:

Wow, that’s pretty. There should be a big poster version of this in every elementary school classroom.

• Brent says:

Yes, but with more color! =D I haven’t come up with a good (meaningful) way to incorporate color into these diagrams. Somehow I want to assign a color to each prime, sort of like http://sonderbooks.com/blog/?p=843, except in my diagrams each dot represents 1, not a prime factor, so the dots themselves can’t really be colored.

• You could draw one big centered colored circle in the background in primeLayout.

• Brent says:

Good idea!

• Keithpeter says:

Yup, I get my students to make rectangles of various sizes in teams for the numbers 1 to 100, and then they get the idea about factors and numbers that have only two factors.

These patterns give me the prime factor decomposition as well.

5. Matt Gardner Spencer says:

That’s pretty neat. It reminds me a lot of the book “You Can Count on Monsters” which is less automated drawing, and of course, with more monsters. I’m looking forward to reading more about diagrams.

• Brent says:

Yes, I think “You Can Count on Monsters” was one of the influences that prompted me to make these.

6. suevanhattum says:

Lovely!

7. In college, there was a poster with different Pascal Triangles, each of them highlighting the multiples of different prime numbers. The patterns were beautiful. And they are really easy to generate, I created a Logo program for it (I didn’t have Brent’s graphics library 😉 and used it in an algorithms class.

• Brent says:

Oh, very cool idea. I just took a few minutes to hack something up and it’s pretty awesome. Here’s a teaser:

I’ll write a post about it at some point soon.

8. I wonder if you can see the patterns in the first 36 numbers better if you don’t reverse the factors. (I can’t get cairo installed with ghc 7.6.1…)

• Brent says:

Yes, I’ve considered this. I’ll give it a try.

gtk2hs is known not to compile under 7.6.1. Or do you really mean cairo itself? It would probably help if I split the diagrams-cairo package into two: one that depends just on cairo and another (diagrams-gtk) that depends on all of gtk2hs. I plan to do that soon. In the meantime you can also try the diagrams-svg backend.

• I meant gtk2hs indeed. diagrams-svg worked after editing some cabal files and replacing old-time with time. Here are the first 100 numbers with unreversed factors and colored circles: https://dl.dropbox.com/u/205768/factorDiagram.svg (It’s 3.7MB because the circles are serialized as svg paths.)

• Brent says:

Cool! Hehe, yeah, diagrams-svg needs some optimization work…

• shapr says:

My wife pointed out that every prime is a circle on its own, except two. Groups of four are not shown as two circles of two, but instead one group of four. That makes speedy factoring a bit confusing.

• Brent says:

Yes, two is a bit special. I don’t understand the distinction though, what’s the difference between “two circles of two” and “one group of four”? What would the former look like?

• Jan Van lent says:

If you start with two non-overlapping circles and then put two circles in each, they can never be as close together as in the square group of four.
In other words, you cannot draw non-overlapping circles around groups of two in the square group of four.

• shapr says:

Yes, that’s exactly it. For both of us the pattern was broken when four circles were equal spacing from each. Circles around any other groups could not overlap, exactly as Jan van Lent says.
The svg generated from the javascript D3 library does two differently, more like two separate groups.

9. Lucas says:

You may be interested in Lost Lander’s “Wonderful World”. The music video is made out of geometric creatures merging, and the whole thing is based on prime factorization as well. It’s wonderfully animated: http://www.youtube.com/watch?v=TZkQ65WAa2Q

• Brent says:

Amazing!!! Thanks for sharing!

10. Ariel D. Moya Sequeira says:

This is a good way to visualize integer factorization. Great work!

11. As usual, you’ve done something fascinating with your ability to get something abstract into a visual form.

12. I like this a lot. It’s beautiful, simple and obvious once you’ve seen it, not before :-).

13. Rhys Ulerich says:

Any chance you could provide SVGs of some of the images? They’re quite interesting from a design perspective.

• Brent says:

Sure, I could make SVGs, but have other things I need to be working on at the moment. I plan to write a followup post sometime in the next week, I’ll make some SVGs and link to them then.

14. > Powers of three are especially fun, since their factorization diagrams are Sierpinski triangles!
Haha, excellent! I like this choice.

15. Don Stewart says:

Brent, gorgeous use of the diagrams package – and I’m sure you could convince the snap or yesod teams to web-appify the tool

16. mikero says:

Consider having primelayout *rotate* the p copies of the base image around the center of the circle, rather than translating. It would make things more radially symmetric (numbers 10 and 30 would look a lot nicer), but would not change the result for prime powers (for prime powers, rotating and translating would have the same effect due to dihedral symmetry).

• Brent says:

Yes, this is an excellent idea! Someone else already suggested this, though I was worried about the prime powers — but now that I think about it more, you’re absolutely right about the symmetry. I’m already planning a follow-up post sometime next week with improved versions of the diagrams and a collection of related links and such that various people have contributed.

17. One thought that *might* help wrangle larger prime factors is if you nest concentric rings. This idea deviates from the general rule you’ve established, but it might at least help in some cases.

For example 21 wouldn’t be seven triples in a ring, it’d be three concentric rings of seven dots.

Two motivations. 1) To use up some of that empty space in the middle of eg 611. 2) It’s easier to count the number of nestings (presumably linearly along a radius) instead of around the circle. On the other hand, it might be harder to count the number of dots in a ring versus the number of compound structures in a ring.

Awesome stuff!

• Brent says:

Hmm, interesting idea, though one big difficulty I forsee with this is that the layout algorithm is no longer purely a fold over the list of prime factors. I do plan to release some more generic code (as a module for the diagrams-contrib package) which should make it easier for people to play around with ideas like this. In the meantime I’ve also come up with (what I think is) a nice use of color to make it eas(ier) to interpret diagrams for numbers like 611. Stay tuned. =)

18. Paul Murray says:

Try drawing a ring of sub-diagrams by rotate each sub-diagram so they all point “inward” to the centre. Apply this recursively.

19. Kevin Carr says:

This is just absolutely beautiful.

20. Jason Davies says:

Here’s a version written using JavaScript and SVG: http://www.jasondavies.com/factorisation-diagrams/

• Brent says:

Cool, thanks! I’ve been a big fan of your work for a while, so I’m happy you noticed this. =)

21. Jan Van lent says:

Excellent idea.
I was going to make the same suggestion of rotating the pattern as it is being duplicated.
To avoid getting straight line patterns you can deal with 2 as a special case as above or you can rotate the pattern before duplicating.
I prefer the straightforward implementation though.
There is no need to only consider sorted lists of primes.
I implemented something using Maple, exported to eps, cleaned up using Ghostscript and converted to SVG using pstoedit.
Two examples:
https://dl.dropbox.com/u/100280700/23456.svg
https://dl.dropbox.com/u/100280700/65432.svg
The SVG files are big.
Same as png:

It would be good exercise to code this directly in Postscript.
A nice web service could dynamically generate pictures based on a URL with a base 36 filename representing a list of integers.
A complete diagram with for each integer all the patterns for all possible factorisations (including ordering) might be interesting.

The geometry I used might be slightly different than in the original.
I used the idea of bounding circles.
Start of with a pattern contained in a unit circle.
Rescale, translate and then rotate n times so that the n new circles have their centre on the unit circle and are packed tightly. Then rescale the whole thing so that it fits again into a unit circle. Repeat.
The examples use a disk of radius 0.5 as the starting pattern.

• Brent says:

Very nice, thanks for sharing!

22. Pingback: 인수분해 그림과 프랙탈 « Hav fuN with Math

23. Ken says:

I’d like to suggest that 7 be special-cased to hexagonal close packing.

• Struan says:

Actually, I think that 2 and three should be the special cases, with 4 implied from the flip-flop of case 2.

Then all the other n (prime) should be laid out with a central item and (n-1) surrounding items, possibly even enhanced to have multiple rings of surrounding items.
ie.
* when n = (1+3i) and i > 3
have a central item, an inner ring of i items and an outer ring of 2i items
* when n = (1+4i) and i > 3
have a central item, an inner ring of i items and an outer ring of 3i items
* when n = (1+6i) …

I’m sure there’s some better pattern here but I’m not mathematician enough to know it

24. David says:

LOVE IT! This is such a fun post, and those diagrams are so cute, I was also motivated to re-implement this one for myself. I took mikero’s rotation suggestion, but thought I’d add one more little observation. If you sort your prime factors going inward from large to small instead of small to large, the overall result has a slightly different aesthetic. I feel like maybe they’re easier to read on the whole, if I’m actually trying to mentally look at a number and quickly ‘read’ the entire set of prime factors.

David.

25. Pingback: Visto nel Web – 48 « Ok, panico

26. sseefried says:

I have created a page that animates transitions from the factorisation diagram of one number to the factorisation diagram of its successor. Implemented in JavaScript using the Raphaël library

http://seanseefried.com/factor-diagrams/

27. Pingback: Skaitļu maģija 1 « prometejs

28. David Li says:

We’ve implemented this for SymPy Gamma: http://gamma.sympy.org/input/?i=140

This uses D3.js for rendering and SymPy/Python in the backend.

29. s-987618 says:

This is the best idea about integer factorization, written here is to let more people know and participate.
A New Way of the integer factorization
1+2+3+4+……+k=Ny,(k<N/2),"k" and "y" are unknown integer,"N" is known integer.
How do I know "k" and "y"?
"P" is a factor of "N",GCD(k,N)=P.

Two Special Presentation:
N=5287
1+2+3+…k=Ny
Using the dichotomy
1+2+3+…k=Nrm
"r" are parameter(1;1.25;1.5;1.75;2;2.25;2.5;2.75;3;3.25;3.5;3.75)
"m" is Square
(K^2+k)/(2*4)=5287*1.75 k=271.5629(Error)
(K^2+k)/(2*16)=5287*1.75 k=543.6252(Error)
(K^2+k)/(2*64)=5287*1.75 k=1087.7500(Error)
(K^2+k)/(2*256)=5287*1.75 k=2176(OK)
K=2176,y=448
GCD(2176,5287)=17
5287=17*311

N=13717421
1+2+3+…+k=13717421y
K=4689099,y=801450
GCD(4689099,13717421)=3803
13717421=3803*3607

The idea may be a more simple way faster than Fermat's factorization method(x^2-N=y^2)!
True gold fears fire, you can test 1+2+3+…+k=Ny(k<N/2).
More details of the process in my G+ and BLOG.

30. Can I include your diagrams in this collection? I think I will make a separate “chapter” there for factorization diagrams: http://mathfuture.wikispaces.com/SubQuan+and+friends

31. arnulfo says:

Reblogged this on conlatio and commented:
A program to generate “factorization diagrams”.