2020-10-19 MATH 3600 Factor Trees

383 days ago by calkin

Goal: every non-prime integer $n$ has a factorization into $n=ab$ in which $a<b$ and $a$ and $b$ are as close together as possible.  For example, $105 = 7 \times 15$.  Here $a$ will be the largest divisor of $n$ for which $a^2<n$.  We can use this fact to create unique factor trees for each $n$.  If $n$ is prime, the tree will be a single vertex.  Otherwise, each vertex of the tree will have either 0 or 2 children.  

It is to be expected, for many reasons, that there will be multiple copies of trees: for example, the single vertex tree occurs for every prime, the three vertex tree occurs for every biprime (including $p^2$), etc.  It seems highly likely, though it is not yet clear to me, that every tree ought to occur infinitely often.  Can we find a trivial proof of this?

If we take the first $n$ with a given tree $T$, we can ask what subsequence of $N$ this gives us.  Further questions abound: does every prime $p$ appear as a factor of such an $n$?  If so, in what order do the primes first appear?  How far out do we have to go to see each prime? 

T1=[] 
       
T2=[T1,T1] 
       
print(T2) 
       
[[], []]
[[], []]
T3 = [T2,T1] 
       
T4=[T1,T2] 
       
print(T1,T2,T3,T4) 
       
([], [[], []], [[[], []], []], [[], [[], []]])
([], [[], []], [[[], []], []], [[], [[], []]])
T3==T4 
       
False
False
T3==[T2,T1] 
       
True
True
n=2*3*5*7*11 
       
a=n.divisors() b=len(a) 
       
print(b) 
       
32
32
a[15] 
       
42
42
a[16] 
       
55
55
print(a) 
       
[1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 21, 22, 30, 33, 35, 42, 55, 66, 70,
77, 105, 110, 154, 165, 210, 231, 330, 385, 462, 770, 1155, 2310]
[1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 21, 22, 30, 33, 35, 42, 55, 66, 70, 77, 105, 110, 154, 165, 210, 231, 330, 385, 462, 770, 1155, 2310]
42^2 
       
1764
1764
55^2 
       
3025
3025
FactorTreeDictionary= {'[]':2,'[[],[]]':4,'[ [] , [[],[]] ]':8} 
       
FactorTreeDictionary.has_key('[[],[]]') 
       
True
True
def FactorTree(n): #recursive algorith to compute FactorTree --- replace with lists and dictionaries later if is_prime(n): return([]) else: divs=n.divisors() l=len(divs) a= divs[floor((l-1)/2)] b= divs[ceil((l-1)/2)] return([FactorTree(a),FactorTree(b)]) 
       
i.factor() 
       
3^2 * 11 * 101
3^2 * 11 * 101
FactorTreeDictionary= {} 
       
FactorTreeDictionary= {} for i in srange(2,100): L=FactorTree(i) if FactorTreeDictionary.has_key(str(L))==False: FactorTreeDictionary.update({str(L):[i]}) #print i,i.factor() #if i%29 ==0: # print i else: FactorTreeDictionary[str(L)].append(i) 
       
FactorTreeDictionary 
       
{'[[[], [[], []]], [[], [[], []]]]': [64, 96],
 '[[[], [[], []]], [[], []]]': [72, 80],
 '[[[], [[], []]], []]': [88],
 '[[[], []], [[], [[], []]]]': [32, 48],
 '[[[], []], [[], []]]': [16, 24, 36, 54, 60, 81, 90],
 '[[[], []], []]': [20, 28, 42, 44, 52, 66, 68, 76, 78, 92, 99],
 '[[], [[], [[], []]]]': [40, 56, 84],
 '[[], [[], []]]': [8, 12, 18, 27, 30, 45, 50, 63, 70, 75, 98],
 '[[], []]': [4,
  6,
  9,
  10,
  14,
  15,
  21,
  22,
  25,
  26,
  33,
  34,
  35,
  38,
  39,
  46,
  49,
  51,
  55,
  57,
  58,
  62,
  65,
  69,
  74,
  77,
  82,
  85,
  86,
  87,
  91,
  93,
  94,
  95],
 '[]': [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]}
{'[[[], [[], []]], [[], [[], []]]]': [64, 96],
 '[[[], [[], []]], [[], []]]': [72, 80],
 '[[[], [[], []]], []]': [88],
 '[[[], []], [[], [[], []]]]': [32, 48],
 '[[[], []], [[], []]]': [16, 24, 36, 54, 60, 81, 90],
 '[[[], []], []]': [20, 28, 42, 44, 52, 66, 68, 76, 78, 92, 99],
 '[[], [[], [[], []]]]': [40, 56, 84],
 '[[], [[], []]]': [8, 12, 18, 27, 30, 45, 50, 63, 70, 75, 98],
 '[[], []]': [4,
  6,
  9,
  10,
  14,
  15,
  21,
  22,
  25,
  26,
  33,
  34,
  35,
  38,
  39,
  46,
  49,
  51,
  55,
  57,
  58,
  62,
  65,
  69,
  74,
  77,
  82,
  85,
  86,
  87,
  91,
  93,
  94,
  95],
 '[]': [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]}

Does every power of 2 create a new tree?

Which primes do we see as factors in the first trees?  

What is the relative frequency with which we see each prime?

Which primes appear with higher or lower frequency?  Conjecture a pattern?

How often does each tree appear?  

Can we create a list of all trees?  Perhaps with all trees listed in some natural order

(so, for example, trees with  $k$ leaves appear earlier than trees with  $k+1$ leaves?)

Can we automatically generate these?

FactorTreeDictionary[str(FactorTree(2))] 
       
97
97