#!/usr/bin/env sage -python
#
# Written by Tom Cuchta
# 9 August 2009
#

import sys
from sage.all import *
import networkx

#gpf(n) - return the greatest prime factor of an integer
#
def gpf( n ):
	n = int(n)
	prime_factorization = factor(n)					# returns an array of (p,n)'s where (p,e) is
									# the prime it its exponent sorted such that 
									# the last entry is largest prime

	return prime_factorization[len(prime_factorization) - 1][0] 	# -1 because 0 included in array beginning
			     						# [0] because test[len(test)-1] is an array 
									# (p,e) where p is the prime and e is its exponent

#
#

#gpfcycle( n ):
#
def gpfcycle( n ):
	gpfnodes = [gpf(n)]						# generates 1st gpf of given number
									# no function applied before evaluation
	
#	NOTE: the following line of code applies 3a+1 BEFORE evaluating the first time
#	keep it commented unless you know what you're doing!	
#	gpfnodes = [gpf(3*int(n)+1)]					# generates the 1st next integer whose gpf we want
#									# uses formula 3*a + 1 where a is the given argument
									# This formula CAN be changed!
	i=0
	while i!=-1:
#		new_gpf_node = gpf(3*gpfnodes[len(gpfnodes)-1]+1)	# generates the next logical node in the sequence	
		new_gpf_node = gpf(3*gpfnodes[len(gpfnodes)-1]+1)	# 3n+1
		if new_gpf_node in gpfnodes:				# checks to see if next generated node is already 
			gpfnodes.append(new_gpf_node)			# in the sequence -- if it is, we quit the loop
			i=-1						# by setting i=-1
		else:
			gpfnodes.append(new_gpf_node)			# if next node is not in sequence, then we add it
									# to the sequence
	return gpfnodes
#
#

#gengraph( n )
#
def gengraph( n ):
	gpfgraph = gpfcycle(n)										# get a no-repeat sequence
	#
	# EXAMPLE:
	# output of gpfcycle(752): [61, 23, 7, 11, 17, 13, 5, 2, 7]
	# 

	# The below constructs the above sequence into one that can be inputted into the sage graph command
	#
	#
	# It turns out there are add_node and add_edge object functions for graph objects. This needs rewritten.
	# So good luck figuring out this mess below!
	# The important part is that it works!
	#
	graph_defn = "{"
	graph_defn = graph_defn + str(gpfgraph[0]) + ": [" + str(gpfgraph[1]) + "]"
	i=2
	while i < len(gpfgraph):
		graph_defn = graph_defn + "," + str(gpfgraph[i-1]) + ": [" + str(gpfgraph[i]) + "]"
		i=i+1
	graph_defn = graph_defn + "}"
	#
	# example of a completed graph_defn for input 752 
	# {47: [71],71: [107],107: [23],23: [7],7: [11],11: [17],17: [13],13: [5],5: [2],2: [7]}
	#
	# This format was shown to me in a tutorial and I just mimiced it instead of looking at 
	# the graph class proper. Basically you have {#_1:[@_1],...,#_n:[@_n]} where #_i is a node
	# and @_i is the nodes that node is connected to
	#
	# This format can be plugged into Graph() from the networkx library and it will generate
	# the png. 
	#

	D = Graph( sage_eval(graph_defn) )
	D.show()

#
#

gengraph(int(sys.argv[1]))		# generates the relevant gpf graph for input
					# run by doing ./main.py ## 

#i=0					#
#while(i < 8):				# use this loop to generate multiple graphs at once	
#	gengraph(int(sys.argv[1])+i)	# each instance of gengraph() will produce a file 
#	i=i+1				# tmp_#.png in the temp folder for sage identified
					# by the processid of the instance of the program
					# running -- I don't know how this behaves in Windows
					# MY graph folder is at ~/.sage/temp/computername.local/