A214583 -id:A214583 - cp's OEIS frontend

A224075 Triangle read by rows: n-th row gives the primes p of form (m - k^2) where m = A214583(n), k < m and gcd(k,m) = 1.

2, 3, 5, 7, 11, 5, 13, 17, 11, 19, 23, 29, 7, 23, 31, 13, 29, 37, 17, 41, 23, 47, 5, 29, 53, 11, 59, 13, 37, 53, 61, 19, 43, 59, 67, 23, 47, 71, 31, 71, 79, 59, 83, 41, 89, 17, 73, 89, 97, 59, 83, 107, 29, 61, 101, 109, 83, 107, 131, 17, 89, 113, 137, 19, 59

Offset: 1

Reinhard Zumkeller, Mar 31 2013

Defined where A214583 is defined.

			.   n | A214583 |  T(n,k) for k = 1 .. A224076(n)
. ----+---------+-------------------------------------------------------
.   1 |      3  |  [2]
.   2 |      4  |  [3]
.   3 |      6  |  [5]
.   4 |      8  |  [7]
.   5 |     12  |  [11]
.   6 |     14  |  [5,13]
.   7 |     18  |  [17]
.   8 |     20  |  [11,19]
.   9 |     24  |  [23]
.  10 |     30  |  [29]
.  11 |     32  |  [7,23,31]           32-5^2, 32-3^2, 32-1^2
.  12 |     38  |  [13,29,37]          38-5^2, 38-3^2, 38-1^2
.  13 |     42  |  [17,41]             42-5^2, 42-1^2
.  14 |     48  |  [23,47]             48-5^2, 48-1^2
.  15 |     54  |  [5,29,53]           54-7^2, 54-5^2, 54-1^2
.  16 |     60  |  [11,59]             60-7^2, 60-1^2
.  17 |     62  |  [13,37,53,61]       62-7^2, 62-5^2, 62-3^2, 62-1^2
.  18 |     68  |  [19,43,59,67]       68-7^2, 68-5^2, 68-3^2, 68-1^2
.  19 |     72  |  [23,47,71]          72-7^2, 72-5^2, 72-1^2
.  20 |     80  |  [31,71,79]          80-7^2, 80-3^2, 80-1^2
.  21 |     84  |  [59,83]             84-5^2, 83-1^2
.  22 |     90  |  [41,89]             90-7^2, 90-1^2
.  23 |     98  |  [17,73,89,97]       98-9^2, 98-5^2, 98-3^2, 98-1^2
.  24 |    108  |  [59,83,107]         108-7^2, 108-5^2, 108-1^2
.  25 |    110  |  [29,61,101,109]     110-9^2, 110-7^2, 101-3^2, 101-1^2
.  26 |    132  |  [83,107,131]        132-7^2, 132-5^2, 132-1^2
.  27 |    138  |  [17,89,113,137]     138-11^2, 138-7^2, ...
.  28 |    140  |  [19,59,131,139]     ...
.  29 |    150  |  [29,101,149]
.  30 |    180  |  [11,59,131,179]
.  31 |    182  |  [61,101,157,173,181]
.  32 |    198  |  [29,149,173,197]
.  33 |    252  |  [83,131,227,251]
.  34 |    318  |  [29,149,197,269,293,317]
.  35 |    360  |  [71,191,239,311,359]
.  36 |    398  |  [37,109,173,229,277,317,349,373,389,397]
.  37 |    468  |  [107,179,347,419,443,467]
.  38 |    570  |  [41,281,401,449,521,569]
.  39 |    572  |  [43,131,211,283,347,491,523,547,563,571]
.  40 |    930  |  [89,401,569,641,761,809,881,929]
.  41 |   1722  |  [353,761,881,1097,1193,1361,1433,1553,1601,1697,1721].

Reinhard Zumkeller, Rows n = 1..41 of triangle, flattened

Cf. A224076 (row lengths), A010051.

a224075 n k = a224075_tabf !! (n-1) !! (k-1)
a224075_row n = a224075_tabf !! (n-1)
a224075_tabf = f 3 where
   f x = g [] 3 1 where
     g ps i k2 | x <= k2        = ps : f (x + 1)
               | gcd k2 x > 1   = g ps (i + 2) (k2 + i)
               | a010051 q == 1 = g (q:ps) (i + 2) (k2 + i)
               | otherwise      = f (x + 1)
               where q = x - k2

