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? 
I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).

[QUOTE=CRGreathouse;506839]I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).[/QUOTE]
No, it is unknown by now. But question is: "Do it exist?". 
[QUOTE=CRGreathouse;506839]I don't think any algorithm with reasonable time is known for leading digits of tetration.[/QUOTE]
(For definiton, see [url]https://en.wikipedia.org/wiki/Tetration[/url]) Here a=power of ten looks like easy. 
[QUOTE=R. Gerbicz;506846](For definiton, see [url]https://en.wikipedia.org/wiki/Tetration[/url])
Here a=power of ten looks like easy.[/QUOTE] FWIW, I remember a number called "Mega" defined in a book called [u]Mathematical Snapshots[/u] by Hugo Steinhaus. One defines n in a triangle as n^n, and n in a square as "n in n (nested) triangles. Finally, n in a circle is n in n (nested) squares. The number mega is 2 in a circle. So, 2 in a circle is 2 in 2 nested squares. Now evaluating 2 in the inner square, that's 2 in two nested triangles. Now 2 in the inner triangle is 2^2, or 4. Now, we have 4 in the outer triangle is 4^4, or 256. That leaves 256 in the outer square. That's 256 in 256 (nested) triangles. Good luck with that... 
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. 
[QUOTE=ixfd64;507268]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.[/QUOTE] I'm currently trying to evaluate the fractional part of the logarithm of tetration using repeated squaring  but I want to evaluate this number (between 0 and 1) directly, 'cause this becomes quickly infeasible to compute in any case. If this is possible, then we will have an algorithm of complexity of double logarithm. Then we need to research the possibility of compute these digits using double logarithm  this gives us the complexity of triple logarithm... continuing, we have iterated logarithm. 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. 
All times are UTC. The time now is 09:58. 
Powered by vBulletin® Version 3.8.11
Copyright ©2000  2021, Jelsoft Enterprises Ltd.