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

Author

Wayne VanWeerthuizen, Aug 01 2014

Keywords

• nonn
• easy

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.

Examples

			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)
		

Links

• Wayne VanWeerthuizen, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A245970, A245971, A245972, A245973, A245974.

Cf. A000010, A000244.

Programs

Haskell

import Math.NumberTheory.Moduli (powerMod)
a245972 n = powerMod 3 (a245972 $ a000010 n) n
-- Reinhard Zumkeller, Feb 01 2015

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 *)

Sage

def A(n):
    if ( n <= 10 ):
        return 27%n
    else:
        return power_mod(3,A(euler_phi(n)),n)

Formula

a(n) = 3^a(A000010(n)) mod n. - Robert Israel, Aug 01 2014