|
%I #39 Dec 19 2020 03:32:57
%S 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,
%T 38,39,41,42,43,46,47,50,51,53,55,57,58,59,61,62,65,66,67,69,70,71,73,
%U 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
%N 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.
%C Numbers n such that, if p^2 divides n for any prime p, then p = 1 mod 4.
%C Equivalently, squarefree numbers times A004613.
%C Thus, numbers k such that A065338(A057521(k)) = 1. - _Antti Karttunen_, Jun 21 2014
%C Different from A193304: terms 169, 289, 338, 507, 578, 841, 845, 867, ... are here but not in A193304. - _Michel Marcus_, Jun 20 2014
%C 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
%H Antti Karttunen, <a href="/A240370/b240370.txt">Table of n, a(n) for n = 1..10000</a>
%H Joshua Harrington, Lenny Jones, and Alicia Lamarche, <a href="http://arxiv.org/abs/1404.0187">Representing Integers as the Sum of Two Squares in the Ring Z_n</a>, arXiv:1404.0187 [math.NT], Apr 01 2014 and, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL17/Jones/jones14.html">J. Int. Seq. 17 (2014) # 14.7.4</a>.
%e 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.
%e In Z_8, there is no way to express 3 as a sum of two squares. Therefore 8 is not in the sequence.
%t rad[n_] := Times @@ First /@ FactorInteger[n];
%t a57521[n_] := n/Denominator[n/rad[n]^2];
%t a65338[n_] := a65338[n] = If[n==1, 1, Mod[p = FactorInteger[n][[1, 1]], 4]* a65338[n/p]];
%t Select[Range[200], a65338[a57521[#]] == 1&] (* _Jean-François Alcover_, Sep 22 2018, after _Antti Karttunen_ *)
%t Select[Range[200], AllTrue[FactorInteger[#], Mod[First[#1], 4] == 1 || Last[#1] == 1 &] &] (* _Amiram Eldar_, Dec 19 2020 *)
%o (PARI) is(n)=my(f=factor(n)); for(i=1,#f~,if(f[i,2]>1 && f[i,1]%4>1, return(0))); 1
%o (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
%o (Scheme, with Antti Karttunen's IntSeq-library)
%o (define A240370 (MATCHING-POS 1 1 (lambda (k) (= 1 (A065338 (A057521 k))))))
%o ;; _Antti Karttunen_, Jun 21 2014
%Y The subsequence A240109 is a version not allowing 0.
%Y Different from A193304.
%Y Complement of A053443. Subsequence of A192450.
%Y Cf. A004613, A057521, A064533, A065338, A243379.
%K nonn
%O 1,2
%A _Charles R Greathouse IV_, Apr 04 2014
|
