cp's OEIS Frontend

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.

%I A378760 #27 Jan 26 2025 09:06:10
%S A378760 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 A378760 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 A378760 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 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.
%C A378760 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 A378760 There are A003238(n) trees of this type (and sequences of b_i).
%H A378760 Matthieu Pluntz, <a href="/A378760/b378760.txt">Table of n, a(n) for n = 1..20000</a>
%F A378760 a(1) = 0; a(n+1) = min_{k divides n} (k + a(n/k)).
%e A378760 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 A378760 a:= proc(n) option remember; `if`(n=1, 0, min(
%p A378760       seq((n-1)/d+a(d), d=numtheory[divisors](n-1))))
%p A378760     end:
%p A378760 seq(a(n), n=1..100);  # _Alois P. Heinz_, Dec 06 2024
%t A378760 a[n_] := a[n] = If[n == 1, 0, Min[Table[(n-1)/d + a[d], {d, Divisors[n-1]}]]];
%t A378760 Table[a[n], {n, 1, 100}](* _Jean-François Alcover_, Jan 26 2025, after _Alois P. Heinz_ *)
%o A378760 (R)
%o A378760 a = rep(0,N)
%o A378760 for(n in 1:(N-1)){
%o A378760   divs = numbers::divisors(n)
%o A378760   a[n+1] = min(divs + a[n/divs])
%o A378760 }
%Y A378760 Cf. A003238.
%K A378760 easy,nonn
%O A378760 1,3
%A A378760 _Matthieu Pluntz_, Dec 06 2024