A387952 Squarefree semiprimes whose prime factors are in A073024.

253, 517, 649, 913, 1081, 1177, 1357, 1639, 1837, 1903, 1909, 1969, 2453, 2461, 2497, 2773, 2893, 2959, 3113, 3223, 3427, 3487, 3817, 3841, 3901, 3949, 3979, 4037, 4117, 4213, 4279, 4829, 4897, 5029, 5129, 5137, 5221, 5269, 5489, 5533, 5599, 6049, 6127, 6187, 6193, 6259, 6313, 6457

Offset

1,1

Comments

Cài Jìn-Yī (蔡进一) proved that these numbers cannot be factored by Shor's algorithm in the presence of noise.

Squares are omitted because it's easy to detect and factor a square.

Links

Pierre Abbat, Table of n, a(n) for n = 1..10509

Pierre Abbat, Julia program

Jin-Yi Cai, Shor's algorithm does not factor large integers in the presence of noise, arXiv:2306.10072 [quant-ph], 2023.

Example

6313=59*107, where 59 and 107 are both in A073024 because 58 and 106 have large prime factors 29 and 53 respectively.

Prog

(Julia) # See link for complete repo.
using Primes
function isFouvry(p::Integer)
  facs=factor(p-1)
  p>2 && big(maximum(keys(facs)))^3>big(p)^2
end
function caiSemiprimes(minPrime::Int, maxSemiprime::Int)
  if minPrime<11
    minPrime=11
  end
  maxPrime=max(minPrime, maxSemiprime÷minPrime)
  primeList=filter(isFouvry, primes(minPrime, maxPrime))
  n=length(primeList)
  sort(filter(x->x<=maxSemiprime, [primeList[i]*primeList[j] for i in 1:n for j in (i+1):n]))
end

Crossrefs

Cf. A073024.

Sequence in context: A244168 A002289 A158078 * A157356 A203085 A245790

Adjacent sequences: A387949 A387950 A387951 * A387953 A387954 A387955

Keyword

nonn

Author

Pierre Abbat, Oct 12 2025

Status

approved