How do we implement this two-valued recursive function using FunctionCompile?

Question

I have the following recursive function that involves DivisorSigma:

r1[n_] := DivisorSigma[1, n];
r2[n_] := Sum[r1[d], {d, Divisors[n]}];
r3[n_] := Sum[r2[d], {d, Divisors[n]}];
...

I would like to implement the generic recursive function r[n_,k_] where k is the value of recursion dept parameter, i.e. for k=1 we obtain r1, for k=2 we obtain r2 and so forth. I came across a relatively new feature called FunctionCompile. I would be very grateful if anyone may help me in implementing this recursive function.

My Background: I am investigating the following identity:

$$r_3(n)=\prod_{p\mid n}(3+p)\quad\text{or generally}\quad r_k(n)=\prod_{p\mid n}(k+p)$$

which is seems to be true at least for $k=2,3$:

p[n_, k_] := Product[p + k, {p, Complement[Divisors[n], {1, n}]}];
Print[r2[10]];
Print[p[10, 2]];
Print[r3[10]];
Print[p[10, 3]];

Answer 1

Not an answer but an extended comment

One solution to the generalized approach is using Divisors's Listable feature:

ClearAll[fn];

fn[n_, k_] := Total[Nest[Catenate@*Divisors, {n}, k]]

But you could not use FunctionCompile. The Divisors is not compilable (in FunctionCompile not Compile) as of now (version 13.0.1) unless somebody came up with an undocumented or manual version.

Another example:

r3[10000] // AbsoluteTiming
(* Out: {0.0007438, 120285} *)

fn[10000, 3] // AbsoluteTiming
(* Out: {0.0007075, 120285} *)

We could use Compile:

fnCompiled = 
 Compile[{{n, _Integer}, {k, _Integer}}, 
  Total[Nest[Catenate@*Divisors, {n}, k]], RuntimeOptions -> "Speed"]

Compare:

r3[10000] // MaxMemoryUsed // AbsoluteTiming
(* Out: {0.000844, 2584} *)

fn[10000, 3] // MaxMemoryUsed // AbsoluteTiming
(* Out: {0.0006784, 51208} *)

fnCompiled[10000, 3] // MaxMemoryUsed // AbsoluteTiming
(* Out: {0.0005641, 48256} *)

Note that this approach will expand k level then sum all those numbers up, so if you choose large numbers, you'll see the effect:

fn[500, 10]
(* Out: 68730 *)

(* AbsoluteTiming: 0.0295315 *)
(* MaxMemoryUsed:  1508424   *)