Better definition for A113166

[Max Alekseyev]

On 6/20/06, Max Alekseyev <maxale at gmail.com> wrote:
> 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)))

And even simpler:

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

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

P.S. Sorry for spamming ;-)

Max