A064272 Number of representations of n as the sum of a prime number and a nonzero square.

Original entry on oeis.org

0, 1, 1, 0, 2, 1, 1, 1, 0, 2, 2, 0, 2, 1, 1, 1, 2, 1, 2, 2, 1, 2, 1, 0, 1, 3, 2, 1, 2, 0, 3, 2, 0, 2, 1, 0, 4, 2, 1, 2, 2, 1, 2, 2, 1, 3, 2, 1, 1, 2, 2, 2, 3, 1, 3, 2, 0, 2, 2, 0, 4, 2, 0, 2, 3, 2, 4, 2, 1, 2, 3, 1, 1, 3, 1, 4, 2, 1, 3, 1, 1, 5, 3, 0, 3, 3, 2, 2, 2, 0, 4, 2, 1, 3, 2, 1, 4, 1, 1, 2, 3, 2, 3, 4, 1

Offset: 2

Vladeta Jovovic, Sep 23 2001

nonn

a(A064233(n))=0.
A002471(n) - 1 <= a(n) <= A002471(n). [Reinhard Zumkeller, Sep 30 2011]
A224076(n) <= a(A214583(n)+1) for n such that A214583 is defined; a(A064283(n)) = n and a(m) <> n for m < A064283(n). - Reinhard Zumkeller, Mar 31 2013

			6=2+4=5+1, thus a(6)=2.

Reinhard Zumkeller, Table of n, a(n) for n = 2..10000

Cf. A064233.

Cf. A000290.

a064272 n = sum $
   map (a010051 . (n -)) $ takeWhile (< n) $ tail a000290_list
-- Reinhard Zumkeller, Jul 23 2013, Sep 30 2011

a(n) = SUM(A010051(k)*A010052(n-k+1): 1<=k<=n). [From Reinhard Zumkeller, Nov 05 2009]

G.f.: (Sum_{k>=1} x^prime(k))*(Sum_{k>=1} x^(k^2)). - Ilya Gutkovskiy, Feb 05 2017

A065428 Numbers k such that no x^2 mod k is prime.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 12, 15, 16, 24, 28, 40, 48, 56, 60, 72, 88, 112, 120, 168, 232, 240, 280, 312, 408, 520, 760, 840, 1320, 1848

Offset: 1

Joerg Arndt, Nov 16 2001

All numbers in this sequence except 56 are idoneal (A000926) - Joerg Arndt, Jul 13 2005
No more terms < 10^6. - T. D. Noe, Aug 10 2007
No more terms < 10^11. - Charles R Greathouse IV, Dec 15 2008
Numbers x such that all x^3 mod k are nonprimes are 1, 2, 7, 9, 63, and apparently no more.

Joerg Arndt, Matters Computational (The Fxtbook), p. 784

Cf. A179402 (x^4 mod n).
Cf. A010051, A000196, A000290.
Cf. A214583 (n such that for all k with gcd(n, k) = 1 and n > k^2, n - k^2 is prime).

