mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Computer Science & Computational Number Theory (https://www.mersenneforum.org/forumdisplay.php?f=116)

 tetramur 2019-01-25 11:25

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 Graham-Conway number (4^^^^4)
6) Any more?

 CRGreathouse 2019-01-25 17:33

I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).

 tetramur 2019-01-25 18:41

[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?".

 R. Gerbicz 2019-01-25 19:23

[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.

 Dr Sardonicus 2019-01-26 00:24

[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...

 ixfd64 2019-01-31 17:59

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 non-decimal 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.

 tetramur 2019-10-24 16:12

[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 non-decimal 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.