A027763 -id:A027763 - cp's OEIS frontend

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

Wayne VanWeerthuizen, Aug 08 2014

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

			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.

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

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

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

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

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

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

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

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

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)

A246491 Smallest k such that 3^^n is not congruent to 3^^(n-1) mod k, where 3^^n denotes the power tower 3^3^...^3 (in which 3 appears n times).

Original entry on oeis.org

3, 5, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14920303, 36449279, 377982107

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

This sequence is a member of an interesting class of sequences defined by the rule, "Smallest k such that b^^n is not congruent to b^^(n-1) mod k, where b^^n denotes the power tower b^b^...^b (in which b appears n times)," for some constant b. Different choices for b, with b>=2, determine a sequence of this class. The first sequence of this class is A027763, which uses b=2. This is the sequence for b=3. Adjacent sequences follow for b=4 through b=9.
Sequences of this class can contain only terms that are either prime numbers or powers of primes (A000961).
Powers of three (A000244) are commonplace as terms in sequences of this class, occurring significantly more often than powers of other primes.
For successive values of b, the sequence of first terms of all sequences of this class is A007978.
It appears that the sequence for b=x contains the term y, if and only if the sequence for b=x+A003418(y) also contains the term y, where A003418(y) is the least common multiple of all the integers from 1 to y. Can this be proved?
Sequences of this class generally share many terms with other sequences of this class, although each appears to be unique. These individual sequences are very similar to each other, so much so that among the first 7000 of them, only 120 distinct values less than 50000 occur (compare that to the 5217 available primes or powers of primes that are less than 50000.)
Sequences of this class tend to share many terms with A056637, the least prime of class n-.

			(3^^3) mod 11 = 9, (3^^2) mod 11 = 5. 11 is the least whole number for which this is true, thus a(3)=11.

Wayne VanWeerthuizen, Sage/Cython source code for all sequences of this class.
Wayne VanWeerthuizen, Initial terms of sequences of this class for b=2..10001

Cf. A027763, A246492, A246493, A246494, A246495, A246496, A246497

Large overlap with A056637.

A246496 Smallest k such that 8^^n is not congruent to 8^^(n-1) mod k, where 8^^n denotes the power tower 8^8^...^8 (in which 8 appears n times).

Original entry on oeis.org

2, 3, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14920303

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

Cf. A027763, A056637, A246491 - A246497

Large overlap with A056637.

A246497 Smallest k such that 9^^n is not congruent to 9^^(n-1) mod k, where 9^^n denotes the power tower 9^9^...^9 (in which 9 appears n times).

Original entry on oeis.org

3, 7, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 14619833, 36449279, 377982107, 1432349099

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

This particular sequence shares all known terms with A082449. they might be identical.

Cf. A082449, A027763, A246491, A246492, A246493, A246494, A246495, A246496.

A185816 Number of iterations of lambda(n) needed to reach 1.

Original entry on oeis.org

0, 1, 2, 2, 3, 2, 3, 2, 3, 3, 4, 2, 3, 3, 3, 3, 4, 3, 4, 3, 3, 4, 5, 2, 4, 3, 4, 3, 4, 3, 4, 3, 4, 4, 3, 3, 4, 4, 3, 3, 4, 3, 4, 4, 3, 5, 6, 3, 4, 4, 4, 3, 4, 4, 4, 3, 4, 4, 5, 3, 4, 4, 3, 4, 3, 4, 5, 4, 5, 3, 4, 3, 4, 4, 4, 4, 4, 3, 4, 3, 5, 4, 5, 3, 4, 4, 4

Offset: 1

Michel Lagneau, Feb 05 2011

nonn

lambda(n) is the Carmichael lambda function, A002322.

a(n) = (length of row n in table A246700) - 1. - Reinhard Zumkeller, Sep 02 2014

			If n = 23 the trajectory is 23, 22, 10, 4, 2, 1. Its length is 6, thus a(23) = 5.

T. D. Noe, Table of n, a(n) for n = 1..10000
Paul Erdős, Andrew Granville, Carl Pomerance, and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204.
Paul Erdős, Andrew Granville, Carl Pomerance, and Claudia Spiro, On the normal behavior of the iterates of some arithmetic functions, Analytic number theory, Birkhäuser Boston, 1990, pp. 165-204. [Annotated copy with A-numbers]
Paul Erdős, A. Granville, C. Pomerance, and C. Spiro, On the Normal Behavior of the Iterates of some Arithmetic Functions, in Analytic number theory (Allerton Park, IL, 1989), Progr. Math., 85 Birkhäuser Boston, Boston, MA, (1990), 165-204.
Nick Harland, The iterated Carmichael lambda function, arXiv:1111.3667v1 [math.NT], Nov 15, 2011.
Nick Harland, The number of iterates of the Carmichael lambda function required to reach 1, arXiv:1203.4791 [math.NT], Mar 21, 2012.

Cf. A002322, A036459, A003434.

Cf. A027763, A173927, A246700.

a185816 n = if n == 1 then 0 else a185816 (a002322 n) + 1
-- Reinhard Zumkeller, Sep 02 2014

a:= n-> `if`(n=1, 0, 1+a(numtheory[lambda](n))):
seq(a(n), n=1..100);  # Alois P. Heinz, Apr 27 2019

f[n_] := Length[ NestWhileList[ CarmichaelLambda, n, Unequal, 2]] - 2; Table[f[n], {n, 1, 120}]

