Better definition for A113166

[Max Alekseyev]

On 6/20/06, Max <maxale at gmail.com> wrote:
> Creighton,
>
> From your new definition of A113166 it follows an explicit formula:
>
> A113166(n) = \sum_{k=1}^{[n/2]} k/(n-k) \sum_{j=1}^{gcd(n,k)} {
> (n-k)*gcd(n,k,j)/gcd(n,k) \choose k*gcd(n,k,j)/gcd(n,k) }

Oh, the formula can be simplified to

A113166(n) = \sum_{k=1}^{[n/2]} k/(n-k) \sum_{d|(n,k)} \phi(d) {
(n-k)/d \choose k/d }

where \phi() is Euler totient function.
Equivalent PARI/GP program:

A113166(n) = sum(k=1,n\2,k/(n-k)*sumdiv(gcd(n,k),d,eulerphi(d)*binomial((n-k)/d,k/d)))

Max