mersenneforum.org Leading numbers of tetration
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2019-01-25, 11:25 #1 tetramur   "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 Graham-Conway number (4^^^^4) 6) Any more? Last fiddled with by tetramur on 2019-01-25 at 11:29
 2019-01-25, 17:33 #2 CRGreathouse     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 (!).
2019-01-25, 18:41   #3
tetramur

"unknown"
Jan 2019
anywhere

17 Posts

Quote:
 Originally Posted by CRGreathouse 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?".

2019-01-25, 19:23   #4
R. Gerbicz

"Robert Gerbicz"
Oct 2005
Hungary

5FB16 Posts

Quote:
 Originally Posted by CRGreathouse 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.

2019-01-26, 00:24   #5
Dr Sardonicus

Feb 2017
Nowhere

2×2,687 Posts

Quote:
 Originally Posted by R. Gerbicz (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...

 2019-01-31, 17:59 #6 ixfd64 Bemusing Prompter     "Danny" Dec 2002 California 1001011111112 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 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
2019-10-24, 16:12   #7
tetramur

"unknown"
Jan 2019
anywhere

17 Posts

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

 Similar Threads Thread Thread Starter Forum Replies Last Post enzocreti enzocreti 13 2019-02-01 08:40 shortcipher YAFU 5 2018-03-27 13:59 Primeinator Information & Answers 9 2010-06-25 07:36 fgrieu Factoring 7 2009-09-23 11:45 ShiningArcanine Math 3 2007-11-07 00:45

All times are UTC. The time now is 06:00.

Thu Jan 27 06:00:16 UTC 2022 up 188 days, 29 mins, 1 user, load averages: 1.71, 1.59, 1.58

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