A022544 -id:A022544 - cp's OEIS frontend

A229062 1 if n is representable as sum of two nonnegative squares, otherwise 0.

1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1

Offset: 0

Ralf Stephan, Sep 17 2013

Characteristic function of A001481.
a(n) = 1 if A000161(n) > 0.
a(A022544(n)) = 0.
Multiplicative because A002654 is. - Andrew Howroyd, Aug 01 2018
For positive n, m = 2*a(n) + 1 is the smallest positive integer such that m * n is not a sum of two squares. - Peter Schorn, Dec 29 2023

Antti Karttunen, Table of n, a(n) for n = 0..65537
Index entries for characteristic functions

Cf. A002654, A004018, A070176. Partial sums are in A102548.

Cf. A000161, A022544.

Join[{1},Table[If[SquaresR[2,n]>1,1,0],{n,120}]] (* Harvey P. Dale, Aug 25 2017 *)

a(n)=my(f=0); my(r=sqrtint(n)); forstep(i=r, 1, -1, if(issquare(n-i*i), f=1; break)); f

a(n)=if(0==n,1,(sumdiv(n, d,(d%4==1) - (d%4==3)) > 0)); \\ Andrew Howroyd, Aug 01 2018, the check for 0-argument added by Antti Karttunen, Apr 22 2022

from sympy import factorint
def A229062(n): return int(all(p & 3 != 3 or e & 1 == 0 for p, e in factorint(n).items())) # Chai Wah Wu, Jun 28 2022

a(n) = min{1, A004018(n)}. - N. J. A. Sloane, Jan 11 2020

A260728 Bitwise-OR of the exponents of all 4k+3 primes in the prime factorization of n.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Aug 12 2015

nonn

A001481 (numbers that are the sum of 2 squares) gives the positions of even terms in this sequence, while its complement A022544 (numbers that are not the sum of 2 squares) gives the positions of odd terms.

If instead of bitwise-oring (A003986) we added in ordinary way the exponents of 4k+3 primes together, we would get the sequence A065339. For the positions where these two sequences differ see A260730.

			For n = 21 = 3^1 * 7^1 we compute A003986(1,1) = 1, thus a(21) = 1.
For n = 63 = 3^2 * 7^1 we compute A003986(2,1) = A003986(1,2) = 3, thus a(63) = 3.

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

Cf. A000035, A001481, A022544, A003986, A020639, A028234, A032742, A067029, A097706, A229062, A260730.
Cf. also A267113, A267116, A267099.
Differs from A065339 for the first time at n=21, where a(21) = 1, while A065339(21)=2.

Table[BitOr @@ (Map[Last, FactorInteger@ n /. {p_, } /; MemberQ[{0, 1, 2}, Mod[p, 4]] -> Nothing]), {n, 0, 120}] (* _Michael De Vlieger, Feb 07 2016 *)

from functools import reduce
from operator import or_
from sympy import factorint
def A260728(n): return reduce(or_,(e for p, e in factorint(n).items() if p & 3 == 3),0) # Chai Wah Wu, Jun 28 2022

(define (A260728 n) (cond ((< n 3) 0) ((even? n) (A260728 (/ n 2))) ((= 1 (modulo (A020639 n) 4)) (A260728 (A032742 n))) (else (A003986bi (A067029 n) (A260728 (A028234 n)))))) ;; A003986bi implements bitwise-or (see A003986).

If n < 3, a(n) = 0; thereafter, for any even n: a(n) = a(n/2), for any n with its smallest prime factor (A020639) of the form 4k+1: a(n) = a(A032742(n)), otherwise [when A020639(n) is of the form 4k+3] a(n) = A003986(A067029(n),a(A028234(n))).
Other identities. For all n >= 0:
A229062(n) = 1 - A000035(a(n)). [Reduced modulo 2 and complemented, the sequence gives the characteristic function of A001481.]
a(n) = a(A097706(n)). [The result depends only on the prime factors of the form 4k+3.]
a(n) = A267116(A097706(n)).
a(n) = A267113(A267099(n)).

A062316 Neither the sum or difference of 2 squares.

Original entry on oeis.org

