 # 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. :)