A342616 a(1) = 1, a(n+1) = Sum_{d | a(n)} c_d, where c_d = number of instances of d | a(k) for 1 <= k < n.

1, 1, 2, 4, 7, 6, 11, 8, 15, 13, 11, 13, 14, 21, 21, 25, 19, 18, 33, 29, 21, 36, 49, 30, 52, 43, 27, 41, 29, 31, 31, 33, 49, 42, 76, 55, 46, 51, 53, 40, 70, 78, 85, 53, 46, 65, 60, 116, 79, 50, 87, 72, 123, 74, 77, 72, 140, 132, 143, 74, 89, 62, 92, 110, 125, 82

Offset: 1

Author

Michael De Vlieger, Mar 17 2021

Keywords

• nonn
• easy

Comments

For all n, we have c_1 = (n-1) since 1 | n for all nonzero n.

There are 2 means by which we set c_p = 1 for p prime. Let m = a(n), the progenitor of a(n+1). The first is directly via Sum_{d | a(n)} c_d = p. The second is indirectly, through Sum_{d | a(n)} c_d = m, and novel p | m. An example of the first is the appearance of a(3) = 2, and the second, a(6) = 6 is divisible by 3, a prime not yet appearing in the sequence.

For a(n) = p novel, a(n+1) = n, since we have (n-1) instances of d = 1 and 1 instance of p. Subsequent appearances of p have a(n+1) exceed n. Primes may appear more than once.

The two instances of 1 that begin the sequence yield a(3) = 2. The terms a(2) and a(3) are the only instances of a(n) < n. This is because only register c_1 > 0 for those terms, and in all other terms, we have the progenitor term a(n) > 1. Indeed, 1 can never again arise, because the only way we have Sum_{d | a(n)} c_d = 1 is when novel a(n) = 1 where d = 1 has only appeared once before. Clearly 1 has already appeared twice for n >= 2. No other number has 1 divisor, therefore there are only 2 occasions of 1 in the sequence, i.e., a(1) = a(2) = 1.

Generally for n > 3, m < n does not appear as a term. This implies the lower bound a(n) = n for n > 3. We have shown that a(n) = n results from certain prime progenitors m.

The striations seen in the scatterplot relate to the lesser prime divisors of progenitors a(n) = m -> a(n+1).

Examples

			a(2) = 1 since we have 1 instance of 1 | a(k) for 1 <= k < n (which we shall abbreviate hereinafter as a count 1(1)).
a(3) = 2 since we have 2(1).
a(4) = 4 since we have 3(1) and 1(2).
a(5) = 7 since we have 4(1), 2(2), and 1(4).
a(6) = 6 since we have 5(1) and 1(7).
a(7) = 11 since we have 6(1), 3(2), 1(3), and 1(6); 6+3+1+1 = 11.
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..10000
• Michael De Vlieger, Plot of a(n) for 1 <= n <= 2^20, showing "paint sprayer" striation features akin to A279818.
• Michael De Vlieger, Plot of a(n) for 1 <= n <= 2^14. The color code applies to the progenitor m -> a(n). If m is prime, we plot (n,a(n)) in red. If m is odd and composite, we plot (n,a(n)) in yellow. If m is even and composite we plot (n,a(n)) in blue.
• Michael De Vlieger, Plot of a(n) for 1 <= n <= 2^14. The color code applies to the divisor counting function tau(m) for m -> a(n), with red signifying a low number of divisors and blue and violet signifying the highest number of divisors.
• Michael De Vlieger, Plot of a(n) for 1 <= n <= 4096 highlighting squarefree semiprime m -> a(n), color coding a(n) according to least prime factor of m. Red indicates lpf(m) = 2, orange lpf(m) = 3, etc.

Crossrefs

Cf. A027750, A279818.

Programs

Mathematica

Block[{a = {1}, c}, Do[(Map[If[! IntegerQ[c[#] ], Set[c[#], 1], c[#]++] &, #]; AppendTo[a, Total[Map[c[#] &, #]] ]) &@ Divisors[a[[-1]] ], 65]; a] (* Michael De Vlieger, Mar 17 2021 *)