OFFSET
1,4
COMMENTS
a(n) = (3^(3^(3^(3^(3^ ... ))))) mod n, provided sufficient 3's are in the tower such that adding more doesn't affect the value of a(n).
For values of n significantly less than Graham's Number, a(n) is equal to Graham's Number mod n.
LINKS
Wayne VanWeerthuizen, Table of n, a(n) for n = 1..10000
FORMULA
a(n) = 3^a(A000010(n)) mod n. - Robert Israel, Aug 01 2014
EXAMPLE
a(7) = 6. For any natural number X, 3^X is a positive odd multiple of 3. 3^(any positive odd multiple of three) mod 7 is always 6.
a(9) = 0, since 3^(3^X) is divisible by 9 for any natural number X. In our case, X itself is a tower of 3's.
a(100000000) = 64195387, giving the rightmost eight digits of Graham's Number.
From Robert Munafo, Apr 19 2020: (Start)
a(1) = 0, because 3 mod 1 = 0.
a(2) = 1, because 3^3 mod 2 = 1.
a(3) = 0, because 3^3^3 mod 3 = 0.
a(4) = 3, because 3^3^3^3 = 3^N for odd N, 3^N = 3 mod 4 for all odd N.
a(5) = 3^3^3^3^3 mod 5, and we should look at the sequence 3^N mod 5. We find that 3^N = 2 mod 5 whenever N = 3 mod 4. As just shown in the a(4) example, 3^3^3^3 = 3 mod 4. (End)
MAPLE
A:= proc(n) option remember; 3 &^ A(numtheory:-phi(n)) mod n end proc:
A(2):= 1;
seq(A(n), n=2..100); # Robert Israel, Aug 01 2014
MATHEMATICA
a[1] = 0; a[n_] := a[n] = PowerMod[3, a[EulerPhi[n]], n]; Array[a, 72] (* Jean-François Alcover, Feb 09 2018 *)
PROG
(Sage)
def A(n):
if ( n <= 10 ):
return 27%n
else:
return power_mod(3, A(euler_phi(n)), n)
(Haskell)
import Math.NumberTheory.Moduli (powerMod)
a245972 n = powerMod 3 (a245972 $ a000010 n) n
-- Reinhard Zumkeller, Feb 01 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Wayne VanWeerthuizen, Aug 01 2014
STATUS
approved