6, 14, 22, 30, 38, 42, 46, 54, 62, 66, 70, 78, 86, 94, 102, 110, 114, 118, 126, 134, 138, 142, 150, 154, 158, 166, 174, 182, 186, 190, 198, 206, 210, 214, 222, 230, 238, 246, 254, 258, 262, 266, 270, 278, 282, 286, 294, 302, 310, 318, 322, 326, 330, 334, 342, 350, 354, 358

Offset: 1

Michel ten Voorde, Jul 05 2001

nonn

Elements of A022544 congruent to 2 (mod 4).
Union of numbers congruent to 6 mod 8 (A017137) with numbers of the form 2 * A084109(n). - Franklin T. Adams-Watters, Jan 21 2007
Explanation: odd numbers are equal to the difference between two successive squares and among even numbers, multiples of 4 are of the form (k+2)^2-k^2, thus odd numbers and multiples of 4 are not in the sequence. Conversely, a difference of 2 squares cannot equal 2 (mod 4), thus this sequence contains the integers of the form 4k+2 that are in A022544 (not the sum of two squares); among integers of form 4k+2, this sequence contains all the integers of the form 8n+6 (A017137) that are not the sum of 2 squares because they have at least one prime factor congruent to 3 (mod 4) to an odd power; it also contains integers of the form 8n+2 = 2(4n+1) with 4n+1 not the sum of two squares, which is sequence A084109. - Jean-Christophe Hervé, Oct 24 2015

			From _Jean-Christophe Hervé_, Oct 24 2015: (Start)
6, 14, 22, 30, 38, 46, ... are in the sequence because they equal 6 (mod 8).
42 = 2*3*7, 66 = 2*3*11, 114 = 2*7*11 are also in the sequence: of the form 2*(4n+1) with 4n+1 not the sum of 2 squares.
(End)

Jean-Christophe Hervé, Table of n, a(n) for n = 1..2507

Cf. A022544, A016825, union of A017137 and 2*A084109, complement of A263715.

Cf. A097271, A079299.

N:= 1000: # to get all terms <= N
S:= {seq(4*i+2,i=0..floor((N-2)/4))}
  minus {seq(seq(x^2 + y^2, y = x .. floor(sqrt(N-x^2)),2),x=1..floor(sqrt(N)))}:
sort(convert(S,list)); # Robert Israel, Oct 25 2015

