Moshe Shmuel Newman - cp's OEIS frontend

A241898 a(n) is the largest integer such that n = a(n)^2 + ... is a decomposition of n into a sum of at most four nondecreasing squares.

1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 2, 2, 1, 1, 4, 2, 3, 1, 2, 2, 2, 1, 2, 5, 2, 3, 2, 2, 1, 2, 4, 2, 3, 1, 6, 2, 2, 1, 2, 4, 2, 3, 2, 3, 1, 2, 4, 7, 5, 1, 4, 2, 3, 1, 2, 4, 3, 3, 2, 5, 2, 3, 8, 4, 4, 3, 4, 2, 3, 2, 6, 4, 5, 5, 3, 4, 2, 3, 4, 9, 4, 3, 4, 6, 5, 2

Offset: 1

Moshe Shmuel Newman, May 15 2014

This differs from A191090 only for n>=30 because 30 cannot be written as a sum of at most four squares without using 1^2, but 30 can be written as a sum of five nondecreasing squares: 2^2 + 2^2 + 2^2 + 3^2 + 3^2, making A191090(30)=2.

By Lagrange's Theorem every number can be written as a sum of four squares. Can the same be said of the set of {a^2|a is any integer not equal to 7}? From the data that I have, it would seem that a(n) is greater than 7 for all n>599. If this could be proved, it would only remain to check if all the numbers up to 599 can be written as the sum of 4 squares none of which is 7^2.

			30 can be written as the sum of at most 4 nondecreasing squares in the following ways: 1^2 + 2^2 + 5^2 or 1^2 + 2^2 + 3^2 + 4^2. Therefore, a(30)=1.

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A191090.

b:= proc(n, i, t) option remember; n=0 or t>0 and
       i^2<=n and (b(n, i+1, t) or b(n-i^2, i, t-1))
    end:
a:= proc(n) local k;
      for k from isqrt(n) by -1 do
        if b(n, k, 4) then return k fi
      od
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, May 25 2014

For[i=0,i<=7^4,i++,a[i]={}];
For[i1=0,i1<=7,i1++,
For[i2=0,i2<=7,i2++,
For[i3=0,i3<=7,i3++,
For[i4=0,i4<=7,i4++,
sumOfSquares=i1^2+i2^2+i3^2+i4^2;
smallestSquare=Min[DeleteCases[{i1,i2,i3,i4},0]];
a[sumOfSquares]=Union[{smallestSquare},a[sumOfSquares]] ]]]];
Table[Max[a[i]],{i,1,50}]

A232832 Shortest composition length for a finite solvable group of derived length n.

Original entry on oeis.org

1, 2, 4, 5, 7, 8, 13, 15

Offset: 1

Moshe Shmuel Newman, Nov 30 2013

The composition length of a finite solvable group is equal to the number of prime factors of the order, counting multiplicities. Thus, for example, the symmetric group of permutations on 4 elements is a solvable group of derived length 3, and its order is 24=2*2*2*3 which has 4 prime divisors. This is the smallest possible number of factors for a solvable group of derived length 3, so a(3) = 4.

The sequences is monotonic increasing, and the difference cannot be 1 twice in a row. Thus the smallest possible differences are 1,2,1,2.., which is what we see for the first 5 differences. The sixth difference is 5 which breaks that pattern. Glasby shows that a(n) grows exponentially, with exponent at least 1.3, so in the long run the differences must often be very large. However, it seems that the difference 1 may show up infinitely often.

S. P. Glasby, Solvable groups with a given solvable length, and minimal composition length, Journal of Group Theory, vol 8, issue 3, May 2005

Cf. A104114.

A179822 Maximally refined partitions into distinct parts (of any natural number) with largest part n.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 12, 16, 26, 37, 58, 79, 128, 171, 271, 376, 576, 783, 1239, 1654, 2567, 3505, 5382, 7245, 11247, 15036, 23187, 31370, 47672, 64146, 98887, 131784, 201340, 271350, 412828, 551744, 843285, 1125417, 1715207, 2299452, 3479341, 4654468, 7090529

Offset: 0

Moshe Shmuel Newman, Jan 10 2011

nonn

For the definition, see sequence A179009. This sequence counts the same objects using a different statistic, the largest part rather than the sum of the parts.

a(n) is the number of subsets of {1..n-1} containing the sum of any two distinct elements whose sum is <= n. This differs from A326080 in that the set may not contain n itself. These sets are the complements of the set of parts in the first definition. - Andrew Howroyd, Apr 13 2021

			The partitions counted by n=4 are:
  4+1, 4+2+1, 4+3+1, 4+3+2, 4+3+2+1.
The partitions counted by n=5 are:
  5+2+1, 5+3+1, 5+3+2+1, 5+4+2+1, 5+4+3+1, 5+4+3+2, 5+4+3+2+1.

