Coprime Convolution Sum

[f.firoozbakht at sci.ui.ac.ir]

Quoting Leroy Quet <qq-quet at mindspring.com>:

> I just submitted the following to the EIS:
>
>
> %S A000001 1,1,2,4,12,24,88
> %N A000001 a(1)=1; for n>1, a(n) = sum{1<=j<n,GCD(j,n)=1} a(j)
> a(n-j)
> %e A000001 Since 1 and 5 are the positive integers < 6 and coprime to
> 6,
> a(6) = a(1)a(5) + a(5)a(1) = 1*12 +12*1 = 24.
> %O A000001 1
> %K A000001 ,more,nonn,
> %A A000001 Leroy Quet (qq-quet at mindspring.com), Aug 08 2004
>
> Maybe someone can extend this sequence.
>
> Also a possibly interesting question, is there a non-recursive way to
> generate this sequence?
>
> We also have the generating function identity:
>
> sum{n=1 to oo} a(n) x^n =
>
> x + sum{n=1 to oo; m=1 to oo; GCD(m,n)=1} a(m) a(n) x^(m+n)
>
> thanks,
> Leroy Quet


In fact a(1) = 1 & a(n)=sum([1/GCD(n, j)]a(j)a(n-j),{j,1,n-1}).

So a(n) for n=1,2,...,50 are :


1, 1, 2, 4, 12, 24, 88, 224, 720, 1792, 7200, 16512, 69952,
185984, 608896, 1797120, 7495424, 17936896, 79457792, 211576832,
742306816, 2190231552, 9482688512, 23198867456, 97967427584,
285227057152, 1046412681216, 3019819909120, 13360270557184,
30582326296576, 147186007113728, 434757887983616, 1557417511550976,
4686632743337984, 18433554756534272, 46679517994942464,
223870769307058176, 655447433226485760, 2389389455359737856,
6759218199287300096, 31134126804938260480, 74605347666353192960,
359460976098271035392, 1048944615383789207552, 3644752685665552957440,
11392065686978594603008, 51163723217754008846336, 128424370760779158257664,
580093126278828127158272, 1625084654371058908921856.

Regards, Farideh.




--------------------------------
This message is sent through UI.
http://www.ui.ac.ir