A295280 a(n) = 1 + the number of distinct earlier terms that are coprime to n.

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

Offset

1,2

Comments

This sequence combines features from A096216 and from A295277.

For any n > 0, a(n) <= 1 + pi(n), with equality iff n is not composite (pi(n) = A000720(n)).

Links

Table of n, a(n) for n=1..77.

Example

The first terms, alongside the earlier terms coprime to n, are:
  n   a(n)    Earlier terms coprime to n
  --  ----    --------------------------
   1     1    {}
   2     2    {1}
   3     3    {1, 2}
   4     3    {1, 3}
   5     4    {1, 2, 3}
   6     2    {1}
   7     5    {1, 2, 3, 4}
   8     4    {1, 3, 5}
   9     5    {1, 2, 4, 5}
  10     3    {1, 3}
  11     6    {1, 2, 3, 4, 5}
  12     3    {1, 5}
  13     7    {1, 2, 3, 4, 5, 6}
  14     4    {1, 3, 5}
  15     5    {1, 2, 4, 7}
  16     5    {1, 3, 5, 7}
  17     8    {1, 2, 3, 4, 5, 6, 7}
  18     4    {1, 5, 7}
  19     9    {1, 2, 3, 4, 5, 6, 7, 8}
  20     5    {1, 3, 7, 9}

Prog

(PARI) pv = Set(); for (n=1, 77, v = 1 + sum(i=1, #pv, gcd(pv[i], n)==1); print1 (v ", "); pv = setunion(pv, Set(v)))

Crossrefs

Cf. A000720, A096216, A295277.

Sequence in context: A288159 A269526 A106448 * A307838 A159909 A176004

Adjacent sequences: A295277 A295278 A295279 * A295281 A295282 A295283

Keyword

nonn

Author

Rémy Sigrist, Nov 19 2017

Status

approved