A377059 - OEIS

%I #37 Nov 15 2024 01:09:27

%S 0,0,0,2,2,2,2,2,6,4,2,2,6,6,4,4,8,6,6,4,6,10,2,2,20,4,18,6,14,4,6,8,

%T 10,16,12,6,18,18,12,4,20,6,14,10,12,22,2,4,42,20,8,6,26,18,20,6,18,

%U 28,2,4,10,30,6,16,12,10,22,16,22,12,10,6,12,18,20,18

%N a(n) is the smallest even r less than n-1 such that x^r = 1 (mod n) for the least x such that gcd(x,n)=1 for n >= 4 else 0.

%C This is essentially a part of Shor's algorithm.

%C While in Shor's algorithm the key step is to determine the period (or order) of x^r (mod n), based on finding the smallest even multiplicative order number r such that x^r = 1 (mod n) for a random x in order to factor a number n efficiently, in this algorithm we find such r for the least x coprime to n.

%C If this r is not even, it is discarded and the next number x is tried.

%C While in Shor's quantum algorithm the period search function runs in polynomial time, its classical counterpart runs in non-polynomial time.

%C Also a(n) is a divisor of the Euler's totient of n (A000010).

%H Robert Israel, <a href="/A377059/b377059.txt">Table of n, a(n) for n = 1..10000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Shor%27s_algorithm">Shor's algorithm</a>.

%F a(n) = gcd(a(n), A000010(n)) for n >= 3.

%p f:= proc(n) local x,r;

%p   for x from 2 to n do

%p     if igcd(x,n) <> 1 then next fi;

%p     r:= numtheory:-order(x,n);

%p     if r::even and r < n-1 then return r fi

%p   od;

%p   0

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Nov 14 2024

%o (Python)

%o from sympy import gcd

%o from sympy.ntheory.residue_ntheory import n_order

%o def a(n):

%o     for x in range(2, n):

%o         if gcd(x, n) == 1:

%o             r = n_order(x, n)

%o             if r & 1 == 0 and r < n-1:

%o                 return r

%o     return 0

%o print([a(n) for n in range(1, 77)])

%Y Cf. A000010, A378028, A378029.

%K nonn,look

%O 1,4

%A _Darío Clavijo_, Oct 14 2024