A378760 - OEIS

%I #27 Jan 26 2025 09:06:10

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

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

%U 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

%N 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.

%C 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.

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

%H Matthieu Pluntz, <a href="/A378760/b378760.txt">Table of n, a(n) for n = 1..20000</a>

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

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

%p a:= proc(n) option remember; `if`(n=1, 0, min(

%p       seq((n-1)/d+a(d), d=numtheory[divisors](n-1))))

%p     end:

%p seq(a(n), n=1..100);  # _Alois P. Heinz_, Dec 06 2024

%t a[n_] := a[n] = If[n == 1, 0, Min[Table[(n-1)/d + a[d], {d, Divisors[n-1]}]]];

%t Table[a[n], {n, 1, 100}](* _Jean-François Alcover_, Jan 26 2025, after _Alois P. Heinz_ *)

%o (R)

%o a = rep(0,N)

%o for(n in 1:(N-1)){

%o   divs = numbers::divisors(n)

%o   a[n+1] = min(divs + a[n/divs])

%o }

%Y Cf. A003238.

%K easy,nonn,changed

%O 1,3

%A _Matthieu Pluntz_, Dec 06 2024