cp's OEIS Frontend

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.

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