# drawing patterns based on prime factorization

can someone help me generate code to type the diagram for any given natural number based on its prime factorization such as these diagrams

consider the next number 36 and its prime factorization, $36=3^2\cdot 2^2$, writing the primes in descending order... then, start with the pattern for a 3, which is 3 circles 120 degrees apart, now, replace each circle with 3 more circles in the same pattern to account for the $3^2$, this part would look like the pattern for 9 which is also $3^2$. now.. to finish the pattern for 36, we take the pattern for 9 and in each circle replace it with the pattern for 4... that is each of the 9 circles gets replaced with 4 tinier circles arranged in the same pattern as the pattern for 4

• I can help. What am I looking at ? Can you make it a proper question? I don't even know what to draw and why Commented Oct 4, 2015 at 19:55
• Welcome to TeX.SX! This is probably relevant: How to automatically draw tree diagram of prime factorization with LaTeX? Commented Oct 4, 2015 at 20:00
• The algorithm is described here mathlesstraveled.com/2012/10/05/factorization-diagrams Commented Oct 4, 2015 at 20:42
• Also, a JavaScript implementation (not mine), which can be a starting point for a luatex or tikz implementation, here: jsfiddle.net/FEKX2/3 Commented Oct 4, 2015 at 20:47
• I saw this and thought "I must remember that when I teach about factorisation", closely followed by "I hope that someone figures out how to do it so that I can steal^H^H^H^H^Huse their code." Commented Oct 5, 2015 at 19:06

(See update at the end for an alternative output)

Done with Lualatex and tikz, simply converting the code from this javascript fiddle

This is a sample result for number 36:

Which was generated with:

\begin{tikzpicture}[y=-1cm]
\draw[red] (0,0) rectangle (5,5);
\primediagram{36}{2.5}{2.5}{2.5};
\end{tikzpicture}


The macro \primediagram receives four parameters. The first one is the number to represent. The remaining three are the center and radius of the diagram to be generated.

A more interesting example:

Produced by a tikz loop:

\begin{tikzpicture}[y=-1cm]
\foreach \y in {0,...,6} {
\foreach \x in {0,...,4} {
\draw(3.1*\x,3.1*\y) rectangle +(3,3);
\pgfmathtruncatemacro{\number}{\x+5*\y}
\primediagram{\number}{3.1*\x+1.55}{3.1*\y+1.55}{1.3};
\node[black!50, below right] at (3.1*\x, 3.1*\y)  {\number};
}
}
\end{tikzpicture}


# The complete code

To produce these figures, three files are required:

## primediagram.sty

This one simply defines the tex macro which interfaces with the lua code:

% This is primediagram.sty
\directlua{dofile("primediagram.lua")}
\newcommand{\primediagram}[4]{
\directlua{draw(#1,#2,#3,#4)}
}


## primediagram.lua

This one contains the lua code which actually performs the computations and outputs the required \draw commands for tikz. It is a direct translation to lua of the mentioned javascript code.

-- This is primediagram.lua
local smallfirst = false
local off2 = 0

function circle(cx, cy, s)
tex.print(string.format("\\fill (%f, %f) circle(%f);", cx, cy, s))
end

function draw(N, cx, cy, s)
if N==0 then
return
end
if N==1 then
circle(cx,cy,s)
else
local f, r, d, oy, x, y
f = primefactor(N)
if f == 2 then
oy = 0;
if N % 4 == 0 then
f = 4;
r = 2 * s / (f + 2);
d = f * s / (f + 2);
else
f = 2;
r = 0.75 * 2 * s / (2 + 2);
d = 2 * s / (2 + 2);
end
else
r = 2 * s / (f + 2);
d = f * s / (f + 2);
oy = d / 2 * (1 - math.cos(math.pi / f));
end
for i = 0, f do
x = math.sin(math.pi + 2 * math.pi * (i + 0.5) / f + off2);
y = math.cos(math.pi + 2 * math.pi * (i + 0.5) / f + off2);
draw(N / f, cx + x * d, cy - y * d + oy, r);
end
end
end

local primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109,
113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
263, 269, 271}

function primefactor(N)
local ans = N;
for i,pi in pairs(primes) do
if N % pi == 0 then
ans = pi;
if smallfirst then
return ans
end
end
end
return ans
end


# The main document

You only need to include the sty package, as for example:

\documentclass{article}
\usepackage{nopageno}
\usepackage[margin=1cm]{geometry}
\usepackage{tikz}
\usepackage{primediagram}

\begin{document}
\begin{tikzpicture}[y=-1cm]
\foreach \y in {0,...,6} {
\foreach \x in {0,...,4} {
\draw(3.1*\x,3.1*\y) rectangle +(3,3);
\pgfmathtruncatemacro{\number}{\x+5*\y}
\primediagram{\number}{3.1*\x+1.55}{3.1*\y+1.55}{1.3};
\node[black!50, below right] at (3.1*\x, 3.1*\y)  {\number};
}
}
\end{tikzpicture}
\end{document}


Which produces the figure already shown.

# Update: Rotating sub-groups

If each sub-groups is rotated according to the angle at which it is drawn, the output is different, nicer, and more close to the one shown by the OP. I also removed the black filling of the dots:

This is the new code (only primediagram.lua has to be replaced):

-- This is primediagram.lua
local smallfirst = false
local off2 = 0

function circle(cx, cy, s)
tex.print(string.format("\\draw (%f, %f) circle(%f);", cx, cy, s))
end

function draw(N, cx, cy, s, a)
if N==0 then
return
end
if N==1 then
circle(cx,cy,s)
else
local f, r, d, x, y, off
off = 0
a = a or 0
tex.print(string.format("\\begin{scope}[xshift=%fcm, yshift=-%fcm, rotate=%f]", cx, cy, a))
f = primefactor(N)
if f == 2 then
oy = 0;
if N % 4 == 0 then
f = 4;
r = 2 * s / (f + 2);
d = f * s / (f + 2);
else
f = 2;
r = 0.75 * 2 * s / (2 + 2);
d = 2 * s / (2 + 2);
off = math.pi/2
end
else
r = 2 * s / (f + 2);
d = f * s / (f + 2);
end
for i = 0, f-1 do
local angle = math.pi + 2 * math.pi * (i + 0.5) / f + off
x = math.sin(angle);
y = math.cos(angle);
draw(N / f, x * d, y * d , r, angle*180/math.pi+180);
end
tex.print("\\end{scope}")
end
end

local primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43,
47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109,
113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181,
191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257,
263, 269, 271}

