A389737 Number of subsets of {1..n} forming a finite arithmetic progression.

1, 2, 4, 8, 14, 23, 34, 49, 66, 87, 111, 139, 169, 205, 243, 285, 331, 382, 435, 494, 555, 622, 693, 768, 845, 930, 1018, 1110, 1206, 1308, 1412, 1524, 1638, 1758, 1882, 2010, 2142, 2283, 2426, 2573, 2724, 2883, 3044, 3213, 3384, 3561, 3744, 3931, 4120, 4319

Offset

0,2

Comments

An arithmetic progression is a sequence with all equal first differences.

Links

Table of n, a(n) for n=0..49.

Formula

a(n) = A051336(n) + 1.

Example

The a(0) = 1 through a(5) = 23 subsets:
  {}  {}   {}     {}       {}         {}
      {1}  {1}    {1}      {1}        {1}
           {2}    {2}      {2}        {2}
           {1,2}  {3}      {3}        {3}
                  {1,2}    {4}        {4}
                  {1,3}    {1,2}      {5}
                  {2,3}    {1,3}      {1,2}
                  {1,2,3}  {1,4}      {1,3}
                           {2,3}      {1,4}
                           {2,4}      {1,5}
                           {3,4}      {2,3}
                           {1,2,3}    {2,4}
                           {2,3,4}    {2,5}
                           {1,2,3,4}  {3,4}
                                      {3,5}
                                      {4,5}
                                      {1,2,3}
                                      {1,3,5}
                                      {2,3,4}
                                      {3,4,5}
                                      {1,2,3,4}
                                      {2,3,4,5}
                                      {1,2,3,4,5}

Maple

b:= proc(n) option remember; `if`(n<1, [0$2],
      (p-> p+[numtheory[tau](n), p[1]])(b(n-1)))
    end:
a:= n-> 1+n+b(n)[2]:
seq(a(n), n=0..49);  # Alois P. Heinz, Oct 22 2025

Mathematica

Table[Length[Select[Subsets[Range[n]], SameQ@@Differences[#]&]], {n, 0, 15}]

Prog

(Python)
from math import isqrt
def A389737(n): return (((s:=isqrt(n-1))*(s+1))**2>>2)+(n-s**2)*n+1+sum((q:=(n-1)//k)*(2*n-k*(1+q)) for k in range(2, s+1)) if n else 1 # Chai Wah Wu, Oct 20 2025

Crossrefs

For partitions instead of subsets we have A049988 (ranks A325328), strict A049980.

The nonempty case is A051336.

The 0-prepended case (also the version containing maximum) is A054519, ranks A389732.

For compositions instead of subsets we have A175342, ranks A389731.

For distinct instead of equal differences we have A364465.

The complement for compositions is A389741, ranks A389735.

The complement for partitions is A389811, ranks A389812.

The complement is counted by A389813.

Cf. A000740, A007862, A008965, A011782, A325557.

Sequence in context: A259392 A261968 A138526 * A286522 A201347 A089054

Adjacent sequences: A389734 A389735 A389736 * A389738 A389739 A389740

Keyword

nonn

Author

Gus Wiseman, Oct 19 2025

Extensions

More terms from Chai Wah Wu, Oct 20 2025

Status

approved