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

Author

Bernat Pagès Vives, Apr 04 2021

Keywords

• nonn

Comments

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

Examples

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

Links

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

Crossrefs

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

Programs

Mathematica

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
]

Formula

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

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