Select[Range@ 360, SquaresR[2, #] == 0 && Mod[#, 4] == 2 &] (* Michael De Vlieger, Oct 26 2015, after Harvey P. Dale at A022544 *)

a(n) == 2 (mod 4). Subsequence of A016825 (non-differences of squares). All first differences are either 4 or 8, each of which occurs infinitely often. - David W. Wilson, Mar 09 2005

Lim_{n->inf} a(n)/n = 4.

More terms from David W. Wilson, Feb 11 2003

A034023 Imprimitively represented by x^2+y^2.

Original entry on oeis.org

4, 8, 9, 16, 18, 20, 25, 32, 36, 40, 45, 49, 50, 52, 64, 68, 72, 80, 81, 90, 98, 100, 104, 116, 117, 121, 125, 128, 136, 144, 148, 153, 160, 162, 164, 169, 180, 196, 200, 208, 212, 225, 232, 234, 242, 244, 245, 250, 256, 260, 261, 272, 288, 289

Offset: 0

N. J. A. Sloane

nonn

Cf. A001481, A008784, A022544, A034024-.

A104271 First element of first run of exactly n consecutive numbers not of form x^2+y^2.

Original entry on oeis.org

3, 6, 42, 21, 75, 91, 186, 378, 3051, 987, 1670, 4182, 6531, 1494, 8435, 9705, 22161, 5166, 16110, 16869, 154709, 57099, 31658, 52394, 401481, 176811, 101350, 105573, 678357, 241883, 501717, 393818, 284003, 685542, 1437354, 1751297, 3225579

Offset: 1

David W. Wilson, Feb 26 2005

nonn

Gives the position of the start of the first run of exactly n consecutive zeros in A004018.

Hugo Pfoertner, Table of n, a(n) for n = 1..122

Cf. A022544, A004018.

A143574 Sum of all distinct squares occurring when partitioning n into two squares.

Original entry on oeis.org

0, 1, 1, 0, 4, 5, 0, 0, 4, 9, 10, 0, 0, 13, 0, 0, 16, 17, 9, 0, 20, 0, 0, 0, 0, 50, 26, 0, 0, 29, 0, 0, 16, 0, 34, 0, 36, 37, 0, 0, 40, 41, 0, 0, 0, 45, 0, 0, 0, 49, 75, 0, 52, 53, 0, 0, 0, 0, 58, 0, 0, 61, 0, 0, 64, 130, 0, 0, 68, 0, 0, 0, 36, 73, 74, 0, 0, 0, 0, 0, 80, 81, 82, 0, 0, 170, 0, 0, 0

Offset: 0

Reinhard Zumkeller, Aug 24 2008

nonn

For n > 0: a(n) = 0 iff A000161(n) = 0: a(A022544(n)) = 0;

A143575 gives numbers m such that a(m) = m.

			A000161(25)=#{5^2+0^2,4^2+3^2}=2: a(25)=25+0+16+9=50;
A000161(26)=#{5^2+1^2}=1: a(16)=25+1=26;
A000161(49)=#{7^2+0^2}=1: a(49)=49+0=49;
A000161(50)=#{7^2+1^2,5^2+5^2}=2: a(50)=49+1+25=75;
A000161(2600)=#{50^2+10^2,46^2+22^2,38^2+34^2}=3: a(2600)=2500+100+2116+484+1444+1156=7800;
A000161(2601)=#{51^2+0^2,45^2+24^2}=2: a(2601)=2601+0+12025+576=5202;
A000161(2602)=#{51^2+1^2}=1: a(2602)=2601+1=2602.

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

Cf. A000161, A002654, A010052, A022544, A143575.

a(n) = sum(k=1, n, if (issquare(k) && issquare(n-k), k)); \\ Michel Marcus, May 16 2023

from sympy import divisors
from sympy.solvers.diophantine.diophantine import cornacchia
def A143574(n):
    c = 0
    for d in divisors(n):
        if (k:=d**2)>n:
            break
        q, r = divmod(n,k)
        if not r:
            c += sum(k*(a[0]**2+(a[1]**2 if a[0]!=a[1] else 0)) for a in cornacchia(1,1,q) or [])
    return c # Chai Wah Wu, May 15 2023

a(n) = Sum_{k=1..n} k*A010052(k)*A010052(n-k). [Reinhard Zumkeller, Sep 27 2008]

A026468 a(1) = 1, a(2) = 2; for n >= 3, a(n) = least positive integer > a(n-1) and not a(i)^2 + a(j)^2 for 1<=i<=j<=n-1.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 9, 11, 12, 14, 15, 16, 19, 21, 22, 23, 24, 26, 27, 28, 29, 30, 31, 33, 34, 35, 36, 38, 39, 41, 42, 43, 44, 46, 47, 48, 49, 51, 54, 55, 56, 57, 59, 60, 61, 62, 63, 64, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78

Offset: 1

Clark Kimberling

nonn

A022544 is a subsequence.

Cf. A026469, A261604.

# return true if 'candid' is allowed (not a sum of squares)
A026469aux := proc(a,candid) local i,j; for j from 1 to nops(a) do for i from 1 to j do if (op(i,a))^2+(op(j,a))^2 = candid then RETURN(false); fi; od; od; RETURN(true); end:
A026468 := proc(nmax) local a,candidat; a := [1,2]; while nops(a) < nmax do candidat := op(nops(a),a)+1; while A026469aux(a,candidat) = false do candidat := candidat+1; od; a := [op(a),candidat]; od: RETURN(a); end: A026468(60); # R. J. Mathar, Nov 01 2006

Definition corrected by Ralf Stephan, Nov 01 2006

A070176 Let s(n) be smallest number >= n which is a sum of two squares (A001481); sequence gives s(n) - n.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, May 13 2002

It is an unsolved problem to determine the rate of growth of this sequence.

a(A001481(n)) = 0; a(A022544(n)) > 0. [Reinhard Zumkeller, Feb 04 2012]

H. L. Montgomery, Ten Lectures on the Interface Between Analytic Number Theory and Harmonic Analysis, Amer. Math. Soc., 1996, p. 208.

T. D. Noe, Table of n, a(n) for n = 0..10000

a070176 n = (head $ dropWhile (< n) a001481_list) - n
a070176_list = map a070176 [0..]
-- Reinhard Zumkeller, Feb 04 2012

sumOfTwoSquaresQ[n_] := With[{r = Ceiling[Sqrt[n]]}, Do[ Which[n == x^2 + y^2, Return[True], x == r && y == r, Return[False]], {x, 0, r}, {y, x, r}]]; a[n_] := For[s = n, True, s++, If[sumOfTwoSquaresQ[s], Return[s - n]]]; Table[a[n], {n, 0, 104}](* Jean-François Alcover, May 23 2012 *)
s2s[n_]:=Module[{i=0},While[SquaresR[2,n+i]==0,i++];i]; Array[s2s,110,0] (* Harvey P. Dale, Jun 16 2012 *)

More terms from Jason Earls, Jun 15 2002

A204384 G.f.: Product_{n>=1} (1 - A002203(n)x^n + (-x^2)^n) / (1 + A002203(n)x^n + (-x^2)^n) where A002203(n) is the companion Pell numbers.

Original entry on oeis.org

1, -4, -4, 0, 68, 56, 0, 0, 4, -5572, -4616, 0, 0, -328, 0, 0, 2663428, 2206456, -4, 0, 156808, 0, 0, 0, 0, -7420309452, -6147187208, 0, 0, -436867144, 0, 0, 4, 0, -5326856, 0, 120491016385604, 99818026262072, 0, 0, 7093848711176, -11144, 0, 0, 0, 86497488056, 0, 0, 0

Offset: 0

Paul D. Hanna, Jan 14 2012

sign

a(A022544(n)) = 0 where A022544 lists numbers that are not the sum of 2 squares.

Compare to: Product_{n>=1} (1-q^k)/(1+q^k) = 1 + 2*Sum_{n>=1} (-1)^n*q^(n^2), the Jacobi theta_4 function, which has the g.f: exp( Sum_{n>=1} -(sigma(2*k)-sigma(k)) * x^n/n ).

			G.f.: A(x) = 1 - 4*x - 4*x^2 + 68*x^4 + 56*x^5 + 4*x^8 - 5572*x^9 - 4616*x^10 +...
-log(A(x)) = 2*2*x + 4*6*x^2/2 + 8*14*x^3/3 + 8*34*x^4/4 + 12*82*x^5/5 + 16*198*x^6/6 +...+ (sigma(2*n)-sigma(n))*A002203(n)*x^n/n +...
Compare to the logarithm of Jacobi theta4 H(x) = 1 + 2*Sum_{n>=1} (-1)^n*q^(n^2):
-log(H(x)) = 2*x + 4*x^2/2 + 8*x^3/3 + 8*x^4/4 + 12*x^5/5 + 16*x^6/6 + 16*x^7/7 +...+ (sigma(2*n)-sigma(n))*x^n/n +...
The g.f. equals the products:
A(x) = (1-2*x-x^2)/(1+2*x-x^2) * (1-6*x^2+x^4)/(1+6*x^2+x^4) * (1-14*x^3-x^6)/(1+14*x^3-x^6) * (1-34*x^4+x^8)/(1+34*x^4+x^8) * (1-82*x^5-x^10)/(1+82*x^5-x^10) *...* (1 - A002203(n)*x^n + (-x^2)^n)/(1 + A002203(n)*x^n + (-x^2)^n) *...
A(x) = (1-2*x-x^2)^2 * (1-6*x^2+x^4) * (1-14*x^3-x^6)^2 * (1-34*x^4+x^8) * (1-82*x^5-x^10)^2 *(1-198*x^6+x^12) * (1-478*x^7-x^14)^2 * (1-1154*x^8+x^16) *...
Positions of zeros form A022544:
[3,6,7,11,12,14,15,19,21,22,23,24,27,28,30,31,33,35,38,39,42,43,44,...]
which are numbers that are not the sum of 2 squares.

Paul D. Hanna, Table of n, a(n) for n = 0..500

Cf. A203850, A204382, A204383, A022544.

/* Subroutine used in PARI programs below: */
{A002203(n)=polcoeff(2*(1-x)/(1-2*x-x^2+x*O(x^n)), n)}

{a(n)=polcoeff(prod(m=1, n, 1 - A002203(m)*x^m + (-1)^m*x^(2*m) +x*O(x^n))/prod(m=1, n, 1 + A002203(m)*x^m + (-1)^m*x^(2*m) +x*O(x^n)), n)}

{a(n)=polcoeff(prod(m=1, n\2+1, (1 - A002203(2*m-1)*x^(2*m-1) - x^(4*m-2))^2*(1 - A002203(2*m)*x^(2*m) + x^(4*m) +x*O(x^n))), n)}

{a(n)=polcoeff(exp(sum(k=1, n,-(sigma(2*k)-sigma(k))*A002203(k)*x^k/k)+x*O(x^n)), n)}

G.f.: Product_{n>=1} (1 - A002203(2*n-1)*x^(2*n-1) - x^(4*n-2))^2 * (1 - A002203(2*n)*x^(2*n) + x^(4*n)).

G.f.: exp( Sum_{n>=1} -(sigma(2*n)-sigma(n)) * A002203(n) * x^n/n ) where A002203(n) is the companion Pell numbers.

A026469 a(1) = 1; for n > 1, a(n) = least positive integer > a(n-1) and not equal to a(i)^2 + a(j)^2 for 1<=i<=j<=n-1.

Original entry on oeis.org

1, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 19, 20, 21, 22, 23, 24, 27, 28, 29, 30, 31, 33, 35, 36, 38, 39, 40, 42, 43, 44, 46, 47, 48, 49, 51, 53, 54, 55, 56, 57, 59, 60, 62, 63, 64, 66, 67, 68, 69, 70, 71, 75, 76, 77, 78, 79

Offset: 1

Clark Kimberling

nonn

A022544 is a subsequence.

Cf. A026468.

# return true if 'candid' is allowed (not a sum of squares)
A026469aux := proc(a,candid) local i,j ; for j from 1 to nops(a) do for i from 1 to j do if (op(i,a))^2+(op(j,a))^2 = candid then RETURN(false) ; fi ; od ; od ; RETURN(true) ; end:
A026469 := proc(nmax) local a,candidat ; a := [1] ; while nops(a) < nmax do candidat := op(nops(a),a)+1 ; while A026469aux(a,candidat) = false do candidat := candidat+1 ; od ; a := [op(a),candidat] ; od: RETURN(a) ; end: A026469(60) ; # R. J. Mathar, Nov 01 2006

Corrected by Franklin T. Adams-Watters, Oct 25 2006

Definition corrected by N. J. A. Sloane, Nov 01 2006

cp's OEIS Frontend

A229062 1 if n is representable as sum of two nonnegative squares, otherwise 0.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Python

Formula

A260728 Bitwise-OR of the exponents of all 4k+3 primes in the prime factorization of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Scheme

Formula

A062316 Neither the sum or difference of 2 squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A034023 Imprimitively represented by x^2+y^2.

Views

Author

Keywords

Crossrefs

A104271 First element of first run of exactly n consecutive numbers not of form x^2+y^2.

Views

Author

Keywords

Comments

Links

Crossrefs

A143574 Sum of all distinct squares occurring when partitioning n into two squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Python

Formula

A026468 a(1) = 1, a(2) = 2; for n >= 3, a(n) = least positive integer > a(n-1) and not a(i)^2 + a(j)^2 for 1<=i<=j<=n-1.

Views

Author

Keywords

Crossrefs

Programs

Maple

Extensions

A070176 Let s(n) be smallest number >= n which is a sum of two squares (A001481); sequence gives s(n) - n.

Views

Author

Keywords

Comments

References

Links

Programs

A204384 G.f.: Product_{n>=1} (1 - A002203(n)x^n + (-x^2)^n) / (1 + A002203(n)x^n + (-x^2)^n) where A002203(n) is the companion Pell numbers.