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

3, 4, 6, 8, 12, 14, 18, 20, 24, 30, 32, 38, 42, 48, 54, 60, 62, 68, 72, 80, 84, 90, 98, 108, 110, 132, 138, 140, 150, 180, 182, 198, 252, 318, 360, 398, 468, 570, 572, 930, 1722

Offset: 1

Hans Ruegg, Jul 21 2012

No further terms < 10^10.
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):
"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)"
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.
A224076(n) <= A064272(a(n)+1). - Reinhard Zumkeller, Mar 31 2013

			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.

Leo Moser, An Introduction to the Theory of Numbers, The Trillia Group 2004, page 84.

Cf. A065428.
Cf. A057828, A000290, A010051.
Cf. A224075; subsequence of A008864.

a214583 n = a214583_list !! (n-1)
a214583_list = filter (p 3 1) [2..] where
   p i k2 x = x <= k2 || (gcd k2 x > 1 || a010051' (x - k2) == 1) &&
                         p (i + 2) (k2 + i) x
-- Reinhard Zumkeller, Mar 31 2013, Jul 22 2012

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 *)
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 *)

N=10^10;
default(primelimit,N);
{ forprime (p=2, N,
    n = p + 1;
    q = 1;
    k = 1;
    while ( k*k < n,
        if ( gcd(k,n)==1,
            if ( ! isprime(n-k^2),  q=0; break() );
        );
        k += 1;
    );
    if ( q, print1(n,", ") );
); }
/* Joerg Arndt, Jul 21 2012 */

