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,3

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).

Links

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

Formula

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

Example

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

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 *)

Prog

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

Crossrefs

Cf. A003238.

Sequence in context: A126236 A198194 A375815 * A073047 A038567 A185195

Adjacent sequences: A378757 A378758 A378759 * A378761 A378762 A378763

Keyword

easy,nonn,changed

Author

Matthieu Pluntz, Dec 06 2024

Status

approved