|
%I #55 Sep 01 2023 14:11:50
%S 1,1,1,1,1,5,1,1,1,7,1,1,11,9,1,1,1,11,13,1,1,19,1,1,1,15,1,19,1,17,
%T 23,1,29,19,1,1,25,31,1,29,1,23,26,1,1,41,1,1,35,27,1,1,34,43,37,1,1,
%U 49,1,1,55,33,51,43,1,35,47,41,1,55,1,1,49,39,43,53
%N a(n) is the largest k <= n-2 such that k^2 == 1 (mod n).
%C It appears that the terms > 1 comprise the sequence A277777.
%C What is the asymptotic behavior of this sequence? Numerically, it seems like sum_{3 <= n <= x} a(n) is of the order x log x or so. - _Charles R Greathouse IV_, Oct 27 2022
%H Charles R Greathouse IV, <a href="/A358016/b358016.txt">Table of n, a(n) for n = 3..10000</a>
%H Project Euler, <a href="https://projecteuler.net/problem=451">Problem 451. Modular inverses</a>, where a(n) = I(n).
%t lkn[n_]:=Module[{k=n-2},While[PowerMod[k,2,n]!=1,k--];k]; Array[lkn,80,3] (* _Harvey P. Dale_, Sep 01 2023 *)
%o (Python)
%o def a(n):
%o for k in range(n - 2, 0, -1):
%o if pow(k,2,n) == 1: return k
%o (Python)
%o from sympy.ntheory import sqrt_mod_iter
%o def A358016(n): return max(filter(lambda k: k<=n-2,sqrt_mod_iter(1,n))) # _Chai Wah Wu_, Oct 26 2022
%o (PARI) a(n) = forstep(k=n-2, 1, -1, if ((gcd(k, n) == 1) && (lift(Mod(1,n)/k) == k), return(k));); \\ _Michel Marcus_, Oct 25 2022
%o (PARI) rootsOfUnity(p,e,pe=p^e)=if(p>2, return(Mod([1,-1],pe))); if(e==1, return(Mod([1],2))); if(e==2, return(Mod([1,3],4))); Mod([1,pe/2-1,pe/2+1,-1],pe)
%o a(n,f=factor(n))=my(v=apply(x->rootsOfUnity(x[1],x[2]),Col(f)),r,t); forvec(u=vector(#v,i,[1,#v[i]]), t=lift(chinese(vector(#u,i,v[i][u[i]]))); if(t>r && t<n-1, r=t)); r \\ _Charles R Greathouse IV_, Oct 26 2022
%Y Cf. A228179, A277777, A033948, A060594.
%K nonn
%O 3,6
%A _Darío Clavijo_, Oct 24 2022
|
