A357906 a(n) = log_2(A073103(n)).

0, 0, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 2, 1, 3, 3, 2, 1, 1, 3, 2, 1, 1, 3, 2, 2, 1, 2, 2, 3, 1, 3, 2, 2, 3, 2, 2, 1, 3, 4, 2, 2, 1, 2, 3, 1, 1, 4, 1, 2, 3, 3, 2, 1, 3, 3, 2, 2, 1, 4, 2, 1, 2, 3, 4, 2, 1, 3, 2, 3, 1, 3, 2, 2, 3, 2, 2, 3, 1, 5, 1, 2, 1, 3, 4, 1, 3, 3, 2, 3, 3, 2, 2, 1, 3, 4, 2, 1, 2, 3

Offset: 1

Author

Jianing Song, Oct 19 2022

Keywords

• nonn
• easy

Examples

			a(16) = 3 since x^4 == 1 (mod 16) has 2^3 = 8 solutions.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..10000

Crossrefs

Cf. A073103, A072273, A357905.

Programs

Mathematica

f[p_, e_] := If[Mod[p, 4] == 1, 2, 1]; f[2, e_] := Switch[e, 1, 0, 2, 1, 3, 2, , 3]; a[1] = 0; a[n] := Plus @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Oct 05 2023 *)

PARI

a(n)=my(f=factor(n)); sum(i=1, #f~, if(f[i, 1]==2, min(f[i, 2]-1, 3), if(f[i, 1]%4==1, 2, 1))) \\ after Charles R Greathouse IV's program for A073103

Formula

Additive with a(2) = 0, a(4) = 1, a(8) = 2, a(2^e) = 3, e >= 4; a(p^e) = 2 for p == 1 (mod 4), 1 for p == 3 (mod 4).