Prime Factor Diagrams

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

This is what 700 looks like:


By the location of the points it is easy to see that all of them here are 7 * 5 * 5 * 2 * 2.
')
The following is a description of how this works.

For a start, 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 number) and an image, and then arranges n copies of the image symmetrically.

 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 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

which is not so beautiful and clear.

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

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


Further, having a list of prime factors, we recursively create the entire image.
If the list is empty, it 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 remaining ps, we recursively create an image from the remaining prime numbers ps and draw p copies of this image using the primeLayout function.

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

Finally, in order to turn a number into a factorization diagram, we decompose it into prime factors, normalize them into a list of prime numbers, turn it over so that large 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 works well only with numbers from the range {2, 3, 5, 7} (and possibly 11). For example, 121 looks like this:


And so 611:


Here are diagrams of all integers from 1 to 36:


The degrees of the triples are especially interesting, since their diagrams are Sierpinski triangles . For example, 3 ⁵ = 243:


The powers of two are also quite good; they are fractals called Cantor dust . Here are 2 ¹⁰ = 1024:


And finally 104:


Posted by: Brent Yorgey. Original

PS: There is no particular practical use (except to demonstrate the expansion of a number into prime factors), but it looks funny. :)
At the end of the original article, the author says that he would like to arrange the application in the form of a site so that anyone can enter their number and see the result.
I did something similar in javascript, anyone can experiment here . Performance is lower than the haskell version, so be careful with large numbers.
PPS: Post from the sandbox, so I apologize in advance that I did not arrange the translation properly.

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 3628800 decomposition looks like? That way. :)