A321211 Let S be the sequence of integer sets defined by these rules: S(1) = {1}, and for any n > 1, S(n) = {n} U S(pi(n)) U S(n - pi(n)) (where X U Y denotes the union of the sets X and Y and pi is the prime counting function); a(n) = the number of elements of S(n).

1, 2, 3, 3, 4, 4, 5, 4, 6, 6, 6, 7, 7, 7, 8, 7, 8, 9, 9, 9, 9, 8, 10, 9, 10, 11, 11, 11, 11, 12, 12, 12, 11, 12, 11, 12, 13, 13, 13, 14, 14, 14, 13, 14, 14, 14, 15, 14, 14, 12, 14, 15, 14, 15, 16, 17, 17, 16, 16, 16, 16, 17, 16, 16, 17, 17, 16, 16, 15, 17, 19

Offset

1,2

Comments

The prime counting function corresponds to A000720.

This sequence has similarities with A294991; a(n) gives approximately the number of intermediate terms to consider in order to compute A316434(n) using the formula of its definition.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Rémy Sigrist, Illustration of a(42)

Rémy Sigrist, Density plot of the first 100000000 terms

Rémy Sigrist, C++ program for A321211

Example

The first terms, alongside pi(n) and S(n), are:
  n   a(n)  pi(n)  S(n)
  --  ----  -----  ----------------------
   1     1      0  {1}
   2     2      1  {1, 2}
   3     3      2  {1, 2, 3}
   4     3      2  {1, 2, 4}
   5     4      3  {1, 2, 3, 5}
   6     4      3  {1, 2, 3, 6}
   7     5      4  {1, 2, 3, 4, 7}
   8     4      4  {1, 2, 4, 8}
   9     6      4  {1, 2, 3, 4, 5, 9}
  10     6      4  {1, 2, 3, 4, 6, 10}
  11     6      5  {1, 2, 3, 5, 6, 11}
  12     7      5  {1, 2, 3, 4, 5, 7, 12}

Prog

(C++) See Links section.
(PARI) a(n) = my (v=Set([-1, -n]), i=1); while (v[i]!=-1, my (pi=primepi(-v[i])); v=setunion(v, Set([v[i]+pi, -pi])); i++); #v

Crossrefs

Cf. A000720, A294991, A316434.

Sequence in context: A294991 A300118 A256544 * A336515 A130500 A072073

Adjacent sequences: A321208 A321209 A321210 * A321212 A321213 A321214

Keyword

nonn

Author

Altug Alkan and Rémy Sigrist, Oct 31 2018

Status

approved