A254328 Numbers k such that all x^2 mod k are squares (including 0 and 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 12, 16

Offset: 1

Joerg Arndt, Jan 28 2015

Are there any more terms > 16?
There are no more terms less than 10^12. Probably the sequence is finite. - Charles R Greathouse IV, Jan 29 2015
This is a subsequence of A303704, so it is full. - Jianing Song, Feb 14 2019

			Terms k <= 16 and the squares mod k:
1: [0]
2: [0, 1]
3: [0, 1, 1]
4: [0, 1, 0, 1]
5: [0, 1, 4, 4, 1]
8: [0, 1, 4, 1, 0, 1, 4, 1]
12: [0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1]
16: [0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9, 0, 9, 4, 1]
k = 10 is not a term: in the list of squares mod 10, [0, 1, 4, 9, 6, 5, 6, 9, 4, 1], the numbers 5 and 6 are not squares.

Dan Ismailescu and Yunkyu James Lee, Polynomially growing integer sequences all whose terms are composite, arXiv:2501.04851 [math.NT], 2025. (See the proof of Theorem 2.1.)

Cf. A065428, A254329, A096008, A303704.

f[n_] := Mod[Range[n]^2, n]; Select[Range@ 10000, AllTrue[f@ #, IntegerQ[Sqrt[#]] &] &] (* AllTrue function introduced in version 10; Michael De Vlieger, Jan 29 2015 *)

isok(n)=for(k=2,n-1,if(!issquare(lift(Mod(k,n)^2)),return(0)));return(1);
for(n=1,10^9,if(isok(n),print1(n,", ")));

is(n)=for(k=sqrtint(n)+1,n\2, if(!issquare(k^2%n), return(0))); 1
for(m=10,10^6,for(k=0,sqrtint(2*m),if(is(t=m^2-k^2),print(t))))
\\ Charles R Greathouse IV, Jan 29 2015

Keywords fini and full added by Jianing Song, Feb 14 2019

A132213 Number of distinct primes among the squares mod n.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 2, 0, 1, 3, 0, 0, 2, 2, 4, 1, 1, 3, 3, 0, 2, 4, 3, 0, 4, 1, 4, 1, 2, 4, 2, 1, 3, 6, 2, 0, 5, 2, 6, 2, 2, 7, 5, 0, 6, 5, 3, 3, 8, 6, 3, 0, 3, 6, 8, 0, 6, 8, 3, 2, 2, 3, 7, 3, 3, 2, 7, 0, 9, 10, 3, 4, 6, 4, 9, 1, 10, 10, 11, 1, 2, 13, 3, 0, 10, 4, 5, 4, 4, 13, 4, 1, 11, 10, 4, 4

Offset: 1

T. D. Noe, Aug 13 2007, Aug 17 2007

It appears that a(n)=0 for only the 30 numbers in A065428, which appears to be related to idoneal numbers, A000926. The graph shows a(n) can be quite small even for large n. For example, a(9240)=7. Observe that the graph up to n=10000 appears to have 5 components. Why?
The logarithmic plot of the first 10^6 terms shows seven components.
From Rémy Sigrist, Nov 28 2017: (Start)
Empirically, in the logarithmic plot of the sequence:
- the set of indices of the first component (starting from the top), say S_1, is the union of A061345 and of A278568,
- the set of indices of the n-th component (for n > 1), say S_n, contains the numbers k not in a previous component and such that (omega(k) = n-1) or (omega(k) = n and val(k) = 0 or 2) or (omega(k) = n+1 and val(k) = 1) (where omega(k) = A001221(k) and val(k) = A007814(k)),
- see logarithmic scatterplot colored according to this scheme in Links section.
(End)

			For n=14, the squares (mod n) repeat 0,1,4,9,2,11,8,7,8,11,2,9,4,1,0,..., a sequence containing three distinct primes: 2, 7 and 11. Hence a(14)=3.

T. D. Noe, Table of n, a(n) for n = 1..10000
T. D. Noe, Logarithmic plot of 10^6 terms
Rémy Sigrist, Colored logarithmic plot of 2*10^6 terms

Cf. A000224 (number of squares mod n).

Cf. A000290, A001221, A007814, A010051, A061345, A278568.

import Data.List (nub, genericTake)
a132213 n = sum $ map a010051' $
            nub $ genericTake n $ map (`mod` n) $ tail a000290_list
-- Reinhard Zumkeller, Jun 23 2015, Oct 15 2011

Table[s=Union[Mod[Range[n]^2,n]]; Length[Select[s,PrimeQ]], {n,10000}]
Table[Count[Union[PowerMod[Range[n],2,n]],?PrimeQ],{n,100}] (* _Harvey P. Dale, Mar 02 2018 *)

A179402 Numbers n such that all x^4 mod n are nonprimes.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 12, 15, 16, 24, 28, 30, 40, 48, 56, 60, 72, 80, 85, 88, 96, 104, 105, 112, 120, 140, 145, 160, 168, 232, 240, 255, 265, 280, 312, 408, 420, 520, 624, 680, 760, 840, 1040, 1320, 1360, 1848, 1904, 4080

Offset: 1

Joerg Arndt, Jan 07 2011

nonn

A065428 is a subsequence.
No more such numbers up to 10^6.
Observe that many of these numbers are of the form k^2-1. Why?

A065428 (x^2 mod n).

for(n=1,10^6,q=1;for(x=1,n-1,if(isprime(component(Mod(x,n)^4,2)),q=0;break()));if(q,print1(n,", ")));

{a(n) = my(c, m); if(n<=1, n==1, c=1; m=1; while( cMichael Somos, Jan 07 2011 */

A254329 Numbers n such that all x^2 mod n are prime powers (including 0 and 1).

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 20, 32

Offset: 1

Joerg Arndt, Jan 28 2015

Cf. A065428, A254328.

f[n_] := Mod[Range[n]^2, n]; Select[Range@ 10000, AllTrue[f@ #, Length@ FactorInteger[#] == 1 &] &] (* AllTrue function introduced with Version 10; Michael De Vlieger, Jan 29 2015 *)

is(n)=for(i=2,9,if(!isprimepower(i^2%n) && i^2%n>1, return(0))); 1 \\ Charles R Greathouse IV, Jan 30 2015

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

A254328 Numbers k such that all x^2 mod k are squares (including 0 and 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Extensions

A132213 Number of distinct primes among the squares mod n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Mathematica

A179402 Numbers n such that all x^4 mod n are nonprimes.

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

PARI

A254329 Numbers n such that all x^2 mod n are prime powers (including 0 and 1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI