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

Author

Altug Alkan and Rémy Sigrist, Oct 31 2018

Keywords

• nonn

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.

Examples

			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}
		

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

Crossrefs

Cf. A000720, A294991, A316434.

Programs

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