A376012 a(n) = number of solutions (x_1, x_2, ..., x_n) to Product_{i=1..n} (1 + 1/x_i) = any integer.

1, 1, 3, 12, 83, 1323, 63090, 14736464

Offset

0,3

Comments

Number of ways any integer is a product of n superparticular ratios, without regard to order. A superparticular ratio is a ratio of the form (m+1)/m.

Links

Table of n, a(n) for n=0..7.

Example

For n = 2, a(2) = 3, three solutions, {x_1, x_2} = {2, 3} = 2; {1, 2} = 3; {1, 1} = 4.
In other words, a(2) = 3 since 2 can be written as (3/2)(4/3), 3 can be written as (2/1)(3/2), and 4 can be written as (2/1)^2, but no other integers are the product of two superparticular ratios.
a(3) = 12 since 2 can be written in 5 ways, 3 can be written in 3 ways, and 4, 5, 6, and 8 can be written in 1 way each, as the product of three superparticular ratios.

Prog

(PARI) f(n, m, p, q)={ \\ the number of solutions in which product of the ratios is equal to p/q
    if(p<=q, return(0));
    if(n==1, return(if(q%(p-q)==0, 1, 0)));
    x=floor(1/((p/q)^(1/n)-1)); \\ x is the maximum of the least denominator of the ratios
    my(ans=0);
    for(i=m, x, ans=ans+f(n-1, i, p*i, q*(i+1)));
    \\ m indicates that the solutions require the denominators of all ratios not to be less than m
    \\ discard the ratio (i+1)/i
    return(ans);
};
a(n)={
    my(ans=0);
    for(i=2, 2^n, ans=ans+f(n, 1, i, 1));
    return(ans);
}; \\ Yifan Xie, Nov 21 2024

Crossrefs

Cf. A085098, A118086, A277608.

Sequence in context: A067111 A171186 A229421 * A212718 A357846 A051549

Adjacent sequences: A376009 A376010 A376011 * A376013 A376014 A376015

Keyword

hard,nonn,more

Author

Keith F. Lynch, Sep 05 2024

Status

approved