Cf. A179009, A179817, A326080.

a(n)={
  my(ok(k,b)=for(i=1, (k-1)\2, if(bittest(b,i) && bittest(b,k-i), return(0))); 1);
  my(recurse(k,b)=if(k==n, ok(k,b), self()(k+1, bitor(b,1<Andrew Howroyd, Apr 13 2021

a(19)-a(42) from Andrew Howroyd, Apr 13 2021

A179817 Maximally refined partitions into distinct parts (of any natural number) with n parts.

Original entry on oeis.org

1, 2, 4, 8, 14, 27, 48, 86, 151, 269, 460, 808, 1386, 2372, 4048, 6890, 11661, 19719, 33167, 55705, 93288, 155954, 260040, 432895, 719252, 1192989, 1975724, 3267513, 5396171, 8900534, 14663096

Offset: 0

Moshe Shmuel Newman, Jan 10 2011

For the definition, see sequence A179009. This sequence counts the same objects using a different statistic, the number of parts rather than their sum.

			For n=2, the partitions being counted are:
  2+1, 3+1, 4+1, 3+2.
For n=3, the partitions are:
  3+2+1, 4+2+1, 5+2+1, 6+2+1,
  4+3+1, 5+3+1, 6+4+1, 4+3+2.

Cf. A179009, A179822.

ok(k,b)={for(i=1, (k-1)\2, if(bittest(b,i) && bittest(b,k-i), return(0))); 1}
a(n)={((k,w,b)->if(w==n, 1, if(k<=2*w+1, self()(k+1, w, bitor(b,1<Andrew Howroyd, Apr 14 2021

a(0)=1 prepended and a(19)-a(30) from Andrew Howroyd, Apr 14 2021

A140348 Growth function for the submonoid generated by the generators of the free nil-2 group on three generators.

Original entry on oeis.org

1, 3, 9, 27, 78, 216, 568, 1410, 3309, 7307, 15303

Offset: 0

David S. Newman and Moshe Shmuel Newman, May 29 2008

The process of expressing a word in generators as a sorted word in generators and commutators is Marshall Hall's 'collection process'.
Since this monoid 'lives in' a nilpotent group, it inherits the growth restriction of a nilpotent group. So according to a result of Bass, a(n) = O( n^8).
It seems this is the correct growth rate. This sequence may well have a rational generating function, though, according to a result of M Stoll, the growth function of a nilpotent group need not be rational, or even algebraic.
Computations on a free nilpotent group, or on submonoids, may be aided by using matricies. I. D. MacDonald describes how to do this in an American Mathematical Monthly article and he gives a recipe explicitly for the nil-2, 3 generator case.

			Suppose the generators are a,b,c and their commutators are q,r,s, so:
ba = abq, ca = acr, cb = bcs;
nil-2 means that q,r,s commute with everything.
Now there are 81 different words of length 4 on a,b,c, but there are three equations:
abba = baab ( = aabbqq)
acca = caac ( = aaccrr)
bccb = cbbc ( = bbccss)
and these are the only equations, so instead of 81 distinct words we have 78 distinct words, a(4)=78.

H. Bass, The degree of polynomial growth of finitely generated nilpotent groups, Proc. London Math. Soc. 25 (1972).
I. D. MacDonald, Commutators and Their Products, The American Mathematical Monthly, Vol. 93, No. 6, (Jun. - Jul., 1986), pp. 440-444.
Michael Stoll, Rational and transcendental growth series for the higher Heisenberg groups, Inventiones Mathematicae Volume 126, Number 1 / September, 1996.

Cf. sequence A000125 gives the analogous count for the 2 generator case. sequence A077028 refines A000125 by giving the number of words with k a's and (n-k)b's.

A139561 Growth function for the relatively free monoid on three generators with identity xyzyx = yxzxy.

Original entry on oeis.org

1, 3, 9, 27, 78, 216, 568, 1416, 3327

Offset: 0

David S. Newman and Moshe Shmuel Newman, Jun 10 2008

nonn

A semigroup which satisfies the identity xyzyx=yxzxy is called nilpotent of class 2 in the Malcev sense. Initially this sequence looks very like A140348, which counts the words that are distinct in the free nil-2 group.
The sequences first differ at n=7, where there are six equations that hold for the group but do not follow from the Malcev identity, e.g. abccaab = caabbca. Cancellation is not assumed and does not hold, so despite the fact that the former equation does not follow from the Malcev identity, aabccaab = acaabbca does follow.
Shneerson has shown that this sequence grows roughly like some power of n^logn . Contrast to A140348, which has polynomial growth.

			Substituting x->a, y->b, z->1 in the identity gives abba=baab, this is the smallest example.
Substituting x->ab, y->b, z->c in the identity gives abbcbab=babcabb.

L. M. Shneerson, Relatively free semigroups of intermediate growth, J. Algebra, 235 (2001) 484-546.

Cf. A140348.

A135998 Smallest error in trying to solve n^3 = x^3 + y^3. That is, for each n, find positive integers x <= y < n such that | n^3 - x^3 - y^3 | is minimal and let a(n) := n^3 - x^3 - y^3.

Original entry on oeis.org

6, 11, 10, -3, 27, 2, 44, 1, -24, -12, -1, -43, 16, -81, -8, -28, 8, 19, -29, 54, 56, 71, -8, 64, 69, 27, 72, -46, -133, 47, -64, 161, -8, 79, -27, -99, -57, -263, -133, 8, 254, -62, -155, 109, -15, -56, -64, 2, 259, 107, -17, 269, 216, -78, -20, 316, 164, -28, -27, 333, 181, 47, -70, 6, 704, 63, -64, 253, 343, -389, -216

Offset: 2

Moshe Shmuel Newman, Mar 03 2008

sign

a(n) is never zero, by Fermat's last theorem for cubes. There are infinitely many n for which a(n) = 1, -1 and 2. It is not known if a(n) is ever 3, besides a(5). By congruence considerations, a(n) is never +-4 mod 9. Presumably a(n) is roughly of order n.

The current definition leaves an abiguity when there is (x,y) and (x',y') that yield the same minimal difference but with opposite sign, e.g., for n = 994 or n = 1700, see examples. The sign of a(n) is currently not well defined in that case. - M. F. Hasler, Feb 03 2024

			a(7) = 2 because 7^3 - 5^3 - 6^3 = 2 and this can't be improved,
a(12) = -1 because 12^3 - 9^3 - 10^3 = -1 and this can't be improved.
From _M. F. Hasler_, Feb 03 2024: (Start)
a(994) = +- 1503 because 994^3 - 718^3 - 849^3 = 1503, 994^3 - 496^3 - 951^3 = -1503, and there is no smaller difference in absolute value.
a(1700) = +- 3375 because 1700^3 - 1070^3 - 1545^3 = 3375, 1700^3 - 719^3 - 1656^3 = -3375, and these are minimal in absolute value. (End)

Daniel Bernstein, Representations using three cubes.

Cf. A308834 (equivalent for 4th powers).

a[n_] := SortBy[n^3-Flatten[Table[x^3+y^3, {x, n-1}, {y, x}]], Abs][[1]];
Table[a[n], {n, 2, 72}] (* Jean-François Alcover, Jul 05 2019, after Giovanni Resta in A308834 *)

A135998(n, p=3) = { my(np=n^p, m=np); for(y=max(sqrtnint(np\2, p), 1), n-1, my(x = sqrtnint(np - y^p, p), dy = np-y^p, d = if(dy-x^p > (x+1)^p-dy && x < n-1, dy-(x+1)^p, dy-x^p)); abs(d) < abs(m) && abs(m=d) < 2 && break); m} \\ M. F. Hasler, Feb 03 2024

A126683 Number of partitions of the n-th triangular number n(n+1)/2 into distinct odd parts.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 8, 16, 33, 68, 144, 312, 686, 1523, 3405, 7652, 17284, 39246, 89552, 205253, 472297, 1090544, 2525904, 5867037, 13663248, 31896309, 74628130, 174972341, 411032475, 967307190, 2280248312, 5383723722, 12729879673, 30141755384, 71462883813

Offset: 0

Moshe Shmuel Newman, Feb 15 2007

nonn

Also the number of self-conjugate partitions of the n-th triangular number.

			The 5th triangular number is 15. Writing this as a sum of distinct odd numbers: 15 = 11 + 3 + 1 = 9 + 5 + 1 = 7 + 5 + 3 are all the possibilities. So a(5) = 4.

Alois P. Heinz, Table of n, a(n) for n = 0..200

Sequences A066655 and A104383 do the same thing for triangular numbers, with partitions or distinct partitions. Sequences A072213 and A072243 are analogs for squares rather than triangular numbers.

Cf. A000217.

g:= mul(1+x^(2*j+1),j=0..900): seq(coeff(g,x,n*(n+1)/2),n=0..40); # Emeric Deutsch, Feb 27 2007
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i^2n, 0, b(n-2*i+1, i-1))))
    end:
a:= n-> b(n*(n+1)/2, ceil(n*(n+1)/4)*2-1):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 31 2018

a[n_] := SeriesCoefficient[QPochhammer[-x, x^2], {x, 0, n*(n+1)/2}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, May 25 2018 *)

More terms from Emeric Deutsch, Feb 27 2007

a(0)=1 prepended by Alois P. Heinz, Jan 31 2018

A119712 a(n) is the smallest integer k such that the n-th (forward) difference of the partition sequence A000041 is positive from k onwards.

Original entry on oeis.org

0, 1, 6, 23, 64, 129, 222, 345, 502, 695, 924, 1193, 1502, 1853, 2246, 2687, 3172, 3705, 4286, 4917, 5600, 6333, 7118, 7957, 8848, 9797, 10800, 11861, 12978, 14153, 15386, 16681, 18034, 19447, 20922, 22459, 24060, 25723, 27448, 29239, 31094, 33015

Offset: 0

Moshe Shmuel Newman, Jun 11 2006

nonn

The first entry is considered to be indexed by zero. For example, the third difference A072380 starts with -1,1 and continues alternating in sign till the 24th entry, from which point it is positive.

Using a different (backward) definition of the difference operator, this sequence has also been given as 1, 8, 26, 68, 134, 228, 352, ... A155861.

Jean-François Alcover, Table of n, a(n) for n = 0..60
Gert Almkvist, On the differences of the partition function, Acta Arith., 61.2 (1992), 173-181.
I. J. Good, Problem 6137, American Mathematical Monthly, 1978, pages 830-831.
Hansraj Gupta, Finite Differences of the Partition Function, Math. Comp. 32 (1978), 1241-1243.
A. M. Odlyzko, Differences of the partition function, Acta Arithmetica 49.3 (1988): 237-254.
Eric Weisstein's World of Mathematics, Forward Difference.

Cf. A000041, A002865, A053445, A072380, A081094, A081095, A175804, A155861.

with(combinat): DD:= proc(p) proc(n) option remember; p(n+1) -p(n) end end: a:= proc(n) option remember; local f, k; if n=0 then 0 else f:= (DD@@n)(numbpart); for k from a(n-1) while not (f(k)>0 and f(k+1)>0) do od; k fi end: seq(a(n), n=0..20); # Alois P. Heinz, Jul 20 2009

a[n_] := a[n] = Module[{f}, f[i_] = DifferenceDelta[PartitionsP[i], {i, n}]; For[j = 2, True, j++, If[f[j] > 0 && f[j+1] > 0, Return[j]]]];
a[0] = 0; a[1] = 1;
Table[Print[n, " ", a[n]]; a[n], {n, 0, 60}] (* Jean-François Alcover, Dec 04 2020 *)

Odlyzko gives an asymptotic formula a(n)~(6/(Pi)^2) * (n log n)^2

a(11)-a(41) from Alois P. Heinz, Jul 20 2009

A118814 Number of 'tree-like curves' with n intersection points.

Original entry on oeis.org

1, 2, 5, 18, 70, 323, 1683, 9690, 59917, 388894, 2606742, 17869870, 124516636, 878591340

Offset: 0

Moshe Shmuel Newman, May 23 2006

The objects being enumerated are a subset of those enumerated by A008983. The restriction involved is that the Gauss diagram (or chord diagram) has no intersecting chords.

			The first 3 entries are the same as A008983 because, for less than 3 intersection points, all curves are tree-like. For 3 intersection points there are only 2 curves that are not tree-like. They appear as the 4th and 15th entries in the table for n=3, on page 14 of Arnold's book.

V. I. Arnold, Topological Invariants of plane curves and caustics, AMS, 1994, page 12.

Andrei Zabolotskii, closed_curves - a program computing the sequence (2025).

Cf. A008983.

a(5)-a(11) from Andrei Zabolotskii, Jan 16 2025

a(12)-a(13) from Andrei Zabolotskii, Aug 15 2025

cp's OEIS Frontend

User: Moshe Shmuel Newman

A241898 a(n) is the largest integer such that n = a(n)^2 + ... is a decomposition of n into a sum of at most four nondecreasing squares.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A232832 Shortest composition length for a finite solvable group of derived length n.

Views

Author

Keywords

Comments

Links

Crossrefs

A179822 Maximally refined partitions into distinct parts (of any natural number) with largest part n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A179817 Maximally refined partitions into distinct parts (of any natural number) with n parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Extensions

A140348 Growth function for the submonoid generated by the generators of the free nil-2 group on three generators.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A139561 Growth function for the relatively free monoid on three generators with identity xyzyx = yxzxy.

Views

Author

Keywords

Comments

Examples

References

Crossrefs

A135998 Smallest error in trying to solve n^3 = x^3 + y^3. That is, for each n, find positive integers x <= y < n such that | n^3 - x^3 - y^3 | is minimal and let a(n) := n^3 - x^3 - y^3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A126683 Number of partitions of the n-th triangular number n(n+1)/2 into distinct odd parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A119712 a(n) is the smallest integer k such that the n-th (forward) difference of the partition sequence A000041 is positive from k onwards.