A321312 -id:A321312 - cp's OEIS frontend

A343073 a(n) is the number of integers 0 < b < n such that b^^x == 1 (mod n) has a solution; ^^ denotes the tetration operation (cf. A321312).

1, 2, 1, 3, 1, 2, 1, 2, 1, 3, 1, 6, 2, 5, 1, 9, 1, 5, 1, 3, 3, 2, 1, 3, 3, 2, 2, 5, 1, 3, 1, 5, 1, 8, 1, 9, 2, 5, 1, 8, 1, 6, 3, 5, 1, 2, 1, 4, 1, 17, 2, 5, 1, 5, 2, 3, 3, 3, 1, 7, 3, 3, 1, 15, 2, 5, 1, 5, 2, 4, 1, 16, 4, 5, 3, 10, 1, 5

Offset: 2

Bernat Pagès Vives, Apr 04 2021

nonn

If the same definition were used, but with b^x instead of b^^x, then a(n) would be A000010(n), the Euler Totient Function.
A019434 plays a special role for this sequence. a(A019434(n)) = (A019434(n)+1)/2, since all even numbers b satisfy the condition, and b=1 is the only odd number that satisfies it. This can be easily proved with the Fermat-Euler Theorem.
a(n) <= A000010(n), since gcd(b,n)=1 is a necessary condition. There is equality when n = 2 and n = 3. It is a conjecture that there are no more equality cases.
The sequence A239063 gives exactly the numbers n where a(n) = 1. This means that if b^^2 == 1 (mod n) has no solutions with 1 < b < n, then neither will b^^x == 1 (mod n).

			For n = 5,
Setting b = 1, x = 1 gives 1^^1 == 1 (mod 5).
Setting b = 2, x = 3 gives 2^^3 == 2^8 == 1 (mod 5).
Setting b = 3 has no solutions, since 3^^x == 2 (mod 5) for all x > 1.
Setting b = 4, x = 2 gives 4^^2 == 1 (mod 5).
Thus there are 3 possible values of b, and that is the value of a(5).

Bernat Pagès Vives, Table of n, a(n) for n = 2..500
Wikipedia, Tetration
Wikipedia, Carmichael Function

Cf. A000010, A019434, A239063, A317905, A321312.

Tetration[a_,b_,mod_]:=
    Which[
        Mod[a,mod]==0, 0,
        b == 1,Mod[a,mod],
        b==2,PowerMod[a,a,mod],
        b==3&&a==2,Mod[16,mod],
        True,PowerMod[a,Mod[(Tetration[a,b-1,EulerPhi[mod]]-Floor[Log[2,mod]]),EulerPhi[mod]]+Floor[Log[2,mod]],mod]]
TetraInv[n_,mod_,it_]:=
    Which[
        GCD[n,mod]!=1 ,0,
        it==LambdaRoot[mod]+1,0,
        Tetration[n,it,mod]==1,it,
        True,TetraInv[n,mod,it+1]
]
LambdaRoot[n_]:=Module[{counter,it},
    counter = 0;
    it = n;
    While[it!=1,
        it = CarmichaelLambda[it];
        counter++;
    ];
    counter
]
a[n_] := Module[{counter ,t},
    counter = 0;
    For[j=1,j<=n,j++,
        t =TetraInv[j,n,1];
        If[t!=0,counter++]
    ];
    counter
]

If n is a Fermat prime, a(n) = (n+1)/2.

If n is a power of 2, a(n) = 1.

A004231 Ackermann's sequence: n^^n := n^n^n^...^n (with n n's).

Original entry on oeis.org

1, 1, 4, 7625597484987

Offset: 0

Daniel Wild (wild(AT)edumath.u-strasbg.fr)

nonn

