A240162 Tower of 3's modulo n.

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

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

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