cp's OEIS Frontend

A240162 Tower of 3's modulo n.

%I A240162 #60 May 16 2020 03:34:52
%S A240162 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,
%T A240162 23,27,9,7,27,27,36,37,27,27,27,27,2,31,27,41,6,27,6,37,24,27,50,27,
%U A240162 42,27,18,39,49,27,52,23,27,59,27,9,52,7,18,27,49,27
%N A240162 Tower of 3's modulo n.
%C A240162 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).
%C A240162 For values of n significantly less than Graham's Number, a(n) is equal to Graham's Number mod n.
%H A240162 Wayne VanWeerthuizen, <a href="/A240162/b240162.txt">Table of n, a(n) for n = 1..10000</a>
%F A240162 a(n) = 3^a(A000010(n)) mod n. - _Robert Israel_, Aug 01 2014
%e A240162 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.
%e A240162 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.
%e A240162 a(100000000) = 64195387, giving the rightmost eight digits of Graham's Number.
%e A240162 From _Robert Munafo_, Apr 19 2020: (Start)
%e A240162 a(1) = 0, because 3 mod 1 = 0.
%e A240162 a(2) = 1, because 3^3 mod 2 = 1.
%e A240162 a(3) = 0, because 3^3^3 mod 3 = 0.
%e A240162 a(4) = 3, because 3^3^3^3 = 3^N for odd N, 3^N = 3 mod 4 for all odd N.
%e A240162 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)
%p A240162 A:= proc(n) option remember; 3 &^ A(numtheory:-phi(n)) mod n end proc:
%p A240162 A(2):= 1;
%p A240162 seq(A(n), n=2..100); # _Robert Israel_, Aug 01 2014
%t A240162 a[1] = 0; a[n_] := a[n] = PowerMod[3, a[EulerPhi[n]], n]; Array[a, 72] (* _Jean-François Alcover_, Feb 09 2018 *)
%o A240162 (Sage)
%o A240162 def A(n):
%o A240162     if ( n <= 10 ):
%o A240162         return 27%n
%o A240162     else:
%o A240162         return power_mod(3,A(euler_phi(n)),n)
%o A240162 (Haskell)
%o A240162 import Math.NumberTheory.Moduli (powerMod)
%o A240162 a245972 n = powerMod 3 (a245972 $ a000010 n) n
%o A240162 -- _Reinhard Zumkeller_, Feb 01 2015
%Y A240162 Cf. A245970, A245971, A245972, A245973, A245974.
%Y A240162 Cf. A000010, A000244.
%K A240162 nonn,easy
%O A240162 1,4
%A A240162 _Wayne VanWeerthuizen_, Aug 01 2014