20190125, 11:25  #1 
"unknown"
Jan 2019
anywhere
17 Posts 
Leading numbers of tetration
I would like to solve this problem.
Question: Can the algorithm for finding the leading digits of some tetration with time complexity of iterational logarithm (or, ideally, the constant time complexity) exist? If yes, how this algorithm can be implemented? The most wanted: 1) Mega, 2) 4096^^166, 3) Tritri (3^^^3) 4) Grahal (3^^^^3) 5) g1 in the construction of GrahamConway number (4^^^^4) 6) Any more? Last fiddled with by tetramur on 20190125 at 11:29 
20190125, 17:33  #2 
Aug 2006
3·1,993 Posts 
I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).

20190125, 18:41  #3 
"unknown"
Jan 2019
anywhere
17 Posts 

20190125, 19:23  #4  
"Robert Gerbicz"
Oct 2005
Hungary
5·13·23 Posts 
Quote:
Here a=power of ten looks like easy. 

20190126, 00:24  #5  
Feb 2017
Nowhere
138E_{16} Posts 
Quote:
Good luck with that... 

20190131, 17:59  #6 
Bemusing Prompter
"Danny"
Dec 2002
California
2·17·71 Posts 
I don't think it's feasible to calculate the leading digits of very large numbers. However, it's possible to narrow down the first digit in nondecimal bases. For example, Graham's number must start with 1 in base 3 because it's basically an exponential stack of 3's.
You can always calculate the ending digits using modular arithmetic. Last fiddled with by ixfd64 on 20190131 at 18:02 
20191024, 16:12  #7  
"unknown"
Jan 2019
anywhere
17 Posts 
Quote:
But: "Even if we do find a O(log* n) algorithm, it becomes unworkable at the pentational level. A constant time algorithm is needed, and finding such an algorithm would take a miracle."  and methinks that this is almost impossible. Last fiddled with by tetramur on 20191024 at 16:15 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Exponents leading to pg primes  enzocreti  enzocreti  13  20190201 08:40 
nextprime function is spooked by leading zero.  shortcipher  YAFU  5  20180327 13:59 
Leading Edge  Primeinator  Information & Answers  9  20100625 07:36 
Fixed leading bits in RSA modulus, vs NFS  fgrieu  Factoring  7  20090923 11:45 
Tetration questions  ShiningArcanine  Math  3  20071107 00:45 