A240370 Positive integers n such that every element in the ring of integers modulo n can be written as the sum of two squares modulo n.

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 50, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107, 109, 110, 111, 113, 114, 115, 118, 119, 122, 123, 125, 127, 129, 130, 131, 133, 134, 137, 138, 139, 141, 142, 143, 145, 146, 149, 150, 151, 154, 155, 157, 158, 159, 161, 163, 165, 166, 167, 169

Offset

1,2

Comments

Numbers n such that, if p^2 divides n for any prime p, then p = 1 mod 4.

Equivalently, squarefree numbers times A004613.

Thus, numbers k such that A065338(A057521(k)) = 1. - Antti Karttunen, Jun 21 2014

Different from A193304: terms 169, 289, 338, 507, 578, 841, 845, 867, ... are here but not in A193304. - Michel Marcus, Jun 20 2014

The asymptotic density of this sequence is 3/(8*K^2) = (3/4) * A243379 = 0.64208..., where K is the Landau-Ramanujan constant (A064533). - Amiram Eldar, Dec 19 2020

Links

Antti Karttunen, Table of n, a(n) for n = 1..10000

Joshua Harrington, Lenny Jones, and Alicia Lamarche, Representing Integers as the Sum of Two Squares in the Ring Z_n, arXiv:1404.0187 [math.NT], Apr 01 2014 and, J. Int. Seq. 17 (2014) # 14.7.4.

Example

In Z_7, 0^2 + 0^2 = 0, 1^2 + 0^2 = 1, 1^2 + 1^2 = 2, 3^2 + 1^2 = 3, 2^2 + 0^2 = 4, 2^2 + 1^2 = 5, 3^2 + 2^2 = 6. Therefore 7 is in the sequence.
In Z_8, there is no way to express 3 as a sum of two squares. Therefore 8 is not in the sequence.

Mathematica

rad[n_] := Times @@ First /@ FactorInteger[n];
a57521[n_] := n/Denominator[n/rad[n]^2];
a65338[n_] := a65338[n] = If[n==1, 1, Mod[p = FactorInteger[n][[1, 1]], 4]* a65338[n/p]];
Select[Range[200], a65338[a57521[#]] == 1&] (* Jean-François Alcover, Sep 22 2018, after Antti Karttunen *)
Select[Range[200], AllTrue[FactorInteger[#], Mod[First[#1], 4] == 1 || Last[#1] == 1 &] &] (* Amiram Eldar, Dec 19 2020 *)

Prog

(PARI) is(n)=my(f=factor(n)); for(i=1, #f~, if(f[i, 2]>1 && f[i, 1]%4>1, return(0))); 1
(PARI) isok(n) = { if (n < 2, return (0)); if ((n % 4) == 0, return (0)); forprime(q = 2, n, if (((q % 4) == 3) && ((n % q) == 0) && ((n % q^2) == 0), return (0)); ); return (1); } \\ Michel Marcus, Jun 08 2014
(Scheme)
;; With Antti Karttunen's IntSeq-library.
(define A240370 (MATCHING-POS 1 1 (lambda (k) (= 1 (A065338 (A057521 k))))))
;; Antti Karttunen, Jun 21 2014

Crossrefs

The subsequence A240109 is a version not allowing 0.

Different from A193304.

Complement of A053443. Subsequence of A192450.

Cf. A004613, A057521, A064533, A065338, A243379.

Sequence in context: A358976 A064594 A325511 * A193304 A333634 A348499

Adjacent sequences: A240367 A240368 A240369 * A240371 A240372 A240373

Keyword

nonn

Author

Charles R Greathouse IV, Apr 04 2014

Status

approved