Prime Factorization Trees

by The Bayesian Observer

A positive integer can be visualized as a tree, structured by its prime factors. I wrote a little program which takes a positive integer as input, and creates a tree layout that shows its prime factors visually.

Here’s the tree for 70:

The tree is drawn recursively, starting with a root node in the center of a circular layout. The degree of the root node is the largest prime factor. Then, more prime factors are added recursively (including multiplicities of the same prime factor) in decreasing order of factor, by growing the tree. Finally, the leaf nodes are displayed as filled black circles. As seen from the tree above, the prime factorization of 70 is 7*5*2.

Here is the layout for 700 = 7 * 5 * 5 * 2 * 2:

This method of displaying numbers has been proposed and implemented by others on the internet, with much prettier results. I was too tempted to quickly try it for myself using a graph visualization library, because the graph drawing library can do all the heavy lifting. I used Graphviz (developed at AT&T Labs) which I use often for visualizing network data. I also wanted to see if the underlying tree structure revealed by the edges in the graph makes the prime factorization more evident.

Here are a few more trees:

243 = 3^5:

43 (a prime):

128 = 2^7:

121 = 11 * 11:

625 = 5^4:

2310 = 11 * 7 * 5 * 3 * 2:

Code gist (Without prime factorization implementation and graph library):

def createnode(x):
	# x == 1: support node
	# x == 0: real node
	global nodenames
	name = random.random()
	while name in nodenames:
		name = random.random()
	nodenames.add(name)
	if x == 1:
		retval = '"'+str(name)+'"'+whitenode
	else:
		retval = '"'+str(name)+'"'+blacknode
	print retval
	return '"'+str(name)+'"'

def createedge(x,y,t):
	# x and y are nodes, t is type (0=last stage of the tree, 1=all other stages)
	if t == 1:
		print x + '--' + y + ' [color="#DDDDDD"]'
	if t == 0:
		print x + '--' + y + ' [color=grey]'
	return x + '--' + y

pf = factorization(n) # keys are factors, values are the multiplicity of the prime factors
factors = []
for fac in pf:
	for multiplicity in range(0, pf[fac]):
		factors.append(fac)
factors = sorted(factors, reverse=True)
print 'graph G{'
print 'overlap = false'
nodenames = set()
edgeset = set()
whitenode = ' [fixedsize=True, width=0.1, height=0.1, color = white, fontcolor = white, shape = circle]'
blacknode = ' [color = black, style = filled, fontcolor = black, shape = circle]'
rootnode = createnode(1)
currentset = set()
currentset.add(rootnode)
level = len(factors) + 1
for i in range(0, len(factors)):
	level -= 1
	f = factors[i]
	nodetype = 1
	if i == len(factors) - 1:
		nodetype = 0
	newnodeset = set()
	for eachnode in currentset:
		for j in range(0, f):
			newnode = createnode(nodetype)
			newnodeset.add(newnode)
			edgeset.add(createedge(eachnode, newnode, level, nodetype))
	currentset = newnodeset
print '}'

For prime factorization, I used the this implementation.

About these ads