formula for A103314(2pq)

[Max Alekseyev]

SeqFans,

I've got a new somewhat interesting formula for A103314.

Let b(n) be the number of aperiodic subsets S of the n-th roots of 1
with zero sum (i.e., there is no root r such that r*S=S).
Then

A103314(n) = b(n)*n + 2^n - A001037(n)*n

Note that as soon as b(n)=0, we have simply A103314(n) = 2^n -
A001037(n)*n, that makes it especially interesting to study those n
for which b(n)=0.

Using known values/formulas for A103314 and A001037, we can easily
compute first 104 terms of b(n):

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 24, 0, 6, 0, 0, 0,
236, 0, 0, 0, 18, 0, 3768, 0, 0, 0, 0, 0, 20384, 0, 0, 0, 7188, 0,
227784, 0, 186, 480, 0, 0, 1732448, 0, 237600, 0, 630, 0, 16028160, 0,
306684, 0, 0, 0, 341521732, 0, 0, 4896, 0, 0, 1417919208, 0, 7710, 0,
357790944, 0, 12934218752, 0, 0, 608640, 27594, 0, 122160785880, 0,
8578527648, 0, 0, 0, 1571823757356, 0, 0, 0, 782047788, 0,
34798691213160, 0, 364722, 0, 0, 0, 101234590920704, 0, 658522617984,
764832, 9384778461696, 0, 959311205529720, 0, 42304397940]

This sequence is not in OEIS yet.
The indices n below 200 with b(n)>0 so far are:

1, 12, 18, 20, 24, 28, 30, 36, 40, 42, 44, 45, 48, 50, 52, 54, 56, 60,
63, 66, 68, 70, 72, 75, 76, 78, 80, 84, 88, 90, 92, 96, 98, 99, 100,
102, 104, ?, 108, 110, 112, 114, 116, 117, 120, 124, 126, 130, 132,
135, 136, 138, 140, 144, 147, 148, 150, 152, 153, 154, 156, 160, 162,
164, ?, 168, 170, 171, 172, 174, 175, 176, 180, 182, 184, 186, 188,
189, 190, 192, ?, 196, 198, 200

where ? stands for unknown possibly missing term.
To my greatest surprise they all known terms perfectly agree with
A102467 (correspondingly, the indices of zero terms seem to be
A102466). Unfortunately, this observation does not help us to get
A103314(105) (the first term of A103314 with unknown value) since 105
belongs to A102467.

Regards,
Max

On Jan 8, 2008 2:04 AM, Max Alekseyev <maxale at gmail.com> wrote:
> 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
>