A245970 Tower of 2's modulo n.

0, 0, 1, 0, 1, 4, 2, 0, 7, 6, 9, 4, 3, 2, 1, 0, 1, 16, 5, 16, 16, 20, 6, 16, 11, 16, 7, 16, 25, 16, 2, 0, 31, 18, 16, 16, 9, 24, 16, 16, 18, 16, 4, 20, 16, 6, 17, 16, 23, 36, 1, 16, 28, 34, 31, 16, 43, 54, 48, 16, 22, 2, 16, 0, 16, 64, 17, 52, 52, 16, 3, 16

Offset

1,6

Comments

a(n) = (2^(2^(2^(2^(2^ ... ))))) mod n, provided enough 2's are in the tower so that adding more doesn't affect the value of a(n).

References

Ilan Vardi, "Computational Recreations in Mathematica," Addison-Wesley Publishing Co., Redwood City, CA, 1991, pages 226-229.

Links

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

Formula

a(n) = 2^(A000010(n)+a(A000010(n))) mod n.

a(n) = 0 if n is a power of 2.

a(n) = (2^2) mod n, if n < 5.

a(n) = (2^(2^2)) mod n, if n < 11.

a(n) = (2^(2^(2^2))) mod n, if n < 23.

a(n) = (2^(2^(2^(2^2)))) mod n, if n < 47.

a(n) = (2^^k) mod n, if n < A027763(k), where ^^ is Knuth's double-arrow notation.

From Robert Israel, Aug 19 2014: (Start)

If gcd(m,n) = 1, then a(m*n) is the unique k in [0,...,m*n-1] with

k == a(n) mod n and k == a(m) mod m.

a(n) = 1 if n is a Fermat number.

a(n) = 2^a(A000010(n)) mod n if n is not in A003401.

(End)

Example

a(5) = 1, as 2^x mod 5 is 1 for x being any even multiple of two and X = 2^(2^(2^...)) is an even multiple of two.

Maple

A:= proc(n)
     local phin, F, L, U;
     phin:= numtheory:-phi(n);
     if phin = 2^ilog2(phin) then
        F:= ifactors(n)[2];
        L:= map(t -> t[1]^t[2], F);
        U:= [seq(`if`(F[i][1]=2, 0, 1), i=1..nops(F))];
        chrem(U, L);
     else
        2 &^ A(phin) mod n
     fi
end proc:
seq(A(n), n=2 .. 100); # Robert Israel, Aug 19 2014

Mathematica

(* Import Mmca coding for "SuperPowerMod" and "LogStar" from text file in A133612 and then *) $RecursionLimit = 2^14; f[n_] := SuperPowerMod[2, 2^n, n] (* 2^^(2^n) (mod n), in Knuth's up-arrow notation *); Array[f, 72]
(* Second program: *)
a[n_] := Module[{phin, F, L, U},
   phin = EulerPhi[n];
   If[phin == 2^Floor@Log2[phin],
      F = FactorInteger[n];
      L = Power @@@ F;
      U = Table[If[F[[i, 1]] == 2, 0, 1], {i, 1, Length[F]}];
      ChineseRemainder[U, L],
      (2^a[phin])~Mod~n]];
Table[a[n], {n, 1, 100}] (* Jean-François Alcover, May 03 2023, after Robert Israel *)

Prog

(Sage)
def tower2mod(n):
    if ( n <= 22 ):
        return 65536%n
    else:
        ep = euler_phi(n)
        return power_mod(2, ep+tower2mod(ep), n)
(Haskell)
import Math.NumberTheory.Moduli (powerMod)
a245970 n = powerMod 2 (phi + a245970 phi) n
            where phi = a000010 n
-- Reinhard Zumkeller, Feb 01 2015
(PARI) a(n)=if(n<3, return(0)); my(e=valuation(n, 2), k=n>>e); lift(chinese(Mod(2, k)^a(eulerphi(k)), Mod(0, 2^e))) \\ Charles R Greathouse IV, Jul 29 2016

Crossrefs

Cf. A014221, A027763, A240162, A245971, A245972, A245973, A245974, A000010, A000079.

Sequence in context: A328819 A330578 A355289 * A197813 A200496 A058546

Adjacent sequences: A245967 A245968 A245969 * A245971 A245972 A245973

Keyword

nonn,easy,nice,look

Author

Wayne VanWeerthuizen, Aug 08 2014

Status

approved