A075432 Primes with no squarefree neighbors.

17, 19, 53, 89, 97, 127, 149, 151, 163, 197, 199, 233, 241, 251, 269, 271, 293, 307, 337, 349, 379, 449, 487, 491, 521, 523, 557, 577, 593, 631, 701, 727, 739, 751, 773, 809, 811, 881, 883, 919, 953, 991, 1013, 1049, 1051, 1061, 1063, 1097, 1151, 1171, 1249

Offset: 1

Author

Reinhard Zumkeller, Sep 15 2002

Keywords

• nonn

Comments

Complement of A075430 in A000040.

From Ludovicus (luiroto(AT)yahoo.com), Dec 07 2009: (Start)

I propose a shorter name: non-Euclidean primes. That is justified by the Euclid's demonstration of the infinitude of primes. It appears that the proportion of non-Euclidean primes respect to primes tend to the limit 1-2A where A = 0.37395581... is Artin's constant. This table calculated by Jens K. Andersen corroborates it:

10^5: 2421 / 9592 = 0.2523978315

10^6: 19812 / 78498 = 0.2523885958

10^7: 167489 / 664579 = 0.2520227091

10^8: 1452678 / 5761455 = 0.2521373507

10^9: 12817966 / 50847534 = 0.2520862860

10^10: 114713084 / 455052511 = 0.2520875750

10^11: 1038117249 / 4118054813 = 0.2520892256

It comes close to the expected 1-2A. (End)

This sequence is infinite by Dirichlet's theorem, since there are infinitely many primes == 17 or 19 (mod 36) and these have no squarefree neighbors. Ludovicus's conjecture about density is correct. Capsule proof: either p-1 or p+1 is divisible by 4, so it suffices to consider the other number (without loss of generality, p+1). For some fixed bound L, p is not divisible by any prime q < L (with finitely many exceptions) so there are q^2 - q possible residue classes for p. The primes in each are uniformly distributed so the probability that p+1 is divisible by q^2 is 1/(q^2 - q). The product of the complements goes to 2A as L increases without bound, and since 2A is an upper bound the limit is sandwiched between. - Charles R Greathouse IV, Aug 27 2014

Primes p such that both p-1 and p+1 are divisible by a square greater than 1. - N. J. A. Sloane, Jul 19 2024

Examples

			p = 17 is a term because 16 = 4^2 and 18=2*3^2 are divisible by squares > 1. - _N. J. A. Sloane_, Jul 19 2024
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
• Pieter Moree, Artin's primitive root conjecture -a survey -, arXiv:math/0412262 [math.NT], 2004-2012.
• Carlos Rivera, Conjecture 65. Non-Euclidean primes, The Prime Puzzles and Problems Connection.

Crossrefs

Cf. A039787, A049097, A005117, A000040, A008966, A010051.

Intersection of A000040 and A281192.

Programs

Haskell

a075432 n = a075432_list !! (n-1)
a075432_list = f [2, 4 ..] where
   f (u:vs@(v:ws)) | a008966 v == 1 = f ws
                   | a008966 u == 1 = f vs
                   | a010051' (u + 1) == 0 = f vs
                   | otherwise            = (u + 1) : f vs
-- Reinhard Zumkeller, May 04 2013

Maple

filter:= n -> isprime(n) and not numtheory:-issqrfree(n+1) and not numtheory:-issqrfree(n-1):
select(filter, [seq(2*i+1, i=1..1000)]); # Robert Israel, Aug 27 2014

Mathematica

lst={}; Do[p=Prime[n]; If[ !SquareFreeQ[Floor[p-1]] && !SquareFreeQ[Floor[p+1]], AppendTo[lst,p]], {n,6!}]; lst (* Vladimir Joseph Stephan Orlovsky, Dec 20 2008 *)
Select[Prime[Range[300]],!SquareFreeQ[#-1]&&!SquareFreeQ[#+1]&] (* Harvey P. Dale, Apr 24 2014 *)

PARI

is(n)=!issquarefree(if(n%4==1, n+1, n-1)) && isprime(n) \\ Charles R Greathouse IV, Aug 27 2014

Formula

a(n) ~ Cn log n, where C = 1/(1 - 2A) = 1/(1 - Product_{p>2 prime} (1 - 1/(p^2-p))), where A is the constant in A005596. - Charles R Greathouse IV, Aug 27 2014

Extensions

More terms (that were already in the b-file) from Jeppe Stig Nielsen, Apr 23 2020