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

Author

Wayne VanWeerthuizen, Aug 08 2014

Keywords

• nonn
• easy
• nice
• look

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

Let b(i) = A014221(i) = (2^(2^(2^(2^(2^ ... ))))), with i 2's. Since gcd(b(i)+1, b(j)+1) = gcd(2^2^b(i-2)+1, 2^2^b(j-2)+1) = gcd(A000215(b(i-2)), A000215(b(j-2))) = 1 for 1 <= i < j, there is no n > 1 such that a(n) = n-1. Since b(i)-1 = 2^2^b(i-2)-1 divides b(j)-1 = 2^2^b(j-2)-1 for 1 <= i < j, a(n) = 1 if and only if n > 1 is a divisor of a number of the form b(i)-1, or if and only if n > 1 is a divisor of a Fermat number (A023394). - Jianing Song, May 16 2024

Examples

			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.
		

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

Crossrefs

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

Programs

Haskell

import Math.NumberTheory.Moduli (powerMod)
a245970 n = powerMod 2 (phi + a245970 phi) n
            where phi = a000010 n
-- Reinhard Zumkeller, Feb 01 2015

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

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

SageMath

def tower2mod(n):
    if ( n <= 22 ):
        return 65536%n
    else:
        ep = euler_phi(n)
        return power_mod(2,ep+tower2mod(ep),n)

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)