formula for A103314(2pq)

[Max Alekseyev]

I've computed A103314 for n=3*5*7=105:

A103314(105) = 166093023482

It fills some gaps in other sequences:

A107847(105) = 386331611498127055692651519510
and
b(105) = 1254582432  (non-zero, as it was expected from A102467).

Time to attack n=165=3*5*11 ...

Regards,
Max

On Jan 14, 2008 2:30 AM, Max Alekseyev <maxale at gmail.com> wrote:
> Forgot to specify that aperiodic zero-sum subsets are counted up to
> rotations, so that the total number of aperiodic zero-sum subsets is
> b(n)*n.
>
> Also, the new formula implies:
>
> A107847(n) = A001037(n) - b(n)
>
> Regards,
> Max
>
>
> On Jan 14, 2008 2:02 AM, Max Alekseyev <maxale at gmail.com> wrote:
> > 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
> > >
> >
>