A378760 Smallest sum b_1 + .. + b_k among the sequences of positive integers b_1, b_2, ..., b_k such that 1 + b_1*(1 + b_2*(...(1 + b_k) ... )) = n.

0, 1, 2, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 7, 6, 6, 7, 8, 7, 8, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 8, 9, 8, 8, 9, 9, 9, 10, 9, 9, 9, 10, 9, 10, 9, 9, 9, 10, 9, 10, 10, 10, 10, 11, 10, 10, 10, 10, 10, 11, 10, 11, 10, 10, 10, 11, 10, 11, 10, 10, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 11, 12, 11, 11, 11, 12, 12, 13, 11, 11

Offset: 1

Author

Matthieu Pluntz, Dec 06 2024

Keywords

• easy
• nonn

Comments

Among rooted trees with n vertices in which vertices at depth level i-1 all have b_i children each (generalized Bethe trees), a(n) is the smallest sum of those numbers of children.

There are A003238(n) trees of this type (and sequences of b_i).

Examples

			a(5) = 3 is reached by b_1 = 2, b_2 = 1. 5 = 1 + b_1*(1 + b_2), 3 = b_1 + b_2.
		

Links

• Matthieu Pluntz, Table of n, a(n) for n = 1..20000

Crossrefs

Cf. A003238.

Programs

Maple

a:= proc(n) option remember; `if`(n=1, 0, min(
      seq((n-1)/d+a(d), d=numtheory[divisors](n-1))))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Dec 06 2024

Mathematica

a[n_] := a[n] = If[n == 1, 0, Min[Table[(n-1)/d + a[d], {d, Divisors[n-1]}]]];
Table[a[n], {n, 1, 100}](* Jean-François Alcover, Jan 26 2025, after Alois P. Heinz *)

R

a = rep(0,N)
for(n in 1:(N-1)){
  divs = numbers::divisors(n)
  a[n+1] = min(divs + a[n/divs])
}

Formula

a(1) = 0; a(n+1) = min_{k divides n} (k + a(n/k)).