Discover Top Posts Tagged with #functions

Info Dump on Graham's Number

This is by far my favourite so enjoy :D

(update: this is the info dump on hypercube)

Graham's number is mind-bendingly large you literally can’t write it down in the observable universe. Not because your hand would get tired (sure it will), but because even if you turned every atom in the universe into ink and paper, you wouldn’t have enough to express it in normal notation.

It is born from Ramsey theory, a field where mathematicians say: “If you have enough stuff, patterns happen whether you like it or not.” Ronald Graham, legendary mathematician/juggler, needed an upper bound for a problem about colouring edges of a hypercube (I'll info dump on this sooner or later but not now). He didn’t just pick big numbers. He went full “hold my beer” and gave the world something too large.

Let me break it down for you:

To even talk about Graham’s number, we need a special notation called Knuth up-arrow notation:

3↑3 = 3³ = 27 3↑↑3 = 3^(3^3) = 3^27 = 7,625,597,484,987 3↑↑↑3 is already incomprehensibly big.

Graham’s number starts with something even worse:

G₁ = 3↑↑↑↑3 G₂ = 3↑^(G₁) 3 (with that many arrows) ... G₆₄ = Graham’s number

Each step uses the previous beast to decide how many arrows the next operation has. That happens 64 times. Yes, that’s 64 recursive levels of arrow hell :D

So why do people even care about a number so big we can't write?

Because it’s in a real proof. I'm not joking, and I will never wish it to be. Guinness Book of World Records listed it as the largest number ever used in a serious proof in 1980. Mathematicians later found smaller numbers to solve the same problem, but Graham’s number stayed famous because it’s basically math’s middle finger to practicality (and efficiency but at least it's cool).

Can we visualize It? Nope. Even the number of digits in Graham’s number is so huge it can’t be represented in the physical universe. Like, if you converted every particle in existence into an atom-sized digit, you’d still fall short. (There are 10⁸⁰ atoms in this observable universe by the way)

Thanks to modular arithmetic, we actually know that the last few digits of Graham’s number are 7262464195387. Here is the modular arithmetic breakdown (if anyone was wondering).

The powers of 3 repeat last digits every 4 steps:

3¹ → 3 3² → 9 3³ → 7 3⁴ → 1 → cycle repeats. Cycle: (3 → 9 → 7 → 1).

Now, the last digit of 3ⁿ depends on n mod 4:

n ≡ 1 (mod 4) → last digit = 3 n ≡ 2 (mod 4) → last digit = 9 n ≡ 3 (mod 4) → last digit = 7 n ≡ 0 (mod 4) → last digit = 1

Graham’s number = 3^(huge exponent)

We don’t need “huge exponent.” We just need huge exponent mod 4. And that “huge exponent” is itself a power tower of 3’s.

Powers of 3 mod 4 are simple: 3 ≡ -1 (mod 4)

(-1)^odd = -1 → 3 (mod 4) (-1)^even = 1 → 1 (mod 4)

Tracing the parity of the tower shows it’s odd, therefore:

exponent ≡ 3 (mod 4)

QED. The ultimate incomprehensible number ends in 7.

But how did mathematicians figure out 7262464195387 these?

It's not actually rocket science. We want last 13 digits which mathematically means G mod 10¹³ (i.e., what remains when you divide by 10¹³).

We are going to use these mates for this:

Modular arithmetic: we only care about certain digits, not the whole number Euler’s Totient Theorem and Carmichael Function: they will help with giant exponents. Pattern cycles of powers of 3 for mod 2^n and mod 5^n separately (because 10¹³ = 2¹³ × 5¹³). Chinese Remainder Theorem (CRT): for combining results mod 2¹³ and mod 5¹³ back into one result

We will first split 10¹³ into factors: 2¹³ and 5¹³.

Now we can work out last 13 digits separately in base-2 and base-5 worlds.

2¹³ = 8192.

For powers of 3 mod 2¹³, there’s a repeating cycle because 3 and 2 are coprime.

The cycle length = Carmichael function λ(2¹³) = 2¹¹ = 2048

So exponent mod 2048 decides result mod 2¹³.

5¹³ = 1220703125.

The cycle length = 4 × 5¹² = 4 × 244140625 = 976562500

So exponent mod 976562500 decides result mod 5¹³.

The “exponent” of the top-level 3 is itself a tower of 3’s (from all those recursive arrows). Now reduce that tower mod the cycle lengths from above, which collapses ridiculously fast because patterns repeat at small moduli. After multiple reductions, the exponent collapses into manageable values.

Now we know:

Result mod 2¹³ = some number A. Result mod 5¹³ = some number B.

Chinese Remainder Theorem gives one number mod 10¹³ which is unique because 2¹³ and 5¹³ are coprime.

After doing all that, we can know that

the last 13 digits = 7262464195387

The beauty is: we don’t need to know the full value of Graham’s number; just its exponent mod relatively small cycles is enough. The computation is heavy but finite and actually doable on a computer (unlike writing the whole number).

#functions

Trending Tags

Recently Viewed Tags

#functions