cp's OEIS Frontend

A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.

%I A214583 #39 Jan 15 2023 02:07:56
%S A214583 3,4,6,8,12,14,18,20,24,30,32,38,42,48,54,60,62,68,72,80,84,90,98,108,
%T A214583 110,132,138,140,150,180,182,198,252,318,360,398,468,570,572,930,1722
%N A214583 Numbers m such that for all k with gcd(m, k) = 1 and m > k^2, m - k^2 is prime.
%C A214583 No further terms < 10^10.
%C A214583 This sequence is based on a remark in a paper distributed over the Internet (see the Leo Moser link) under the heading "Unsolved Problems and Conjectures" (page 84):
%C A214583 "Is 968 the largest number n such that for all k with (n, k) = 1 and n > k^2, n - k^2 is prime? (Erdős)"
%C A214583 The statement by Moser contains an error: 968 does NOT have this property (968-25*25 = 343 = 7*7*7), and the largest such number (1722) is larger than 968.
%C A214583 A224076(n) <= A064272(a(n)+1). - _Reinhard Zumkeller_, Mar 31 2013
%H A214583 Leo Moser, <a href="http://www.trillia.com/moser-number.html">An Introduction to the Theory of Numbers</a>, The Trillia Group 2004, page 84.
%e A214583 For example, the number 20 is part of this sequence because 20-1*1 = 19 (prime), and 20-3*3 = 11 (prime). Not considered are 20-2*2 and 20-4*4, because 2 and 4 are not relative primes to 20.
%t A214583 Reap[For[p = 2, p < 2000, p = NextPrime[p], n = p+1; q = True; k = 1; While[k*k < n, If[GCD[k, n] == 1, If[! PrimeQ[n - k^2], q = False; Break[]]]; k += 1]; If[q, Sow[n]]]] [[2, 1]] (* _Jean-François Alcover_, Oct 11 2013, after _Joerg Arndt_'s Pari program *)
%t A214583 gQ[n_]:=AllTrue[n-#^2&/@Select[Range[Floor[Sqrt[n]]],CoprimeQ[ #, n]&], PrimeQ]; Select[Range[2000],gQ] (* The program uses the AllTrue function from Mathematica version 10 *) (* _Harvey P. Dale_, Dec 02 2018 *)
%o A214583 (PARI)
%o A214583 N=10^10;
%o A214583 default(primelimit,N);
%o A214583 { forprime (p=2, N,
%o A214583     n = p + 1;
%o A214583     q = 1;
%o A214583     k = 1;
%o A214583     while ( k*k < n,
%o A214583         if ( gcd(k,n)==1,
%o A214583             if ( ! isprime(n-k^2),  q=0; break() );
%o A214583         );
%o A214583         k += 1;
%o A214583     );
%o A214583     if ( q, print1(n,", ") );
%o A214583 ); }
%o A214583 /* _Joerg Arndt_, Jul 21 2012 */
%o A214583 (Haskell)
%o A214583 a214583 n = a214583_list !! (n-1)
%o A214583 a214583_list = filter (p 3 1) [2..] where
%o A214583    p i k2 x = x <= k2 || (gcd k2 x > 1 || a010051' (x - k2) == 1) &&
%o A214583                          p (i + 2) (k2 + i) x
%o A214583 -- _Reinhard Zumkeller_, Mar 31 2013, Jul 22 2012
%Y A214583 Cf. A065428.
%Y A214583 Cf. A057828, A000290, A010051.
%Y A214583 Cf. A224075; subsequence of A008864.
%K A214583 nonn,nice
%O A214583 1,1
%A A214583 _Hans Ruegg_, Jul 21 2012