For n > 1: a(n) = a(A002322(n)) + 1. - Reinhard Zumkeller, Sep 02 2014

A246492 Smallest k such that 4^^n is not congruent to 4^^(n-1) mod k, where 4^^n denotes the power tower 4^4^...^4 (in which 4 appears n times).

Original entry on oeis.org

2, 5, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 4782969, 14348907

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

Cf. A027763, A246491, A246493, A246494, A246495, A246496, A246497

A246493 Smallest k such that 5^^n is not congruent to 5^^(n-1) mod k, where 5^^n denotes the power tower 5^5^...^5 (in which 5 appears n times).

Original entry on oeis.org

3, 7, 19, 47, 243, 719, 1439, 2879, 19683, 59049, 177147, 531441, 1594323, 4782969

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

Cf. A027763, A246491, A246492, A246494, A246495, A246496, A246497

A246494 Smallest k such that 6^^n is not congruent to 6^^(n-1) mod k, where 6^^n denotes the power tower 6^6^...^6 (in which 6 appears n times).

Original entry on oeis.org

2, 4, 13, 47, 107, 643, 1439, 2879, 34549, 138197, 858239, 2029439, 36449279

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

Cf. A027763, A246491, A246492, A246493, A246495, A246496, A246497

A246495 Smallest k such that 7^^n is not congruent to 7^^(n-1) mod k, where 7^^n denotes the power tower 7^7^...^7 (in which 7 appears n times).

Original entry on oeis.org

4, 5, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 1266767, 4782969, 14348907

Offset: 1

Wayne VanWeerthuizen, Aug 27 2014

For general remarks regarding sequences of this type, see A246491.

Cf. A027763, A246491, A246493, A246494, A246496, A246497

Large overlap with A246492.

A173927 Smallest integer k such that the number of iterations of Carmichael lambda function (A002322) needed to reach 1 starting at k (k is counted) is n.

Original entry on oeis.org

1, 2, 3, 5, 11, 23, 47, 283, 719, 1439, 2879, 34549, 138197, 531441, 1594323, 4782969, 14348907, 43046721, 86093443, 258280327, 688747547

Offset: 1

Michel Lagneau, Nov 26 2010

Smallest number k such that the trajectory of k under iteration of Carmichael lambda function contains exactly n distinct numbers (including k and the fixed point).
The first 13 terms are 1 or a prime. The next five terms are powers of 3. Then another prime. What explains this behavior? - T. D. Noe, Mar 23 2012
A185816(a(n)) = n - 1. - Reinhard Zumkeller, Sep 02 2014
If a(n) (n > 1) is either a prime or a power of 3, then a(n) is also the smallest integer k such that the number of iterations of Euler's totient function (A000010) needed to reach 1 starting at k (k is counted) is n. - Jianing Song, Jul 10 2019

			for n=5, a(5)=11 gives a chain of length 5 because the trajectory is 11 -> 10 -> 4 -> 2 -> 1.

Nick Harland, The number of iterates of the Carmichael lambda function required to reach 1, arXiv:1203.4791v1 [math.NT], Mar 21 2012.

Cf. A002322, A027763, A056637.

Cf. A185816 (number of iterations of Carmichael lambda function needed to reach 1), A003434 (number of iterations of Euler's totient function needed to reach 1).

import Data.List (elemIndex); import Data.Maybe (fromJust)
a173927 = (+ 1) . fromJust . (`elemIndex` map (+ 1) a185816_list)
-- Reinhard Zumkeller, Sep 02 2014

f[n_] := Length@ NestWhileList[ CarmichaelLambda, n, Unequal, 2] - 1; t = Table[0, {30}]; k = 1; While[k < 2100000001, a = f@ k; If[ t[[a]] == 0, t[[a]] = k; Print[a, " = ", k]]; k++] (* slightly modified by Robert G. Wilson v, Sep 01 2014 *)

a(20)-a(21) from Robert G. Wilson v, Sep 01 2014

cp's OEIS Frontend

A245970 Tower of 2's modulo n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

SageMath

Formula

A246491 Smallest k such that 3^^n is not congruent to 3^^(n-1) mod k, where 3^^n denotes the power tower 3^3^...^3 (in which 3 appears n times).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A246496 Smallest k such that 8^^n is not congruent to 8^^(n-1) mod k, where 8^^n denotes the power tower 8^8^...^8 (in which 8 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A246497 Smallest k such that 9^^n is not congruent to 9^^(n-1) mod k, where 9^^n denotes the power tower 9^9^...^9 (in which 9 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A185816 Number of iterations of lambda(n) needed to reach 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

Formula

A246492 Smallest k such that 4^^n is not congruent to 4^^(n-1) mod k, where 4^^n denotes the power tower 4^4^...^4 (in which 4 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A246493 Smallest k such that 5^^n is not congruent to 5^^(n-1) mod k, where 5^^n denotes the power tower 5^5^...^5 (in which 5 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A246494 Smallest k such that 6^^n is not congruent to 6^^(n-1) mod k, where 6^^n denotes the power tower 6^6^...^6 (in which 6 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A246495 Smallest k such that 7^^n is not congruent to 7^^(n-1) mod k, where 7^^n denotes the power tower 7^7^...^7 (in which 7 appears n times).

Views

Author

Keywords

Comments

Crossrefs

A173927 Smallest integer k such that the number of iterations of Carmichael lambda function (A002322) needed to reach 1 starting at k (k is counted) is n.

Views

Author

Keywords

Comments

Examples