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).
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
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) = 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.
(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
(SageMath)
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
KEYWORD
AUTHOR
Wayne VanWeerthuizen, Aug 08 2014
STATUS
approved