Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [big-numbers]

For questions relating to the computation, estimation and properties of extremely large finite quantities that are not usually used in mainstream mathematics. This is not for questions that just have large numbers; the fact that a number is very large has to affect the question.

-1
votes
0answers
12 views

Is there any way to deduce whether TREE(3) or g (as defined as the function by which g64 is Graham's number) sub Graham's number is bigger?

Two obscenely large numbers. Open-ended question with no other explanation. Is there any way to solve this, not knowing how many 3s are nested in Graham's Number?
0
votes
1answer
74 views

What is the language of FOST (First Order Set Theory)

I’ve been reading about Rayo’s number and I’m finding it difficult to grasp what exactly the language of FOST is. I understand the concept of finding the smallest finite number greater than any ...
2
votes
1answer
50 views

How much bigger is 3↑↑↑↑3 compared to 3↑↑↑3?

3↑↑↑3 is already mind-bogglingly large, but how much larger is 3↑↑↑↑3? Is it so large that it is simply around 3↑↑↑↑3 times larger than 3↑↑↑3? Or is there another way to express its magnitude in terms ...
1
vote
1answer
172 views

What is explanation of $\text{Sat}([φ],s)$ in the definition of Rayo’s number?

The definition of $\text{Sat}([φ],s)$ can be found here. All I want is an explanation of what each line in this definition means and how $\text{Sat}([φ],s)$ works. The only relevant thing that I ...
2
votes
1answer
72 views

lower bound for Kruskal's weak tree function

The wiki on Kruskal's tree theorum briefly mentions the weak tree function regarding unlabeled trees. It gives values of tree(1) = 2, tree(2) = 5 (trivial to prove) but then it gives tree(3) >= 262140....
3
votes
4answers
691 views

What is the best algorithm for finding the last digit of an enormous exponent? [duplicate]

I found most answers here not clear enough for my case such as $$ 123155131514315^{4515131323164343214547} $$ I wrote the $n\bmod10$ in Python and execution time ran out. So I need a faster ...
2
votes
1answer
94 views

Question about $TREE(3)$ and Graham's Number

Lets say: $G=\text{Graham's Number}$. And: $$ \begin{align*} \alpha_1&=G\uparrow^G G, \\ \alpha_2&=\alpha_1\uparrow^{\alpha_1} \alpha_1 \\ &\vdots\\ \beta_1 &= \alpha_G\uparrow^{\...
8
votes
0answers
123 views

What is the largest number used in a useful mathematical proof that isn't just an upper or lower bound? [closed]

There are quite a few famous gigantic numbers used in useful mathematical proofs, like Skewes's number, Graham's number, and the number $2 \uparrow \uparrow 10^{10^6}$ from Coward and Lackenby's 2011 ...
2
votes
0answers
140 views

When does the busy beaver function surpass TREE(n)? [closed]

Since TREE is a computable function the BB function grows faster than it, but TREE seems to grow much more quickly early on, so when does Busy Beaver surpass it?
13
votes
3answers
1k views

Sum of digits of sum of digits of sum of digits of $7^{7^{7^7}}$

On the back of a mathematical magazine, I came across some "quick facts" about the number 7. Most of them were real life related ones, like "Rome was buit on 7 hills", "the neck of most mamals is made ...
0
votes
0answers
50 views

(a / b) mod p for large a and b

i get stuck in finding $(a / b) \bmod p$ what i did is googled and saw some theories and i did $(a/b) \bmod p = ((a \bmod p) * (((b^{\,p - 2} \bmod p)) \bmod p)) \bmod p$ where $p$ is prime number $(...
0
votes
2answers
81 views

There is a way to write TREE(3) via $F^a(n)$?

I read about Graham number and TREE(3). Graham number is: $f^{64}(4)$ where $f(n)=3\uparrow^n 3$ My question is: If there is a way to write ...
3
votes
2answers
116 views

Where does this array-based fast-growing function fall in the fast-growing hierarchy, and how does it compare to TREE(n)?

[See below for a clarification edit and progress thus far] So I have been reading into the "fast-growing hierarchy" of functions, and I devised this (somewhat convoluted) function for generating very ...
1
vote
2answers
83 views

Is there any function that like this function?

I got a idea from fast-growing hierarchy function to create new function g.(I think it is computable.) $$g_0(n) = n + 1$$ $$g_{a+1}(n) = g_a^{g_a(n)}(n)$$ Which different from fast-growing ...
7
votes
1answer
151 views

Is it true that $\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$ has period $18$ and can never take the values $3$ and $6$?

Is it true that the arithmetical function $f:\mathbb{N}\setminus\{1\}\rightarrow \mathbb{Z}_9$ given by $$f(x\mid k)=\underbrace{x^{x^{x^{.^{.^{.^x}}}}}}_{k\,\text{times}}\pmod9$$ has period $...
7
votes
0answers
453 views

Is $\frac {2^{716\ 915\ 680\ 417}+1}{3}$ a (Wagstaff)-prime?

How can I verify whether $$\frac {2^{716\ 915\ 680\ 417}+1}3$$ is a (Wagstaff-)prime without the help of a calculator?
3
votes
1answer
127 views

Super-fast growing function exceeding Graham's number [duplicate]

If we define $G_0 = 10^{100}$, and $G_n = 10^{G_{n-1}}$ (hence $G_0$ is a googol, $G_1$ is a googolplex, $G_2$ is a googolplexian), for what first value of n will $G_n$ exceed Graham's number?
12
votes
1answer
402 views

What is $\underbrace{2018^{2018^{2018^{\mathstrut^{.^{.^{.^{2018}}}}}}}}_{p\,\text{times}}\pmod p$ where $p$ is an odd prime?

This recent question inspired me to explore values concerning modulo arithmetic of tetrations, and I thus pose the following question. Is there a general expression for the value of $$\underbrace{...
3
votes
3answers
142 views

$2014^{2014^{2014}}\bmod2011$

I get a question on exam today. What is $$2014^{2014^{2014}}\bmod2011$$ I know that the answer is $985$ but how do I get it?
0
votes
0answers
76 views

Are the lower bounds for the fast growing hierarchy valid for all $n\ge 3$?

Here : http://googology.wikia.com/wiki/Fast-growing_hierarchy lower bounds for the fast growing hierarchy are shown. Unfortunately, it is only stated that the inequalities hold for sufficiently ...
0
votes
0answers
33 views

How tight can we bound $4$ -entry-conway chains with the fast growing hierarchy?

See here : http://googology.wikia.com/wiki/Chained_arrow_notation for the definitions of Conways chained-array-notation and the fast growing hierarchy. Is the approcimation $$a\rightarrow b\...
2
votes
2answers
117 views

Can $10\uparrow^n m<2\uparrow^n (m+2)$ be formally proven?

See here : http://googology.wikia.com/wiki/Arrow_notation for the definition of the up-arrow function. Can $10\uparrow^n m<2\uparrow^n (m+2)$ be formally proven for all $m\ge 1$ and $n\ge 3$ ?...
1
vote
0answers
51 views

Are those estimates of the magnitude of huge numbers correct?

See here http://googology.wikia.com/wiki/Fast-growing_hierarchy for the definitions of the fast growing hierarchy, chained-arrow-notation and two-dimesnional-array-notation. The first number is ...
1
vote
1answer
178 views

What's the largest proven lower-bound for SCG(13)?

I hope someone can answer this question. If you can answer it, then you already know what SCG(13) is. SCG(13) is a very, very large number which is part of a theorem about graphs. It's at least one ...
0
votes
0answers
37 views

Growth rate of three functions containing conway-chains equal?

See here : http://googology.wikia.com/wiki/Chained_arrow_notation for the definition of conway-chains I have three functions : $$f(n)=2\rightarrow 3\rightarrow n\rightarrow 2$$ $$g(n)=3\rightarrow ...
0
votes
0answers
39 views

What is meant with “mix different types of arrows”?

Here : http://googology.wikia.com/wiki/Chained_arrow_notation an extension of the Chained-arrow notation is mentioned. I am confused by : "If we allow to mix different types of arrows in a single ...
0
votes
0answers
42 views

Can I prove $X\rightarrow 1\rightarrow Y=X$ using the given definition?

Here : http://googology.wikia.com/wiki/Chained_arrow_notation the definition of the chained arrow notation is given. How can I prove $$X\rightarrow 1\rightarrow Y=X$$ for every chains $X,Y$ ...
2
votes
1answer
126 views

Decimal expansion of the number $f_3(3)$ with PARI/GP?

I tried to calculate the number $f_3(3)$ with PARI/GP. It seems the number is too large to be calculated exactly. I would like to analyze the full decimal expansion. Is there any trick to get all ...
0
votes
2answers
104 views

3↑↑↑3= ? but with 10 instead of 3 ( approximation, order of magnitude )

3↑↑↑3= (or near) in power tower of 10 or in ( Knuth ) arrow ↑ notation of 10 to get a sense of it's order of magnitude; I grasp numbers more easily with 10 3↑↑↑3 being the first really huge number in ...
4
votes
2answers
127 views

Magnitude of $f_3(n)$ compared to power towers of tens

In the fast growing hierarchy , the sequence $f_2(n)$ is defined as $$f_2(n)=n\cdot 2^n$$ The number $f_3(n)$ is defined by $$f_3(n)=f_2^{\ n}(n)$$ For example, to calculate $f_3(5)$, we have to ...
9
votes
1answer
204 views

How did Euler disprove Mersenne's conjecture?

In 1644, Mersenne made the following conjecture: The Mersenne numbers, $M_n=2^n−1$, are prime for $n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257$, and no others. Euler found that the Mersenne ...
7
votes
2answers
194 views

How to determine $n$, such that $x\uparrow \uparrow n>10^{100}$?

If $x$ is a real number greater than $e^{e^{-1}}$ , then $x\uparrow \uparrow n$ (A power tower of $n$ $x's$) tends to $\infty$, if $n$ tends to $\infty$. Therefore, there must be a number $n$, such ...
1
vote
1answer
510 views

Why is TREE(3) not infinite? [duplicate]

this is my first ever question on this forum so bear with me if the formatting or phrasing of the question itself seems strange... I was reading about TREE(3) and the rules followed in generating ...
5
votes
1answer
817 views

Proof that TREE(n) where n >= 3 is finite?

Reading online, it generally seems accepted that TREE(n) where n >= 3 is a finite number, but large enough to be incomputable and only has extremely loose lower bounds today. TREE(n) is the function ...
3
votes
2answers
511 views

How to solve factorial equations with very big numbers

I have problem. I've calculated memory complexity of my algorithm. In exchange of very good time complexity of my algorithm, I have memory complexity $x!$, where $x$ is number of elements my algorithm ...
4
votes
0answers
229 views

Sanity check: does $D_{\omega_9}(9)$ exceed TREE(3)?

TREE(3) For the Golf a number bigger than TREE(3) challenge I wrote a program but I'm not sure it is bigger than TREE(3). The function TREE(k) gives the length of the longest sequence of trees T1, ...
1
vote
1answer
71 views

How does my modified ordinal hierarchy relate to other ordinal hierachies?

I was working on my answer for Golf a number bigger than TREE(3) and I realized I couldn't use The Hardy Hierarchy in the way wanted to. So I defined a slightly modified version: $$H'_0(n)=n+1$$ $$H'_\...
4
votes
0answers
105 views

Smallest prime factor of $\lfloor e\uparrow e\uparrow e\uparrow e\rfloor$?

What is the smallest prime factor of $$\lfloor e\uparrow e\uparrow e\uparrow e\rfloor$$ To get this number start with $1$ and apply the $\exp$-funtion four times, then take the integer part. This ...
7
votes
1answer
148 views

Smallest twin-prime-pair above $2\uparrow\uparrow 5\ $?

I searched the smallest prime larger than $$N:=2\uparrow\uparrow 5=2^{65536}$$ $N$ has $19\ 729$ digits. This is quite large and finding primes of this magnitude is not easy any more. I found $$N+44\ ...
-2
votes
1answer
145 views

Has something like “Knuth's Up-Arrow Factorial Notation” ever been used? If so, what practical uses does it have?

I was studying Knuth's up-arrow notation and I was wondering if ever something like "Knuth's up-arrow factorial notation" has ever been used. Now I know this probably isn't a recognizable term, ...
3
votes
1answer
146 views

The Ackermann hierarchy vs. the fast growing hierarchy

Suppose we've defined the Ackermann hierarchy as follows: $$A_\alpha(n)=\begin{cases}n+1,&\alpha=0\\A_{\alpha[n]}(n),&\alpha\in\Bbb{Lim}\\A_\beta(1),&n=0,\alpha=\beta+1\\A_\beta(A_\alpha(...
2
votes
1answer
226 views

computable function not outgrowed by fast growing hierarchy

I have been looking at this question Does there exist a computable function that grows faster than fast growing hierarchy?, but I dont understand the answer and cant use it to answer this question ...
4
votes
1answer
190 views

Tighter bounds on the fast growing hierarchy?

Not a dupe of this question, as I'm searching for tighter bounds. We define the fast growing hierarchy for finite values as follows: $$f_k(n)=\begin{cases}n+1,&k=0\\f_{k-1}^n(n),&k>0\end{...
3
votes
0answers
77 views

For which n does the nth “hyperoperation number” n[n]n begin with n in base 2?

If $[n]$ denotes the $n$th binary hyperoperation in the sequence $(+,\times,\uparrow,\uparrow\uparrow,...)$, then the following equality is readily verified for $n=1,2,3,4:$ $$n\,[n]\,n\ =\ (n_2...)...
8
votes
1answer
190 views

Are there nontrivial equations for hyperoperations above exponentiation?

A similar question was asked in comments elsewhere. A paper by Roberto Di Cosmo and Thomas Dufour ("The Equational Theory of 〈ℕ, 0, 1, + , ×, ↑〉 Is Decidable, but Not Finitely Axiomatisable") asserts ...
1
vote
1answer
57 views

how to get the integer part of very large integer multiples of irrational numbers such as $\pi$?

Do I need exact value of $\pi $ upto say $100$ digits if my multiplier is order $10^{10}$.
0
votes
2answers
328 views

How Big would “Graham's Tree” be?

What if in Graham’s Number every “3” was replaced by “tree(3)” instead? How big is this number? Greater than Rayo’s number? Greater than every current named number?
2
votes
2answers
108 views

How does one make a large number using computable methods?

Context: I'm starting another contest and I was interested in how one makes an extremely large finite number as simply as possible. For starters, the Ackermann function is extremely simple: $$A(0,n)=...
3
votes
1answer
89 views

What are these asymptotics called when two functions are bounded by a fixed shift of the other?

When studying large numbers and extremely fast growing functions, I've noticed that the normal big-O notations are not enough to reasonably compare things. Instead, I've been using this: $$f=\...
0
votes
3answers
79 views

Are there more permutations of pixels in a picture or bases in the human genome?

An iPhone 7 takes pictures that have roughly 12 Megapixels. For simplicity, let's assert that the picture only encodes 256 values per red, green and blue channels such that a 1x1 pixel image has 256^3 ...