Using Knuth's arrow notation, this is n^^^2 (n-penta-2) or n^^n (n-tetra-n). - Andrew Robbins, Apr 16 2009
Comment from Trevor Green: The fourth term in this sequence has about as many digits - 8.07 * 10^153 - as the *square* of the number of protons in the universe.
We could prepend a(0) = 1 (since 0^^0 = 1, that is, the "empty power tower" gives the "empty product"). - Daniel Forgues, May 17 2013
The last 60 decimal digits of a(4) are ...67586985427238232605843019607448189676936860456095261392896. - Daniel Forgues, Jun 25 2016
From Daniel Forgues, Jul 06 2016: (Start)
a(4) has (the following number having 154 decimal digits)
  80723047260282253793826303970853990300713679217387 \
  43031867082828418414481568309149198911814701229483 \
  451981557574771156496457238535299087481244990261351117 decimal digits.
a(4) = 4^4^4^4 = 4^
  13407807929942597099574024998205846127479365820592 \
  39337772356144372176403007354697680187429816690342 \
  7690031858186486050853753882811946569946433649006084096,
the exponent of 4 having 155 decimal digits. (End)
The fractional part of 4^4^4*log[10](4) starts .373100157363599870..., so the first few digits of a(4) are 23610226714597313.... - Robert Israel, Jul 06 2016

John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 60.

W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen, Math. Ann. 99 (1928), 118-133, DOI:10.1007/BF01459088.
Eric Weisstein's World of Mathematics, Ackermann Number
Wikipedia, Knuth's up-arrow notation

Cf. A027747, A008868 (which mentions an older estimate for the same number), A266200.

Main diagonal of A321312.

b:= (n, i)-> `if`(i=0, 1, n^b(n, i-1)):
a:= n-> b(n, n):
seq(a(n), n=0..3);  # Alois P. Heinz, Aug 22 2017

a[n_] := If[n == 0, 1, Nest[n^#&, n, n-1]];
Table[a[n], {n, 0, 3}] (* Jean-François Alcover, Mar 19 2019 *)

A171882 Square array, read by antidiagonals, where T(n,k)=n^^k for n>=0, k>=0.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 1, 0, 1, 3, 4, 1, 1, 1, 4, 27, 16, 1, 0, 1, 5, 256, 7625597484987, 65536, 1, 1, 1, 6, 3125, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096

Offset: 0

Robert Munafo, Jan 21 2010

n^^k defined the right-associative way: n^^2=n^n, n^^3=n^(n^n), n^^4=n^(n^(n^n)), etc.
n^^0=1 by convention, so that n^^(k+1) = n^(n^^k) for all k>=0.
More terms on Munafo website.

			Array begins:
1,0,1,0,1,0,1,...
1,1,1,1,1,1,1,...
1,2,4,16,65536,...
1,3,27,7625597484987,...
1,4,256,...
1,5,3125,...
1,6,46656,...

Cf. A171881, A321312 (by downwards diagonals).
Rows n=0 to 4: A059841, A000012, A014221, A014222, A114561.
Columns k=0 to 3: A000012, A001477, A000312, A002488.
Main diagonal A004231 (Ackermann's sequence).

A364270 a(n) = 2^^n + 3^^n, where ^^ indicates tetration.

Original entry on oeis.org

2, 5, 31, 7625597485003

Offset: 0

Marco Ripà, Oct 20 2023

a(4) has 3638334640025 digits and is too large to show here.

a(n) is prime for n = 0, 1, 2, 3, but it is not known if a(4) is prime.

			For n = 3, a(3) = 2^2^2 + 3^3^3 = 2^4 + 3^27 = 7625597485003.

Cf. A004249, A014221, A014222, A321312.

nmax=3; NestList[2^#&, 1,nmax]+NestList[3^#&,1,nmax] (* Stefano Spezia, Oct 22 2023 *)

a(n) = A014221(n) + A014222(n+1).

a(n) = A321312(2,n) + A321312(3,n).

cp's OEIS Frontend

A343073 a(n) is the number of integers 0 < b < n such that b^^x == 1 (mod n) has a solution; ^^ denotes the tetration operation (cf. A321312).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A004231 Ackermann's sequence: n^^n := n^n^n^...^n (with n n's).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

A171882 Square array, read by antidiagonals, where T(n,k)=n^^k for n>=0, k>=0.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A364270 a(n) = 2^^n + 3^^n, where ^^ indicates tetration.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula