A335616 a(n) is twice the number of partitions of n into consecutive parts, minus the number of partitions of n into consecutive parts that contain 1 as a part.

1, 2, 3, 2, 4, 3, 4, 2, 6, 3, 4, 4, 4, 4, 7, 2, 4, 6, 4, 4, 7, 4, 4, 4, 6, 4, 8, 3, 4, 8, 4, 2, 8, 4, 8, 5, 4, 4, 8, 4, 4, 8, 4, 4, 11, 4, 4, 4, 6, 6, 8, 4, 4, 8, 7, 4, 8, 4, 4, 8, 4, 4, 12, 2, 8, 7, 4, 4, 8, 8, 4, 6, 4, 4, 12, 4, 8, 7, 4, 4, 10, 4, 4, 8, 8, 4, 8, 4, 4, 12, 7, 4, 8, 4, 8, 4, 4, 6, 12, 6

Offset: 1

Author

Omar E. Pol, Oct 02 2020

Keywords

• nonn
• easy

Comments

a(n) is twice the number of partitions of n into consecutive parts, minus the number of partitions of n into distinct parts such that the greatest part equals the number of all parts.

For a visualization of the sequence, consider a diagram formed for infinitely many double staircases as shown in the Example section.

a(n) is the number of horizontal line segments (or steps) that are only in the n-th level of the structure, starting from the top.

The total length of all vertical line segments that are adjacent and below the steps of the n-th level of the structure equals twice the total number of parts in all partitions of n into consecutive parts.

Note that in the n-th double staircase the top step is located in the level A000217(n), n >= 1, every horizontal line segment has length 1, and every vertical line segment has length n.

a(n) is also the number of horizontal line segments of length 1 or 2 in the n-th level of the similar diagram used to represent the sequence A237593 and other isosceles triangles related to A237593.

a(n) is odd if and only if n is a nonzero triangular number (A000217).

Double-staircases theorem of the sum of divisors: the total number of steps from level n to the top of all the odd-indexed double staircases that have at least one step in the level n, minus the total number of steps from the level n to the top of all the even-indexed double staircases that have at least one step in the level n equals sigma(n) = A000203(n).

The above theorem shows a symmetry of sigma in accordance with the symmetric Dyck Paths described in A237593 and with the pyramid described in A245092.

For the connection with the partitions into consecutive integers see also A196020, since we can see here that A196020(n,k) is also the number of steps in the first n levels of the k-th double staircase that has at least one step in the n-th level of the diagram, otherwise A196020(n,k) = 0. Also, it is the width of the mentioned staircase in n-th level of the diagram.

It appears that odd primes (A065091) are also the levels where there are steps in the staircases 1 and 2, but no step from other staircases.

It appears that powers of 2 (A000079) are also the levels where there are only one or two steps in total.

This sequence could be related to several other sequences (see the Crossrefs section of A262626).

Examples

			Illustration of initial terms:
n   a(n)                               Diagram
                                          _
1     1                                 _|1|_
2     2                               _|1 _ 1|_
3     3                             _|1  |1|  1|_
4     2                           _|1   _| |_   1|_
5     4                         _|1    |1 _ 1|    1|_
6     3                       _|1     _| |1| |_     1|_
7     4                     _|1      |1  | |  1|      1|_
8     2                   _|1       _|  _| |_  |_       1|_
9     6                 _|1        |1  |1 _ 1|  1|        1|_
10    3               _|1         _|   | |1| |   |_         1|_
11    4             _|1          |1   _| | | |_   1|          1|_
12    4           _|1           _|   |1  | |  1|   |_           1|_
13    4         _|1            |1    |  _| |_  |    1|            1|_
14    4       _|1             _|    _| |1 _ 1| |_    |_             1|_
15    7     _|1              |1    |1  | |1| |  1|    1|              1|_
16    2    |1                |     |   | | | |   |     |                1|
...
For n = 6 (above), the total number of steps in all double staircases that have at least one step in the 6th level of the structure is equal to 3, since there are two steps in the first double staircase, there are no steps in the second double staircase, and there is only one step in the third double staircase, so a(3) = 2 + 0 + 1 = 3.
From the theorem (see comments) for n = 6, let s(k) = A196020(6,k) be the total number of steps from level n to the top, in the k-th double staircase that has at least a step in the 6th level of the structure, otherwise s(k) = 0. We have that s(1) = 11, s(2) = 0 and s(3) = 1. So the alternating sum is 11 - 0 + 1 = 12, which equals sigma(6) = 1 + 2 + 3 + 6 = 12.
Note that to evaluate sigma(n), it is sufficient to have only the n-th level of the diagram, since the width of the base level of a double staircase equals the number of its steps. See below:
For n = 6 the 6th level of the above diagram looks like this:
                                _         _         _
                               |1      | |1| |      1|
.
Width of the 1st staircase:    |<-------- 11 ------->|
.
Width of the 3rd staircase:          --->|1|<---
.
The width of the first double staircase is 11, the width of the second double staircase does not count, and the width of the third double staircase is 1, so the alternating sum is 11 - 0 + 1 = 12 = sigma(6).
For n = 15 the alternating sum is 29 - 13 + 7 - 0 + 1 = 24 = sigma(15).
For n = 16 the alternating sum is 31 -  0 + 0 - 0 + 0 = 31 = sigma(16).
For more information about these alternating sums see A196020.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 1..10000

Crossrefs

Row sums of A339275.

Partial sums give A338722.

Cf. A000079, A000203, A000217, A001227, A054843, A054844, A065091, A136107. A196020, A204217, A236104, A235791, A237048, A237593, A237593, A245092, A249351, A262611, A262626, A279693, A279733, A281010, A281011, A286001, A299765, A338721.

Programs

Maple

N:= 100:
S := convert(series( add( x^(n*(n+1)/2)*(1 + x^n)/(1 - x^n), n = 1..floor(sqrt(2*N)) ), x, N+1 ), polynom):
seq(coeff(S, x, n), n = 1..N); # Peter Bala, Jan 20 2021

Mathematica

A335616[n_]:=2DivisorSigma[0,n/2^IntegerExponent[n,2]]-Boole[IntegerQ[(Sqrt[8n+1]-1)/2]];Array[A335616,100] (* Paolo Xausa, Sep 03 2023 *)

Formula

a(n) = 2*A001227(n) - A010054(n).

a(n) = A054844(n) - A010054(n).

a(n) = 2*A136107(n) + A010054(n). - Omar E. Pol, Nov 27 2020

G.f.: Sum_{n >= 1} x^(n*(n+1)/2)*(1 + x^n)/(1 - x^n). Cf. A000005 with g.f. Sum_{n >= 1} x^(n^2)*(1 + x^n)/(1 - x^n). - Peter Bala, Jan 20 2021

Extensions

Simpler definition from Omar E. Pol, Nov 27 2020