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.

0
votes
1answer
89 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
3answers
60 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
210 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 ...
3
votes
1answer
93 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
717 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
102 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
127 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
177 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
51 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
99 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
120 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
88 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
155 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 $...
3
votes
1answer
137 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
407 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{...
2
votes
3answers
149 views

$2014^{2014^{2014}}\bmod2011$ [closed]

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?
2
votes
2answers
118 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 ...
2
votes
1answer
234 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
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
128 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
133 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
129 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 ...
10
votes
1answer
223 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
199 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
608 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
1k 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
604 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
234 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
73 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
109 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
151 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
152 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
152 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
243 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
192 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
81 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
197 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
58 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
395 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
90 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
84 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 ...
12
votes
1answer
684 views

The first few values of Rayo's function?

Rayo's function defined in English: "$\operatorname{Rayo}(n)$ is the smallest positive integer bigger than any finite positive integer named by an expression in the language of first order set theory ...
0
votes
1answer
96 views

Factorial and exponential relationships (Problem)

I have faced some problems like: $x,A\in N$ $32!=A*10^x \Rightarrow Max(x)=?\\ 26!=A*3^x \Rightarrow Max(x)=?$ My question will be stated after solving the first one as following: Since $10=2*5$ ...
4
votes
2answers
106 views

How are the first digits of these numbers calculated?!

According to googology.wikia, we have the following: $$5^{4^{3^{2^{1}}}}=620606987866087447074832055728467\ldots$$ $$6^{5^{4^{3^{2^{1}}}}}=110356022591769663217914533447534\ldots$$ How are the ...
2
votes
1answer
139 views

Does domination of exponential-factorial by tetration generalize to higher-order hyperoperations?

Let $\star$ be any operation in the sequence of hyperoperations $(\text{Succ},+,\times,\uparrow,\uparrow\uparrow,\ldots)$, and consider the $\star$-factorial function defined as follows on the ...
3
votes
1answer
237 views

Does there exist a computable function that grows faster than fast growing hierarchy?

Does there exist a computable function that grows faster than fast growing hierarchy for every computable ordinal $\alpha$? Or does it follow that fast growing hierarchy grows as fast as any ...
2
votes
1answer
368 views

Magnitude of n-th factorial

In connection with a riddle on The Riddler, I would like to know how to evaluate even crudely the order of magnitude of an iterated factorial like $$(\ldots(9\underbrace{!)!\ldots)!}_{n\text{ ...