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

Author

Darío Clavijo, Oct 14 2024

Keywords

• nonn
• look

Comments

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

Links

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

Crossrefs

Cf. A000010, A378028, A378029.

Programs

Maple

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

Python

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

Formula

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