a065428 n = a065428_list !! (n-1)
a065428_list = filter f [1..] where
   f x = all (== 0) $
         map (a010051' . (`mod` x) . a000290) [a000196 x .. x-1]
-- Reinhard Zumkeller, Aug 01 2012, Aug 15 2011

t={}; Do[s=Union[Mod[Range[n]^2,n]]; If[Select[s,PrimeQ]=={}, AppendTo[t,n]], {n,1000}]; t  (* T. D. Noe, Aug 10 2007 *)
nx2pQ[n_]:=Module[{m=PowerMod[Range[3n],2,n]},Count[ FindTransientRepeat[ m,2][[2]], ?PrimeQ]==0]; Select[Range[2000],nx2pQ] (* Requires Mathematica version 10 or later *) (* _Harvey P. Dale, Jun 11 2019 *)

for(n=1, 10^9, q=1; for(x=1, n-1, if(isprime(lift(Mod(x,n)^2)), q=0; break())); if(q, print1(n, ", "))); \\ edited, Joerg Arndt, Jan 28 2015

from sympy import isprime
def ok(n): return not any(isprime((x**2)%n) for x in range(2, n))
print(list(filter(ok, range(1, 2000)))) # Michael S. Branicky, May 08 2021

A224076 Row lengths of triangle in A224075.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 3, 3, 2, 2, 3, 2, 4, 4, 3, 3, 2, 2, 4, 3, 4, 3, 4, 4, 3, 4, 5, 4, 4, 6, 5, 10, 6, 6, 10, 8, 11

Offset: 1

Reinhard Zumkeller, Mar 31 2013

Cf. A064272, A214583, A224075, A224076.

Haskell
```
a224076 = length . a224075_row
```

a(n) <= A064272(A214583(n)+1) for n such that A214583 is defined.

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 21, 24, 28, 40, 48, 56, 60, 72, 88, 120, 168, 240, 840

Offset: 1

Jianing Song, Apr 29 2018

Numbers k such that A046073(k) = A057828(k).
There are exactly 25 members in this sequence and this is the full list. Note that for other k, A046073(k) > A057828(k).
From Jianing Song, Feb 14 2019: (Start)
For the proof that this sequence is finite, we will show that there are no terms > 130729.
Let A(n) = A046073(n) be the number of coprime quadratic residues modulo n. By definition, if k is a term then A(k) <= sqrt(k), that is, A(k)/sqrt(k) <= 1. Let f(n) = A(n)/sqrt(n), then f(n) is multiplicative with f(2) = sqrt(2)/2, f(4) = 1/2, f(2^e) = 2^(e/2 - 3) for e >= 3, f(p^e) = ((p - 1)/2)*p^(e/2 - 1) when p > 2. Note that f(2^e) >= a(2^3), f(p^e) >= f(p), f(p) > 1 when p >= 7. For every number n, we have:
a) if n is divisible by a prime >= 127, then f(n) >= f(2^3)*f(3)*f(5)*f(127) = sqrt(1323/1270) > 1.
b) if n is divisible by two distinct primes >= 23, then f(n) >= f(2^3)*f(3)*f(5)*f(23)*f(29) = sqrt(11858/10005) > 1.
So if k > 130729 is a term, then all prime factors of k are no greater than 113, and k contains at most one prime factor >= 23. On the other hand, if all prime factors of k are no greater than 19, then 53881 is a coprime quadratic residue modulo k because 53881 is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17 and 19, but 53881 is not a perfect square, a contradiction. As a result, k must contain exactly one prime factor p in [23, 113].
Now if a number m is a coprime quadratic residue modulo 2^3, 3, 5, 7, 11, 13, 17, 19 and p, then m is a coprime quadratic residue modulo k. Consider the numbers 53881, 86641, 87481, 102001, 117049 and 130729. At least one of them is a coprime quadratic residue modulo each prime p in [23, 113], so at least one of them is a coprime quadratic residue modulo k, but none of them is a square, a contradiction! (End)

			All coprime quadratic residues modulo 21 are 1, 4, 16 and they are all squares, so 21 is a term.
All coprime quadratic residues modulo 840 are 1, 121, 169, 289, 361, 529 and they are all squares, so 840 is a term.
249 == 23^2 is a coprime quadratic residue modulo 280 but 249 is not a square number, so 280 is not a term.

Cf. A046073, A057828, A214583.

A254328 is a subsequence.

for(k=1, 130729, if(eulerphi(k)/2^#znstar(k)[2]<=sqrt(k), for(j=1, k, if(gcd(j,k)==1&&!issquare(j^2%k), break()); if(j==k, print1(k, ", "))))) \\ Jianing Song, Feb 15 2019

cp's OEIS Frontend

A224075 Triangle read by rows: n-th row gives the primes p of form (m - k^2) where m = A214583(n), k < m and gcd(k,m) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

A064272 Number of representations of n as the sum of a prime number and a nonzero square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Formula

A065428 Numbers k such that no x^2 mod k is prime.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

A224076 Row lengths of triangle in A224075.

Views

Author

Keywords

Crossrefs

Programs

Haskell

Formula

A303704 Numbers k such that all coprime quadratic residues modulo k are squares.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI