

A240162


Tower of 3's modulo n.


10



0, 1, 0, 3, 2, 3, 6, 3, 0, 7, 9, 3, 1, 13, 12, 11, 7, 9, 18, 7, 6, 9, 18, 3, 12, 1, 0, 27, 10, 27, 23, 27, 9, 7, 27, 27, 36, 37, 27, 27, 27, 27, 2, 31, 27, 41, 6, 27, 6, 37, 24, 27, 50, 27, 42, 27, 18, 39, 49, 27, 52, 23, 27, 59, 27, 9, 52, 7, 18, 27, 49, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)



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] (* JeanFranç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

Cf. A245970, A245971, A245972, A245973, A245974.
Cf. A000010, A000244.
Sequence in context: A256185 A343368 A021313 * A113128 A220075 A266593
Adjacent sequences: A240159 A240160 A240161 * A240163 A240164 A240165


KEYWORD

nonn,easy


AUTHOR

Wayne VanWeerthuizen, Aug 01 2014


STATUS

approved



