formula for A103314(2pq)

[Max Alekseyev]

SeqFans,

a(n)=A103314(n) counts the total number of subsets of the n-th roots
of 1 with the sum of elements equal zero.
Due to a nice formula a(n)=a(s(n))^(n/s(n)), where s(n) is the
square-free kernel of n, a(n) is easy to compute as soon as the value
of a(s(n)) is known.

Therefore, the only challenge is to compute a(n) for square-free
numbers n, i.e., n=p1*p2*...*pk where pi are distinct primes.
For k = 1 and 2, there are relatively simple formulas:
a(p) = 2
a(pq) = 2^p + 2^q - 2.
Until recently no formula was known for k>=3.

I want to announce a new formula for a particular case of k=3 with
p1=2, proved by Sasha Rybak:

a(2pq) = (2^p+2)^q + (2^q+2)^p - 2(2^p+1)^q - 2(2^q+1)^p + 2^(pq) +
SUM[j=0..p] binomial(p,j)*(2^j+2^(p-j))^q.

It shows that the general formula for k=3 (let alone k>3) may be way
more complicated than previously known formulas.

The original Sasha's proof in Russian is given at
http://lib.mexmat.ru/forum/viewtopic.php?p=78783#78783

Using this new formula, I've extended A103314 and its derivative
A107847 up to the 104-th term (updates have been sent to Neil).
And here is a PARI/GP implementation of A103314 that tries to employ
all known formulas to come up with an answer:

{ a(n) = local(f=factorint(n),k=matsize(f)[1]);
if(n<=1,return(1));
if(vecmax(f[,2])>1,return(a(prod(i=1,k,f[i,1]))^prod(i=1,k,f[i,1]^(f[i,2]-1))));
if(k==1,return(2)); f=f[,1];
if(k==2,return(2^f[1]+2^f[2]-2));
if(k==3 && f[1]==2,
sum(j=0,f[2],binomial(f[2],j)*(2^j+2^(f[2]-j))^f[3]) + (2^f[2]+2)^f[3]
+ (2^f[3]+2)^f[2] - 2*((2^f[2]+1)^f[3]+(2^f[3]+1)^f[2]) +
2^(f[2]*f[3]), error("unsupported") )
}

Regards,
Max



Neil's award winning paper is at
http://www.ams.org/notices/200308/comm-sloane.pdf

Tony