cp's OEIS Frontend

A245970 Tower of 2's modulo n.

%I A245970 #78 May 31 2024 14:25:49
%S A245970 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,
%T A245970 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,
%U A245970 31,16,43,54,48,16,22,2,16,0,16,64,17,52,52,16,3,16
%N A245970 Tower of 2's modulo n.
%C A245970 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).
%C A245970 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
%D A245970 Ilan Vardi, "Computational Recreations in Mathematica," Addison-Wesley Publishing Co., Redwood City, CA, 1991, pages 226-229.
%H A245970 Wayne VanWeerthuizen, <a href="/A245970/b245970.txt">Table of n, a(n) for n = 1..10000</a>
%F A245970 a(n) = 2^(A000010(n)+a(A000010(n))) mod n.
%F A245970 a(n) = 0 if n is a power of 2.
%F A245970 a(n) = (2^2) mod n, if n < 5.
%F A245970 a(n) = (2^(2^2)) mod n, if n < 11.
%F A245970 a(n) = (2^(2^(2^2))) mod n, if n < 23.
%F A245970 a(n) = (2^(2^(2^(2^2)))) mod n, if n < 47.
%F A245970 a(n) = (2^^k) mod n, if n < A027763(k), where ^^ is Knuth's double-arrow notation.
%F A245970 From _Robert Israel_, Aug 19 2014: (Start)
%F A245970 If gcd(m,n) = 1, then a(m*n) is the unique k in [0,...,m*n-1] with
%F A245970 k == a(n) mod n and k == a(m) mod m.
%F A245970 a(n) = 1 if n is a Fermat number.
%F A245970 a(n) = 2^a(A000010(n)) mod n if n is not in A003401.
%F A245970 (End)
%e A245970 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.
%p A245970 A:= proc(n)
%p A245970      local phin,F,L,U;
%p A245970      phin:= numtheory:-phi(n);
%p A245970      if phin = 2^ilog2(phin) then
%p A245970         F:= ifactors(n)[2];
%p A245970         L:= map(t -> t[1]^t[2],F);
%p A245970         U:= [seq(`if`(F[i][1]=2,0,1),i=1..nops(F))];
%p A245970         chrem(U,L);
%p A245970      else
%p A245970         2 &^ A(phin) mod n
%p A245970      fi
%p A245970 end proc:
%p A245970 seq(A(n), n=2 .. 100); # _Robert Israel_, Aug 19 2014
%t A245970 (* 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]
%t A245970 (* Second program: *)
%t A245970 a[n_] := Module[{phin, F, L, U},
%t A245970    phin = EulerPhi[n];
%t A245970    If[phin == 2^Floor@Log2[phin],
%t A245970       F = FactorInteger[n];
%t A245970       L = Power @@@ F;
%t A245970       U = Table[If[F[[i, 1]] == 2, 0, 1], {i, 1, Length[F]}];
%t A245970       ChineseRemainder[U, L],
%t A245970       (2^a[phin])~Mod~n]];
%t A245970 Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, May 03 2023, after _Robert Israel_ *)
%o A245970 (SageMath)
%o A245970 def tower2mod(n):
%o A245970     if ( n <= 22 ):
%o A245970         return 65536%n
%o A245970     else:
%o A245970         ep = euler_phi(n)
%o A245970         return power_mod(2,ep+tower2mod(ep),n)
%o A245970 (Haskell)
%o A245970 import Math.NumberTheory.Moduli (powerMod)
%o A245970 a245970 n = powerMod 2 (phi + a245970 phi) n
%o A245970             where phi = a000010 n
%o A245970 -- _Reinhard Zumkeller_, Feb 01 2015
%o A245970 (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
%Y A245970 Cf. A014221, A027763, A240162, A245971, A245972, A245973, A245974, A000010, A000079.
%K A245970 nonn,easy,nice,look
%O A245970 1,6
%A A245970 _Wayne VanWeerthuizen_, Aug 08 2014