A178132 Partial sums of A003995.
0, 1, 5, 10, 19, 29, 42, 56, 72, 89, 109, 130, 155, 181, 210, 240, 274, 309, 345, 382, 420, 459, 499, 540, 582, 627, 673, 722, 772, 823, 875, 928, 982, 1037, 1093, 1150, 1208, 1267, 1328, 1390, 1453, 1517, 1582, 1648, 1716, 1785, 1855, 1926, 1999, 2073, 2148
Offset: 0
Examples
a(13) = 0 + 1 + 4 + 5 + 9 + 10 + 13 + 14 + 16 + 17 + 20 + 21 + 25 + 26 = 181 is prime.
Formula
a(n) = SUM[i=0..n] A003995(i) = SUM[i=0..n] (r^2 + s^2 + t^2+ ...) with 0<=r
A033461 Number of partitions of n into distinct squares.
1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 2, 2, 0, 0, 2, 2, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 0, 0, 2, 2, 0, 0, 2, 3, 1, 1, 2, 2, 1, 1, 1, 1, 1, 0, 2, 3, 1, 1, 4, 3, 0, 1, 2, 2, 1, 0, 1, 4, 3, 0, 2, 4, 2, 1, 3, 2, 1, 2, 3, 3, 2, 1, 3, 6, 3, 0, 2, 5, 3, 0, 1, 3, 3, 3, 4
Offset: 0
Comments
"WEIGH" transform of squares A000290.
Number of partitions of n in which each part i has multiplicity i. Example: a(50)=3 because we have [1,2,2,3,3,3,6,6,6,6,6,6], [1,7,7,7,7,7,7,7], and [3,3,3,4,4,4,4,5,5,5,5,5]. - Emeric Deutsch, Jan 26 2016
The Heinz numbers of integer partitions into distinct pairs are given by A324587. - Gus Wiseman, Mar 09 2019
From Gus Wiseman, Mar 09 2019: (Start)
Equivalent to Emeric Deutsch's comment, a(n) is the number of integer partitions of n where the multiplicities (where if x < y the multiplicity of x is counted prior to the multiplicity of y) are equal to the distinct parts in increasing order. The Heinz numbers of these partitions are given by A109298. For example, the first 30 terms count the following integer partitions:
1: (1)
4: (22)
5: (221)
9: (333)
10: (3331)
13: (33322)
14: (333221)
16: (4444)
17: (44441)
20: (444422)
21: (4444221)
25: (55555)
25: (4444333)
26: (555551)
26: (44443331)
29: (5555522)
29: (444433322)
30: (55555221)
30: (4444333221)
The case where the distinct parts are taken in decreasing order is A324572, with Heinz numbers given by A324571.
(End)
Examples
a(50)=3 because we have [1,4,9,36], [1,49], and [9,16,25]. - _Emeric Deutsch_, Jan 26 2016 From _Gus Wiseman_, Mar 09 2019: (Start) The first 30 terms count the following integer partitions: 1: (1) 4: (4) 5: (4,1) 9: (9) 10: (9,1) 13: (9,4) 14: (9,4,1) 16: (16) 17: (16,1) 20: (16,4) 21: (16,4,1) 25: (25) 25: (16,9) 26: (25,1) 26: (16,9,1) 29: (25,4) 29: (16,9,4) 30: (25,4,1) 30: (16,9,4,1) (End)
References
- James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-289.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..10000 (first 1001 terms from T. D. Noe)
- M. Brack, M. V. N. Murthy, and J. Bartel, Application of semiclassical methods to number theory, University of Regensburg (Germany, 2020).
- Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.
- Vaclav Kotesovec, Graph - The asymptotic ratio.
- M. V. N. Murthy, Matthias Brack, Rajat K. Bhaduri, and Johann Bartel, Semi-classical analysis of distinct square partitions, arXiv:1808.05146 [cond-mat.stat-mech], 2018.
Crossrefs
Programs
-
Maple
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0, b(n, i-1) +`if`(i^2>n, 0, b(n-i^2, i-1)))) end: a:= n-> b(n, isqrt(n)): seq(a(n), n=0..100); # Alois P. Heinz, May 14 2014
-
Mathematica
nn=10; CoefficientList[Series[Product[(1+x^(k*k)), {k,nn}], {x,0,nn*nn}], x] (* T. D. Noe, Jul 24 2006 *) b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i^2 > n, 0, b[n - i^2, i-1]]]]; a[n_] := b[n, Floor[Sqrt[n]]]; Table[a[n], {n, 0, 100}] (* Jean-François Alcover, Sep 21 2015, after Alois P. Heinz *) nmax = 20; poly = ConstantArray[0, nmax^2 + 1]; poly[[1]] = 1; poly[[2]] = 1; Do[Do[poly[[j + 1]] += poly[[j - k^2 + 1]], {j, nmax^2, k^2, -1}];, {k, 2, nmax}]; poly (* Vaclav Kotesovec, Dec 09 2016 *) Table[Length[Select[IntegerPartitions[n],Reverse[Union[#]]==Length/@Split[#]&]],{n,30}] (* Gus Wiseman, Mar 09 2019 *)
-
PARI
a(n)=polcoeff(prod(k=1,sqrt(n),1+x^k^2), n)
-
PARI
first(n)=Vec(prod(k=1,sqrtint(n),1+'x^k^2,O('x^(n+1))+1)) \\ Charles R Greathouse IV, Sep 03 2015
-
Python
from functools import cache from sympy.core.power import isqrt @cache def b(n,i): # Code after Alois P. Heinz if n == 0: return 1 if i == 0: return 0 i2 = i*i return b(n, i-1) + (0 if i2 > n else b(n - i2, i-1)) a = lambda n: b(n, isqrt(n)) print([a(n) for n in range(1, 101)]) # Darío Clavijo, Nov 30 2023
Formula
G.f.: Product_{n>=1} ( 1+x^(n^2) ).
a(n) ~ exp(3 * 2^(-5/3) * Pi^(1/3) * ((sqrt(2)-1)*zeta(3/2))^(2/3) * n^(1/3)) * ((sqrt(2)-1)*zeta(3/2))^(1/3) / (2^(4/3) * sqrt(3) * Pi^(1/3) * n^(5/6)), where zeta(3/2) = A078434. - Vaclav Kotesovec, Dec 09 2016
See Murthy, Brack, Bhaduri, Bartel (2018) for a more complete asymptotic expansion. - N. J. A. Sloane, Aug 17 2018
Extensions
More terms from Michael Somos
A001422 Numbers which are not the sum of distinct squares.
2, 3, 6, 7, 8, 11, 12, 15, 18, 19, 22, 23, 24, 27, 28, 31, 32, 33, 43, 44, 47, 48, 60, 67, 72, 76, 92, 96, 108, 112, 128
Offset: 1
Comments
This is the complete list (Sprague).
References
- S. Lin, Computer experiments on sequences which form integral bases, pp. 365-370 of J. Leech, editor, Computational Problems in Abstract Algebra. Pergamon, Oxford, 1970.
- Harry L. Nelson, The Partition Problem, J. Rec. Math., 20 (1988), 315-316.
- J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 222.
Links
- R. E. Dressler and T. Parker, 12,758, Math. Comp. 28 (1974), 313-314.
- T. Sillke, Not the sum of distinct squares
- R. Sprague, Über Zerlegungen in ungleiche Quadratzahlen, Math. Z. 51, (1948), 289-290.
- Eric Weisstein's World of Mathematics, Square Number.
- Index entries for sequences related to sums of squares
Crossrefs
Programs
-
Mathematica
nn=50; t=Rest[CoefficientList[Series[Product[(1+x^(k*k)), {k,nn}], {x,0,nn*nn}], x]]; Flatten[Position[t,0]] (* T. D. Noe, Jul 24 2006 *)
-
PARI
select( is_A001422(n,m=n)={m^2>n&& m=sqrtint(n); n!=m^2&&!while(m>1,isSumOfSquares(n-m^2,m--)&&return)}, [1..128]) \\ M. F. Hasler, Apr 21 2020
A004432 Numbers that are the sum of 3 distinct nonzero squares.
14, 21, 26, 29, 30, 35, 38, 41, 42, 45, 46, 49, 50, 53, 54, 56, 59, 61, 62, 65, 66, 69, 70, 74, 75, 77, 78, 81, 83, 84, 86, 89, 90, 91, 93, 94, 98, 101, 104, 105, 106, 107, 109, 110, 113, 114, 115, 116, 117, 118, 120, 121, 122, 125, 126, 129, 131, 133
Offset: 1
Comments
Numbers that can be written as a(n) = x^2 + y^2 + z^2 with 0 < x < y < z.
This is a subsequence (equal to the range) of A024803. As a set, it is the union of A025339 and A024804, subsequences of numbers having exactly one, resp. more than one, such representations. - M. F. Hasler, Jan 25 2013
Conjecture: a number n is a sum of 3 squares, but not a sum of 3 distinct nonzero squares (i.e., is in A004432 but not A000408), if and only if it is of the form 4^j*s, where j >= 0 and s in {1, 2, 3, 5, 6, 9, 10, 11, 13, 17, 18, 19, 22, 25, 27, 33, 34, 37, 43, 51, 57, 58, 67, 73, 82, 85, 97, 99, 102, 123, 130, 163, 177, 187, 193, 267, 627, 697}. - Jeffrey Shallit, Jan 15 2017
4*a(n) gives the sums of 3 distinct nonzero even squares. - Wesley Ivan Hurt, Apr 05 2021
Examples
14 = 1^2 + 2^2 + 3^2; 62 = 1^2 + 5^2 + 6^2.
Links
Crossrefs
Programs
-
Haskell
a004432 n = a004432_list !! (n-1) a004432_list = filter (p 3 $ tail a000290_list) [1..] where p k (q:qs) m = k == 0 && m == 0 || q <= m && k >= 0 && (p (k - 1) qs (m - q) || p k qs m) -- Reinhard Zumkeller, Apr 22 2013
-
Mathematica
f[upto_]:=Module[{max=Floor[Sqrt[upto]]},Select[Union[Total/@ (Subsets[ Range[ max],{3}]^2)],#<=upto&]]; f[150] (* Harvey P. Dale, Mar 24 2011 *)
-
PARI
is_A004432(n)=for(x=1,sqrtint(n\3),for(y=x+1,sqrtint((n-1-x^2)\2),issquare(n-x^2-y^2)&return(1))) \\ M. F. Hasler, Feb 02 2013
Formula
A004432 = { x^2 + y^2 + z^2; 0 < x < y < z }.
A004433
Numbers that are the sum of 4 distinct nonzero squares: of form w^2+x^2+y^2+z^2 with 0
30, 39, 46, 50, 51, 54, 57, 62, 63, 65, 66, 70, 71, 74, 75, 78, 79, 81, 84, 85, 86, 87, 90, 91, 93, 94, 95, 98, 99, 102, 105, 106, 107, 109, 110, 111, 113, 114, 116, 117, 118, 119, 120, 121, 122, 123, 125, 126, 127, 129, 130, 131, 133, 134, 135, 137
Offset: 1
Examples
30 = 1^2+2^2+3^2+4^2.
Links
Crossrefs
Programs
-
Haskell
a004433 n = a004433_list !! (n-1) a004433_list = filter (p 4 $ tail a000290_list) [1..] where p k (q:qs) m = k == 0 && m == 0 || q <= m && k >= 0 && (p (k - 1) qs (m - q) || p k qs m) -- Reinhard Zumkeller, Apr 22 2013
-
Mathematica
data = Flatten[ DeleteCases[ FindInstance[ w^2 + x^2 + y^2 + z^2 == # && 0 < w < x < y < z < #, {w, x, y, z}, Integers] & /@ Range[137], {}], 1]; w^2 + x^2 + y^2 + z^2 /. data (* Ant King, Oct 17 2010 *) Select[Union[Total[#^2]&/@Subsets[Range[10],{4}]],#<=137&] (* Harvey P. Dale, Jul 03 2011 *)
-
PARI
list(lim)=my(v=List([30, 39, 46, 50, 51, 54, 57, 62, 63, 65, 66, 70, 71, 74, 75, 78, 79, 81, 84, 85, 86, 87, 90, 91, 93, 94, 95, 98, 99, 102, 105, 106, 107, 109, 110, 111, 113, 114, 116, 117, 118, 119, 120, 121, 122, 123, 125, 126, 127, 129, 130, 131, 133, 134, 135, 137, 138, 139, 140, 141, 142, 143, 145, 146, 147, 149, 150, 151, 153, 154, 155, 156]), u=[160, 168, 172, 176, 188, 192, 208, 220, 224, 232, 240, 256, 268, 272, 288, 292, 304, 320, 328, 352, 368, 384, 388, 400, 412, 416, 432, 448, 496, 512, 528, 544, 576, 592, 608], t=1); if(lim<156, return(select(k->k<=lim, Vec(v)))); for(n=158,lim\1, if(n#u, t=1)); Vec(v) \\ Charles R Greathouse IV, Jan 08 2025
Formula
a(n) = n + O(log n). - Charles R Greathouse IV, Jan 08 2025
A097563 Least integer that can be written as a sum of zero or more distinct squares in exactly n ways, or -1 if no such number exists.
2, 0, 25, 50, 65, 94, 90, 110, 155, 126, 191, 170, 186, 174, 190, 211, 195, 226, 210, 231, 234, 235, 332, 255, 283, 259, 274, 275, 270, 323, 310, 286, 306, 299, 330, 381, 295, 347, 334, 319, 315, 331, 405, 339, 335, 364, 359, 351, 367, 387, 371, 370, 404, 438
Offset: 0
Comments
a(n) = -1 for almost all n. Conjecture: for n > 34189857569982621, this sequence is the integers > 37163, in order, interspersed with -1s. - Charles R Greathouse IV, Sep 04 2015
Examples
a(4) = 65 because we can write 65 as a sum of distinct squares in four ways: 65 = 8^2 + 1^2 = 7^2 + 4^2 = 6^2 + 5^2 + 2^2 = 6^2 + 4^2 + 3^2 + 2^2 and we cannot do this with any smaller integer. a(0) = 2 because we cannot write 2 as a sum of distinct squares and it is the smallest number with this property.
Links
- Charles R Greathouse IV, Table of n, a(n) for n = 0..10000
Programs
-
Maple
gf := product(1+x^F(k), k=1..31); ser := series(gf, x=0, 1001); S := [seq(coeff(ser,x^(1*i)),i=1..1000)]; A := proc(i); x := 0; for j from 1 to nops(a) while x = 0 do > if a[j] = i then x := 1; fi; od; j-1; end; seq(A(n), n=1..67);
Extensions
Edited by Ray Chandler, Sep 01 2004
A003997 Sums of distinct positive cubes.
1, 8, 9, 27, 28, 35, 36, 64, 65, 72, 73, 91, 92, 99, 100, 125, 126, 133, 134, 152, 153, 160, 161, 189, 190, 197, 198, 216, 217, 224, 225, 243, 244, 251, 252, 280, 281, 288, 289, 307, 308, 315, 316, 341, 342, 343, 344, 349, 350, 351, 352, 368, 369, 370, 371
Offset: 1
Comments
12758 is the largest of 2788 positive integers not in this sequence. - Jud McCranie, Dec 11 1999
References
- D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, entry 12758.
Links
- T. D. Noe, Table of n, a(n) for n = 1..10000
- R. Sprague, Über Zerlegungen in n-te Potenzen mit lauter verschiedenen Grundzahlen, Math. Z. 51, (1948), 466-468.
- Index entries for linear recurrences with constant coefficients, signature (2,-1).
Programs
-
Maple
GF := series( (1+x)*(1+x^8)*(1+x^27)*(1+x^64)*(1+x^125)*(1+x^216)*(1+x^343)*(1+x^512)*(1+x^729)*(1+x^1000), x, 11^3); # Edited by M. F. Hasler, May 01 2020 A003997_upto := n -> map(degree,{op(convert(series(product(1 + x^(k^3), k = 1 .. floor(root(n,3)))-1, x, n+1),`+`))}); # M. F. Hasler, May 01 2020;
-
Mathematica
lim = 8; s = {0}; Do[s = Union[s, s + n^3], {n, lim}]; Select[s, 0 < # <= lim^3 &] (* T. D. Noe, Jul 10 2012 *)
-
PARI
list(lim)={ lim\=1; my(lm=min(lim+1,12758), v=List(), P); P=prod(n=1,lm^(1/3),1+x^(n^3),1+O(x^lm)); for(n=1,lm-1,if(polcoeff(P,n),listput(v,n))); if(lim>12758,concat(Vec(v),vector(lim-12758,i,i+12758)),Vec(v)) }; \\ Charles R Greathouse IV, Sep 02 2011
-
PARI
select( is_A003997(n,m=n)={m^3>n&&m=sqrtnint(n,3);n==m^3||while(m>1,is_A003997(n-m^3,m--)&&return(1))}, [1..400]) \\ M. F. Hasler, Apr 21 2020
Formula
For n > 9970, a(n) = n + 2788. - Charles R Greathouse IV, Sep 02 2011
Extensions
Definition clarified by Jeppe Stig Nielsen, Jan 27 2015
A004434 Numbers that are the sum of 5 distinct nonzero squares.
55, 66, 75, 79, 82, 87, 88, 90, 94, 95, 99, 100, 103, 106, 110, 111, 114, 115, 118, 120, 121, 123, 126, 127, 129, 130, 131, 132, 134, 135, 138, 139, 142, 143, 144, 145, 146, 147, 148, 150, 151, 152, 154, 155, 156, 157, 158, 159, 160, 162, 163
Offset: 1
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
- Paul T. Bateman, Adolf J. Hildebrand, and George B. Purdy, Sums of distinct squares, Acta Arithmetica 67 (1994), pp. 349-380.
- Franz Halter-Koch, Darstellung natürlicher Zahlen als Summe von Quadraten, Acta Arithmetica 42 (1982), pp. 11-20.
- Index entries for sequences related to sums of squares
- Index entries for linear recurrences with constant coefficients, signature (2,-1).
Programs
-
Haskell
a004434 n = a004434_list !! (n-1) a004434_list = filter (p 5 $ tail a000290_list) [1..] where p k (q:qs) m = k == 0 && m == 0 || q <= m && k >= 0 && (p (k - 1) qs (m - q) || p k qs m) -- Reinhard Zumkeller, Apr 22 2013
-
PARI
upto(lim)=my(v=List(), tb, tc, td, te); for(a=5, sqrt(lim), for(b=4, min(a-1, sqrt(lim-a^2)), tb=a^2+b^2; for(c=3, min(b-1, sqrt(lim-tb)), tc=tb+c^2; for(d=2, min(c-1, sqrt(lim-tc)), td=tc+d^2; for(e=1, d-1, te=td+e^2; if(te>lim, break,listput(v, te))))))); vecsort(Vec(v), , 8) \\ Charles R Greathouse IV, Jul 17 2011
Formula
a(n) = n + 124 for n > 121. - Charles R Greathouse IV, Jul 17 2011
A224981 Numbers that are the sum of exactly 6 distinct nonzero squares.
91, 104, 115, 119, 124, 130, 131, 136, 139, 143, 146, 147, 151, 152, 154, 155, 156, 159, 160, 163, 164, 166, 167, 168, 169, 170, 171, 175, 176, 178, 179, 180, 181, 182, 184, 187, 188, 190, 191, 192, 194, 195, 196, 199, 200, 201, 202, 203, 204, 206, 207, 208
Offset: 1
Keywords
Examples
a(1) = 1 + 4 + 9 + 16 + 25 + 36 = 91 = A000330(6); a(2) = 1 + 4 + 9 + 16 + 25 + 49 = 104; a(3) = 1 + 4 + 9 + 16 + 36 + 49 = 115; a(4) = 1 + 4 + 9 + 16 + 25 + 64 = 119; a(5) = 1 + 4 + 9 + 25 + 36 + 49 = 124.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
- Paul T. Bateman, Adolf J. Hildebrand, and George B. Purdy, Sums of distinct squares, Acta Arithmetica 67 (1994), pp. 349-380.
- Index entries for sequences related to sums of squares
Programs
-
Haskell
a224981 n = a224981_list !! (n-1) a224981_list = filter (p 6 $ tail a000290_list) [1..] where p k (q:qs) m = k == 0 && m == 0 || q <= m && k >= 0 && (p (k - 1) qs (m - q) || p k qs m)
-
Mathematica
nmax = 1000; S[n_] := S[n] = Union[Total /@ Subsets[ Range[Floor[Sqrt[n]]]^2, {6}]][[1 ;; nmax]]; S[nmax]; S[n = nmax + 1]; While[S[n] != S[n - 1], n++]; S[n] (* Jean-François Alcover, Nov 20 2021 *)
A224982 Numbers that are the sum of exactly 7 distinct nonzero squares.
140, 155, 168, 172, 179, 185, 188, 191, 195, 196, 200, 203, 204, 205, 211, 212, 215, 217, 219, 220, 224, 225, 227, 230, 231, 232, 233, 235, 236, 239, 240, 243, 244, 245, 246, 247, 248, 251, 252, 254, 256, 257, 259, 260, 263, 264, 265, 267, 268, 269, 270, 271
Offset: 1
Keywords
Examples
a(1) = 1 + 4 + 9 + 16 + 25 + 36 + 49 = 140 = A000330(7); a(2) = 1 + 4 + 9 + 16 + 25 + 36 + 64 = 155; a(3) = 1 + 4 + 9 + 16 + 25 + 49 + 64 = 168; a(4) = 1 + 4 + 9 + 16 + 25 + 36 + 81 = 172; a(5) = 1 + 4 + 9 + 16 + 36 + 49 + 64 = 179.
Links
- Reinhard Zumkeller, Table of n, a(n) for n = 1..1000
- Paul T. Bateman, Adolf J. Hildebrand, and George B. Purdy, Sums of distinct squares, Acta Arithmetica 67 (1994), pp. 349-380.
- Index entries for sequences related to sums of squares
Programs
-
Haskell
a224982 n = a224982_list !! (n-1) a224982_list = filter (p 7 $ tail a000290_list) [1..] where p k (q:qs) m = k == 0 && m == 0 || q <= m && k >= 0 && (p (k - 1) qs (m - q) || p k qs m)
-
Mathematica
nmax = 1000; S[n_] := S[n] = Union[Total /@ Subsets[ Range[Floor[Sqrt[n]]]^2, {7}]][[1 ;; nmax]]; S[nmax]; S[n = nmax + 1]; While[S[n] != S[n - 1], n++]; S[n] (* Jean-François Alcover, Nov 20 2021 *)
Comments