A347560 a(n) is the number of solutions to Conv(b,n)=b where Conv(b,n) denotes the limit of b^^t (mod n) as t goes to infinity.

2, 2, 3, 2, 5, 4, 5, 4, 5, 3, 8, 3, 7, 8, 7, 4, 9, 3, 10, 8, 8, 5, 14, 6, 9, 4, 12, 6, 15, 9, 7, 10, 9, 10, 14, 4, 9, 10, 18, 7, 19, 5, 13, 14, 10, 3, 20, 10, 13, 12, 14, 7, 9, 12, 20, 10, 13, 7, 28, 9, 15, 21, 11, 17, 24, 10, 14, 13, 22, 15, 24, 7, 9, 17, 17, 20, 24, 10, 28

Offset

2,1

Comments

Writing n = m^(2k), a(n) >= 2^A001221(n) + m^k - 1.

Writing n = m^(2k+1), a(n) >= 2^A001221(n) + m^k - 1.

If n is in A101793, then a(n) = 3.

It appears that a(n) = 2 only for n = 2, 3, 5.

It appears that a(n) = 3 only for n = 4, 11, 13, 19 and for n in A101793.

It is not known whether there exist infinitely many numbers n satisfying a(n) = 3.

Links

Table of n, a(n) for n=2..80.

Wikipedia, Tetration

Index entries for sequences related to tetration

Example

For n = 100, pick b = 3.
3^^1 ==  3 (mod 100)
3^^2 == 27 (mod 100)
3^^3 == 87 (mod 100)
3^^4 == 87 (mod 100)
3^^5 == 87 (mod 100)
...
It can be proved that the sequence converges to 87, so Conv(3,100) = 87. Since b = 3 does not satisfy Conv(b,100) = b, this value is not counted in a(100).
For n = 7, pick b = 2.
2^^1 == 2 (mod 7)
2^^2 == 4 (mod 7)
2^^3 == 2 (mod 7)
2^^4 == 2 (mod 7)
2^^5 == 2 (mod 7)
...
It can be proved that the sequence converges to 2, so Conv(2,7) = 2. Thus, 2 is a solution for a(7). The other 3 solutions are 0, 1 and 4 giving a total of a(7) = 4 solutions.

Mathematica

Conv[b_, n_] :=
Which[
Mod[b, n]==0, Return[0],
Mod[b, n]==1, Return[1],
GCD[b, n]==1, Return[PowerMod[b, Conv[b, MultiplicativeOrder[b, n]], n]],
True, Return[PowerMod[b, EulerPhi[n]+Conv[b, EulerPhi[n]], n]]
]
a[n_] := Count[Table[Conv[b, n]==b, {b, 0, n-1}], True]

Prog

(PARI) conv(b, n) = {if (b % n == 0, return (0)); if (b % n == 1, return (1)); if (gcd(b, n)==1, return (lift(Mod(b, n)^conv(b, lift(znorder(Mod(b, n))))))); lift(Mod(b, n)^(eulerphi(n) + conv(b, eulerphi(n)))); }
a(n) = sum(b=0, n-1, conv(b, n) == b); \\ Michel Marcus, Sep 13 2021

Crossrefs

Cf. A347561, A343073, A000040, A101793, A183613, A001221.

Sequence in context: A029656 A121306 A073311 * A003974 A065769 A280264

Adjacent sequences: A347557 A347558 A347559 * A347561 A347562 A347563

Keyword

nonn

Author

Bernat Pagès Vives, Sep 06 2021

Status

approved