function primefactor(N)
local ans = N;
for i,pi in pairs(primes) do
if N % pi == 0 then
ans = pi;
if smallfirst then
return ans
end
end
end
return ans
end

• very nice, beautifully done! this is exactly what I was looking for, just a minor point on your modified primediagram.lua version the powers of 2 are not showing up correctly, for example, the numbers 32,16, 8 and 4 are showing up as if 4 was a prime number... then that affects all the numbers with powers-of-two factors Commented Oct 5, 2015 at 15:21
• This is made on purpose, since a group of four dots is easier to visually "parse" than two groups of two, as described in mathlesstraveled.com/2012/10/05/factorization-diagrams (who had first the idea of this kind of representation, aparently) Commented Oct 5, 2015 at 15:39
• I see, yes even on my original file, the special treatment of 2 show up there... thanks! Commented Oct 5, 2015 at 15:45
• Superb. Beautiful example of using Lua to do the heavy lifting and TeX to do the beautification. Commented Oct 5, 2015 at 19:07

Here is a tikzmath solution.

\documentclass[varwidth=147mm]{standalone}
\usepackage{tikz}
\usetikzlibrary{math}
\tikzmath{
% draw diagram for \n centered at (\x,\y) with radius \r
function primediagram(\n,\x,\y,\r){
int \n, \largest;
\largest = \n;
if \n != 4 then {% 4 is considered as particular case
% find the largest prime divisor
for \d in {61,59,53,47,43,41,37,31,29,23,19,17,13,11,7,5,3,2}{
if \d < \n && \largest == \n && abs(\n/\d - div(\n,\d)) < .001 then{
\largest = \d;
};
};
};
% if \n is prime or 4, draw the circles, else recursion ...
\step = 360/\largest;
for \i in {1,...,\largest}{
\a = (\n==2||\n==8||\n==32)? 0:((\n==4)? 45:90); % aesthetic adjustment
\newx = \n==1 ? 0 : \x+cos(\a+\i*\step)*\r;
\newy = \n==1 ? 0 : \y+sin(\a+\i*\step)*\r;
if \largest == \n then{
{\fill (\newx,\newy) circle(1.8*\r/\largest);};
}
else {
primediagram(\n/\largest,\newx,\newy,\r/\largest);
};
};
};
}
\begin{document}
\foreach \n in {1,...,35}{%
\begin{tikzpicture}[scale=.7]
\path (2.1,-2.1) rectangle (-2.1,2.1);
\draw (2,-2) rectangle (-2,2) node[red,below right]{\n};
\tikzmath{primediagram(\n,0,0,1);};
\end{tikzpicture}\linebreak[0]%
}
\end{document}