login
A245970
Tower of 2's modulo n.
14
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).
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) = 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
(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
KEYWORD
nonn,easy,nice,look
AUTHOR
STATUS
approved