login
A073024
Primes p such that p-1 has a prime factor q > p^(2/3).
3
11, 23, 47, 59, 83, 107, 149, 167, 173, 179, 223, 227, 263, 269, 283, 293, 317, 347, 359, 367, 383, 389, 439, 467, 479, 499, 503, 509, 557, 563, 569, 587, 607, 619, 643, 653, 719, 773, 787, 797, 809, 823, 839, 857, 863, 887, 907, 983, 1019, 1031, 1039, 1049, 1087, 1091
OFFSET
1,1
COMMENTS
Étienne Fouvry showed that a positive fraction of all primes have this property.
Jin-Yi Cai showed that a product of two of these primes cannot be factored by Shor's algorithm in the presence of noise. - Hugo van der Sanden, Apr 17 2024
LINKS
Charles R Greathouse IV, Table of n, a(n) for n = 1..27449.
Jin-Yi Cai, Shor's algorithm does not factor large integers in the presence of noise, arXiv:2306.10072 [quant-ph], 2023.
Étienne Fouvry, Théorème de Brun-Titchmarsh; application au théorème de Fermat, Invent. Math 79 (1985), no. 2, 383-407.
MAPLE
with(numtheory); a := []; for i from 2 to 1000 do p := ithprime(i); t1 := factorset(p-1); q := t1[nops(t1)]; if q^3 > p^2 then a := [op(a), p]; fi; od:
MATHEMATICA
p = Prime@Range@1000;
criterion = FactorInteger[# - 1][[-1, 1]]^3 > #^2 &;
Select[p, criterion] (* David Trimas, Apr 02 2024 *)
PROG
(PARI) gpf(n)=my(f=factor(n)[, 1]); f[#f]
is(n)=gpf(n-1)^3>n^2 && isprime(n) \\ Charles R Greathouse IV, Sep 14 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Aug 23 2002
STATUS
approved