mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2019-01-25, 11:25   #1
tetramur
 
"unknown"
Jan 2019
anywhere

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

Last fiddled with by tetramur on 2019-01-25 at 11:29
tetramur is offline   Reply With Quote
Old 2019-01-25, 17:33   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).
CRGreathouse is offline   Reply With Quote
Old 2019-01-25, 18:41   #3
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't think any algorithm with reasonable time is known for leading digits of tetration, let alone iterated log (!).
No, it is unknown by now. But question is: "Do it exist?".
tetramur is offline   Reply With Quote
Old 2019-01-25, 19:23   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×13×23 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't think any algorithm with reasonable time is known for leading digits of tetration.
(For definiton, see https://en.wikipedia.org/wiki/Tetration)
Here a=power of ten looks like easy.
R. Gerbicz is offline   Reply With Quote
Old 2019-01-26, 00:24   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

32·557 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
(For definiton, see https://en.wikipedia.org/wiki/Tetration)
Here a=power of ten looks like easy.
FWIW, I remember a number called "Mega" defined in a book called Mathematical Snapshots 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...
Dr Sardonicus is online now   Reply With Quote
Old 2019-01-31, 17:59   #6
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2·17·71 Posts
Default

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.

Last fiddled with by ixfd64 on 2019-01-31 at 18:02
ixfd64 is offline   Reply With Quote
Old 2019-10-24, 16:12   #7
tetramur
 
"unknown"
Jan 2019
anywhere

17 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
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.
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.

Last fiddled with by tetramur on 2019-10-24 at 16:15
tetramur is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Exponents leading to pg primes enzocreti enzocreti 13 2019-02-01 08:40
nextprime function is spooked by leading zero. shortcipher YAFU 5 2018-03-27 13:59
Leading Edge Primeinator Information & Answers 9 2010-06-25 07:36
Fixed leading bits in RSA modulus, vs NFS fgrieu Factoring 7 2009-09-23 11:45
Tetration questions ShiningArcanine Math 3 2007-11-07 00:45

All times are UTC. The time now is 16:45.


Wed Oct 27 16:45:09 UTC 2021 up 96 days, 11:14, 0 users, load averages: 0.72, 1.35, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.