A378029 -id:A378029 - 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.

A378028 Positions of records in A377059.

Original entry on oeis.org

1, 4, 9, 17, 22, 25, 46, 49, 81, 118, 121, 169, 243, 334, 337, 343, 361, 529, 841, 961, 1331, 1369, 2187, 2197, 2209, 2809, 3481, 3721, 4489, 5041, 6241, 6859, 6889, 7921, 10201, 11449, 12167, 14641, 16129, 17161, 19321, 22201, 24389, 26569, 27889, 29791, 29929, 32041, 32761, 38809, 39601, 44521, 49729

Offset: 1

Robert Israel, Nov 14 2024

nonn

Numbers k such that A377059(k) > A377059(j) for all j < k.
The record values are in A378029.
It appears that in most cases a(n) is in A244623 (Odd prime powers that are not primes) and A378029(n) = A000010(a(n)).
If p is in A001122 and is not a Wieferich prime (A001220), then p^2 is a term with A377059(p^2) = p*(p-1).

			a(3) = 9 is a term because A377059(9) = 6 > A377059(k) for all k < 9.

Cf. A000010, A001122, A001220, A244623, A377059, 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:
J:= 1: m:= 0: count:= 0:
for k from 2 while count < 100 do
v:= f(k);
if v > m then m:= v; J:= J,k; count:= count+1 fi;
od:
J;

A378029(n) = A377059(a(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