June 4th, 2013, 01:27 AM  #11 
Member Joined: May 2013 Posts: 35 Thanks: 1  Re: Power Tower Size
based on further analysis of the problem; the right most 3 powers are the only 3 you need to concern yourself with so long as they are not equal. beyond that, a number would have to be bigger than 1 followed by 10 trillion zeros to have a significant impact on the problem. so my algorithm would be... Code: import math input1 = raw_input("what's your tower A?") input2 = raw_input("what's your tower B?") input1 = input1.split() input2 = input2.split() i = len(input1) j = len(input2) if i < j: while i > 1: if input1[i] != input2[i]: break else: while j > 1: if input1[j] != input2[j]: break if i == 1 or j == 1 and i ==j: print "towers are equal." elif i == 1 or j == 1: if i > j: print "tower 1 is bigger." else: print "tower 2 is bigger." i = j j = i a = input1[i] b = input1[i1] if len(input1) < 3: valueA = a*math.log(b,10) else: c= input[i3] valueA = a*math.log(b,10) +math.log(math.log(c,10),10) a = input2[i1] b = input2[i2] if len(input2) <3: valueB = a*math.log(b,10) else: c= input[i3] valueB = a*math.log(b,10) +math.log(math.log(c,10),10) if valueA > valueB: print "tower A is bigger." else: print "tower B is bigger." 
June 4th, 2013, 05:44 AM  #12  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Power Tower Size Quote:
 
June 4th, 2013, 05:48 AM  #13  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Power Tower Size Quote:
I agree that taking logarithms repeatedly is the main approach, but the corner cases are still hard to handle.  
June 4th, 2013, 07:03 AM  #14  
Member Joined: May 2013 Posts: 35 Thanks: 1  Re: Power Tower Size Quote:
Quote:
let's take two big powers and compare them. is 2^3^4^5^6^7 greater than or less than 7^6^5^4^3^2? 5^6^7can be "evaluated" as 6*log 7 +log log 5 = 5.292. 4^3^2 can be "evaluated" as 2*log 3 + log log 4 =0.734. now, if went to evaluating 4 exponents i would get the following. 4^5^6^7 ~ log(6^7*log 5 +log log 4) = 5.292 5^4^3^2 ~ log(3^2*log 4 +log log 5) = 0.721 as you can see, adding the fourth exponent hardly affects the problem at all. i may as well ignore the two additions and just evaluate the two left hand sides. in order for the fourth exponent to matter the value itself would have to be really large. if i wanted to evaluate the 5th exponent, the value would have to be monstrous in order to effect the problem one iota.  
June 4th, 2013, 07:13 AM  #15  
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Power Tower Size Quote:
Is this problem in the class P? If yes, then what is the algorithm solving it in polynomial time? Otherwise, what is the fastest algorithm that can solve it? The asker wants a polytimesolution, so in particular you can't write out the numbers in their full form. Quote:
(To make the problem harder you could also allow the tetration operator explicitly, which would allow you to describe larger towers with a small length. Then you wouldn't even be able to take the requisite number of logarithms at all, let alone at high precision.)  

Tags 
power, size, tower 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Set size is relative  Same topology of negative size sets  BenFRayfield  Applied Math  4  December 21st, 2013 10:58 PM 
Height of the tower  rakmo  Algebra  3  March 28th, 2013 05:20 AM 
Size of subset of power set....  cknapp  Applied Math  3  December 16th, 2007 09:32 AM 
What is a Tower?  picco  Abstract Algebra  1  October 27th, 2007 08:22 PM 
THE LEANING TOWER OF PISA  Arley  Calculus  0  December 31st, 1969 04:00 PM 