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

%I #7 Nov 20 2017 22:08:30

%S 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,

%T 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,

%U 11,12,11,16,7,20,10,15,8,21,8,22,12,13,11,18

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

%C This sequence combines features from A096216 and from A295277.

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

%e The first terms, alongside the earlier terms coprime to n, are:

%e n a(n) Earlier terms coprime to n

%e -- ---- --------------------------

%e 1 1 {}

%e 2 2 {1}

%e 3 3 {1, 2}

%e 4 3 {1, 3}

%e 5 4 {1, 2, 3}

%e 6 2 {1}

%e 7 5 {1, 2, 3, 4}

%e 8 4 {1, 3, 5}

%e 9 5 {1, 2, 4, 5}

%e 10 3 {1, 3}

%e 11 6 {1, 2, 3, 4, 5}

%e 12 3 {1, 5}

%e 13 7 {1, 2, 3, 4, 5, 6}

%e 14 4 {1, 3, 5}

%e 15 5 {1, 2, 4, 7}

%e 16 5 {1, 3, 5, 7}

%e 17 8 {1, 2, 3, 4, 5, 6, 7}

%e 18 4 {1, 5, 7}

%e 19 9 {1, 2, 3, 4, 5, 6, 7, 8}

%e 20 5 {1, 3, 7, 9}

%o (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)))

%Y Cf. A000720, A096216, A295277.

%K nonn

%O 1,2

%A _Rémy Sigrist_, Nov 19 2017