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).

%I A343073 #40 Dec 13 2021 18:00:06
%S A343073 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,
%T A343073 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,
%U A343073 5,2,4,1,16,4,5,3,10,1,5
%N 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).
%C A343073 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.
%C A343073 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.
%C A343073 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.
%C A343073 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).
%H A343073 Bernat Pagès Vives, <a href="/A343073/b343073.txt">Table of n, a(n) for n = 2..500</a>
%H A343073 Wikipedia, <a href="http://en.wikipedia.org/wiki/Tetration">Tetration</a>
%H A343073 Wikipedia, <a href="http://en.wikipedia.org/wiki/Carmichael_function">Carmichael Function</a>
%F A343073 If n is a Fermat prime, a(n) = (n+1)/2.
%F A343073 If n is a power of 2, a(n) = 1.
%e A343073 For n = 5,
%e A343073 Setting b = 1, x = 1 gives 1^^1 == 1 (mod 5).
%e A343073 Setting b = 2, x = 3 gives 2^^3 == 2^8 == 1 (mod 5).
%e A343073 Setting b = 3 has no solutions, since 3^^x == 2 (mod 5) for all x > 1.
%e A343073 Setting b = 4, x = 2 gives 4^^2 == 1 (mod 5).
%e A343073 Thus there are 3 possible values of b, and that is the value of a(5).
%t A343073 Tetration[a_,b_,mod_]:=
%t A343073     Which[
%t A343073         Mod[a,mod]==0, 0,
%t A343073         b == 1,Mod[a,mod],
%t A343073         b==2,PowerMod[a,a,mod],
%t A343073         b==3&&a==2,Mod[16,mod],
%t A343073         True,PowerMod[a,Mod[(Tetration[a,b-1,EulerPhi[mod]]-Floor[Log[2,mod]]),EulerPhi[mod]]+Floor[Log[2,mod]],mod]]
%t A343073 TetraInv[n_,mod_,it_]:=
%t A343073     Which[
%t A343073         GCD[n,mod]!=1 ,0,
%t A343073         it==LambdaRoot[mod]+1,0,
%t A343073         Tetration[n,it,mod]==1,it,
%t A343073         True,TetraInv[n,mod,it+1]
%t A343073 ]
%t A343073 LambdaRoot[n_]:=Module[{counter,it},
%t A343073     counter = 0;
%t A343073     it = n;
%t A343073     While[it!=1,
%t A343073         it = CarmichaelLambda[it];
%t A343073         counter++;
%t A343073     ];
%t A343073     counter
%t A343073 ]
%t A343073 a[n_] := Module[{counter ,t},
%t A343073     counter = 0;
%t A343073     For[j=1,j<=n,j++,
%t A343073         t =TetraInv[j,n,1];
%t A343073         If[t!=0,counter++]
%t A343073     ];
%t A343073     counter
%t A343073 ]
%Y A343073 Cf. A000010, A019434, A239063, A317905, A321312.
%K A343073 nonn
%O A343073 2,2
%A A343073 _Bernat Pagès Vives_, Apr 04 2021