#!/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/