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,4

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.

Formula

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

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

Prog

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

Crossrefs

Cf. A000010, A378028, A378029.

Sequence in context: A160762 A112968 A263407 * A221838 A343122 A338869

Adjacent sequences: A377055 A377057 A377058 * A377060 A377061 A377062

Keyword

nonn,look

Author

Darío Clavijo, Oct 14 2024

Status

approved