Factorization Diagrams

Published on October 09, 2012

Factorization Diagrams

Recently, in his spare time, he wrote a program for generating diagrams obtained by decomposing a number into prime factors or “ factorization diagrams”.

This is what 700 looks like:

By the location of the points, it is easy to see that there are 7 * 5 * 5 * 2 * 2 in total.

The following is a description of how this works.

To start, there are several imports: a function for decomposing an integer into prime factors and a library for drawing diagrams.

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 (must be a prime) and some kind of image, and then symmetrically arranges n copies of the image.

primeLayout :: Integer -> Picture -> Picture 

For 2, there is a special case: if the image is wider than the height, then two copies are drawn one above the other, otherwise they are drawn side by side. In both cases, we add a small space 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 that if there are several coefficients equal to two, and we call primeLayout several times, it turns out something like:

If we always painted copies next to each other, we would get

something that is not so beautiful and clear.

For other numbers, we create a regular polygon of the appropriate size and arrange the copies along the vertices of the polygon.

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 is primeLayout 5 applied to the green square:

Next, having a list of prime factors, we recursively create the entire image.
If the list is empty, this corresponds to 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 number is called p and the rest are ps, we recursively create an image from the remaining primes ps and draw p copies of this image using the primeLayout function.

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

And finally, to turn a number into a factorization chart, we decompose it into prime factors, normalize them to a list of primes, flip so that the big numbers are at the beginning and call factorDiagram '.

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

And voila! Of course, this only works well with numbers in the range {2, 3, 5, 7} (and maybe 11). For example, here’s 121:

And 611:

Here are the diagrams of all integers from 1 to 36: The

degrees of the three are especially interesting, since their diagrams are Sierpinski triangles . For example, 3 5 = 243:

Degrees of two are also quite good, they are fractals called Kantor dust . Here is 2 10 = 1024:

And finally 104:

Posted by Brent Yorgey. The original .

PS: There is not much practical use (except to demonstrate the decomposition of the number into prime factors), but it looks funny. :)
At the end of the original article, the author says that he would like to place the application in the form of a website so that anyone can enter their number and see the result.
I did something similar in javascript, those who wish can experiment here . Performance is lower than the haskell version, so it’s more accurate with large numbers.
PPS: Post from the sandbox, so I apologize in advance for not having designed the translation in an appropriate way.

UPD: lany wrote a very interesting article with the creation of a similar chart visualizer, but with higher performance on large numbers. Want to see what the decomposition of 3628800 looks like? That way. :)