%I #53 Nov 11 2021 09:48:22
%S 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,
%T 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,
%U 28,9,15,21,11,17,24,10,14,13,22,15,24,7,9,17,17,20,24,10,28
%N 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.
%C Writing n = m^(2k), a(n) >= 2^A001221(n) + m^k - 1.
%C Writing n = m^(2k+1), a(n) >= 2^A001221(n) + m^k - 1.
%C If n is in A101793, then a(n) = 3.
%C It appears that a(n) = 2 only for n = 2, 3, 5.
%C It appears that a(n) = 3 only for n = 4, 11, 13, 19 and for n in A101793.
%C It is not known whether there exist infinitely many numbers n satisfying a(n) = 3.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Tetration">Tetration</a>
%H <a href="/index/Te#tetration">Index entries for sequences related to tetration</a>
%e For n = 100, pick b = 3.
%e 3^^1 == 3 (mod 100)
%e 3^^2 == 27 (mod 100)
%e 3^^3 == 87 (mod 100)
%e 3^^4 == 87 (mod 100)
%e 3^^5 == 87 (mod 100)
%e ...
%e 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).
%e For n = 7, pick b = 2.
%e 2^^1 == 2 (mod 7)
%e 2^^2 == 4 (mod 7)
%e 2^^3 == 2 (mod 7)
%e 2^^4 == 2 (mod 7)
%e 2^^5 == 2 (mod 7)
%e ...
%e 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.
%t Conv[b_,n_] :=
%t Which[
%t Mod[b,n]==0,Return[0],
%t Mod[b,n]==1,Return[1],
%t GCD[b,n]==1,Return[PowerMod[b,Conv[b,MultiplicativeOrder[b,n]],n]],
%t True,Return[PowerMod[b,EulerPhi[n]+Conv[b,EulerPhi[n]],n]]
%t ]
%t a[n_] := Count[Table[Conv[b,n]==b,{b,0,n-1}],True]
%o (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))));}
%o a(n) = sum(b=0, n-1, conv(b, n) == b); \\ _Michel Marcus_, Sep 13 2021
%Y Cf. A347561, A343073, A000040, A101793, A183613, A001221.
%K nonn
%O 2,1
%A _Bernat Pagès Vives_, Sep 06 2021
|