A378028 -id:A378028 - cp's OEIS frontend

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

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, 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, 28, 2, 4, 10, 30, 6, 16, 12, 10, 22, 16, 22, 12, 10, 6, 12, 18, 20, 18

Offset: 1

Darío Clavijo, Oct 14 2024

This is essentially a part of Shor's algorithm.
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.
If this r is not even, it is discarded and the next number x is tried.
While in Shor's quantum algorithm the period search function runs in polynomial time, its classical counterpart runs in non-polynomial time.
Also a(n) is a divisor of the Euler's totient of n (A000010).

Robert Israel, Table of n, a(n) for n = 1..10000
Wikipedia, Shor's algorithm.

Cf. A000010, A378028, A378029.

f:= proc(n) local x,r;
  for x from 2 to n do
    if igcd(x,n) <> 1 then next fi;
    r:= numtheory:-order(x,n);
    if r::even and r < n-1 then return r fi
  od;
  0
end proc:
map(f, [$1..100]); # Robert Israel, Nov 14 2024

from sympy import gcd
from sympy.ntheory.residue_ntheory import n_order
def a(n):
    for x in range(2, n):
        if gcd(x, n) == 1:
            r = n_order(x, n)
            if r & 1 == 0 and r < n-1:
                return r
    return 0
print([a(n) for n in range(1, 77)])

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

A378029 Record values in A377059.

Original entry on oeis.org

0, 2, 6, 8, 10, 20, 22, 42, 54, 58, 110, 156, 162, 166, 168, 294, 342, 506, 812, 930, 1210, 1332, 1458, 2028, 2162, 2756, 3422, 3660, 4422, 4970, 6162, 6498, 6806, 7832, 10100, 11342, 11638, 13310, 16002, 17030, 19182, 22052, 23548, 26406, 27722, 28830, 29756, 31862, 32580, 38612, 39402, 44310, 49506

Offset: 1

Robert Israel, Nov 14 2024

nonn

Numbers k such that for some j, A377059(j) = k and A377059(i) < k for all i < j.

			a(3) = 6 because A377059(9) = 6 and A377059(k) < 6 for all k < 9.

Cf. A377059, A378028.

f:= proc(n) local x, r;
  for x from 2 to n do
    if igcd(x, n) <> 1 then next fi;
    r:= numtheory:-order(x, n);
    if r::even and r < n-1 then return r fi
  od;
  0
end proc:
R:= 1: m:= 0: count:= 0:
for k from 2 while count < 100 do
v:= f(k);
if v > m then m:= v; R:= R, v; count:= count+1 fi;
od:
R;

a(n) = A377059(A378028(n)).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

Formula