Sum Over Coprime Elements: Inversion Formula

[franktaw at netscape.net]

Interesting.
 
It appears that the diagonals are all periodic.  (Just observation, looking at 40 rows; I haven't tried to prove any of this.)
Period 1: [1]
Period 2: [-1,0]
Period 3: [-1,-1,0]
Period 6: [1,0,0,0,0,0]
Period 15: [-1,0,-1,-1,1,-1,-1,0,-1,0,0,-1,-1,0,0]
Period 30: [1,0,2,0,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,0,2,0,1,0,0,0,2,0,0,0]
Period ???: [1,0,0,1,0,0,2,-1,0,0,0,0,0,1,-1,1,0,0,1,0,1,1,-1,0,0,0,0,1,0,-1,1,0,0,1,...]
 
The sequence 1,2,3,6,15,30 is not in the OEIS.  To this point, each term a(n)=n*a(n-1)/b(n-1), where b(n) is 1,2,2,2,3.
 
Franklin T. Adams-Watters
 
-----Original Message-----
From: Paul D. Hanna <pauldhanna at juno.com>
To: seqfan at ext.jussieu.fr
Cc: qq-quet at mindspring.com
Sent: Wed, 1 Mar 2006 21:35:15 -0500
Subject: Re: Sum Over Coprime Elements: Inversion Formula


Hello Leroy,
      Nice triangle!  It continues:
 1;
-1, 1;
-1, 0, 1;
 1,-1,-1, 1;
-1, 0, 0, 0, 1;
 1, 0, 0,-1,-1, 1;
 1, 0,-1, 0,-1, 0, 1;
-1, 0, 2,-1, 0, 0,-1, 1;
-1, 0, 0, 0, 1, 0,-1, 0, 1;
 1, 0,-1, 1, 0,-1, 1,-1,-1, 1;
-1, 0, 1, 0, 0, 0,-1, 0, 0, 0, 1;
 1, 0,-1, 0, 0, 0, 1, 0, 0,-1,-1, 1;
 3, 0,-2, 0,-2, 0, 2, 0,-1, 0,-1, 0, 1;
-3, 0, 1, 0, 3, 0,-1,-1, 1, 0, 0, 0,-1, 1;
-1, 0, 1, 0, 1, 0,-1, 0, 0, 0, 0, 0,-1, 0, 1;
 1, 0, 0, 0,-2, 0, 0, 1, 0, 0, 1,-1, 1,-1,-1, 1; ...
 
I confirm that column 1 agrees with A096433,
and do not find this triangle in the OEIS. 
  
If we take the matrix inverse, it begins: 
1;
1,1;
1,0,1;
1,1,1,1;
1,0,0,0,1;
1,1,1,1,1,1;
1,0,1,0,1,0,1;
1,1,0,1,1,0,1,1;
1,0,1,0,0,0,1,0,1;
1,1,1,1,1,1,1,1,1,1;
1,0,0,0,1,0,1,0,0,0,1;
1,1,1,1,1,1,1,1,1,1,1,1; ...
 
which is found in the OEIS (author: Antti Karttunen) 
as a  square array:
http://www.research.att.com/~njas/sequences/A054431
A054431  -- Array read by antidiagonals: 
T(x, y) tells whether (x, y) are coprime (1) or not (0), 
where (x, y) = (1, 1), (1, 2), (2, 1), (1, 3), (2, 2), (3, 1), ...  
 
When we form a triangle out of A054431:
     T(n,k)=if(gcd(n-k+1,k)==1,1,0)
then the coefficients of your transform repeated 2 times
is the matrix inverse square and begins:
 1; 
-2, 1; 
-2, 0, 1; 
 4,-2,-2, 1; 
-2, 0, 0, 0, 1; 
 2, 1, 1,-2,-2, 1; 
 4, 0,-2, 0,-2, 0, 1; 
-6, 1, 6,-2, 1, 0,-2, 1; 
-4, 0, 1, 0, 3, 0,-2, 0, 1; 
 6,-1,-6, 4,-1,-2, 4,-2,-2, 1; 
-4, 0, 3, 0, 1, 0,-2, 0, 0, 0, 1; 
 4, 0,-3,-1,-1, 1, 2, 1, 1,-2,-2, 1; 
14, 0,-7, 0,-7, 0, 6, 0,-2, 0,-2, 0, 1; 
-14, 0, 3, 1, 10, 0,-4,-2, 3, 0, 1, 0,-2, 1; 
-8, 0, 5, 0, 5, 0,-4, 0, 1, 0, 1, 0,-2, 0, 1; 
 8, 0, 0,-1,-10, 0, 1, 3,-2, 1, 2,-2, 4,-2,-2, 1; ...
 
Column 1 is not found in the OEIS: 
1,-2,-2,4,-2,2,4,-6,-4,6,-4,4,14,-14,-8,8,-16,18,8,-12,
6,-6,-6,-10,28,-6,-10,4,-2,4,-8,-2,-18,48,-20,0,54,-70,
-18,32,-76,86,62,14,14,-110,-40,124,62,94,-24,-224,
-66,224,134,62,-72,-286,14,8,-14,474,10,-458,
 
  
The matrix square would give the 
second iteration of the inverse of your transfrom:
1; 
2, 1; 
2, 0, 1; 
4, 2, 2, 1; 
2, 0, 0, 0, 1; 
6, 3, 3, 2, 2, 1; 
4, 0, 2, 0, 2, 0, 1; 
6, 3, 2, 2, 3, 0, 2, 1; 
4, 0, 3, 0, 1, 0, 2, 0, 1; 
10, 5, 6, 4, 5, 2, 4, 2, 2, 1; 
4, 0, 1, 0, 3, 0, 2, 0, 0, 0, 1; 
12, 6, 7, 5, 7, 3, 6, 3, 3, 2, 2, 1; 
6, 0, 3, 0, 3, 0, 2, 0, 2, 0, 2, 0, 1; 
8, 4, 3, 3, 4, 0, 4, 2, 1, 0, 3, 0, 2, 1; 
8, 0, 5, 0, 5, 0, 4, 0, 3, 0, 3, 0, 2, 0, 1; 
16, 8, 10, 7, 10, 4, 9, 5, 6, 3, 6, 2, 4, 2, 2, 1;  ...
 
where column 1 forms Euler totient function phi(n). 
 
I have not checked the other columns or row sums. 
 
There is more to be developed here ...
 
Great idea,
    Paul
 
On Wed, 1 Mar 06 18:40:15 -0700 Leroy Quet <qq-quet at mindspring.com> writes:
> Let us say we have the arbitrary sequence {a(k)}.
> 
> We define {b(k)}, based on {a(k)}, by:
> 
> b(n) = sum{1<=k<=n, GCD(k,n)=1} a(k).
> 
> (So, for example, b(12) = a(1) + a(5) + a(7) + a(11). And b(1) = 
> b(2) = 
> a(1), obviously.)
> 
> 
> So, given {b(k)} (which must have b(1) = b(2)), how do we get the 
> sequence {a(k)}?
> 
> If a(n) =
> 
> sum{k>=2} b(k) * c(n,k),
> 
> then there is a triangular array {c(n,k)} which begins as follows
> (unless I made an error):
> 
>  1
> -1, 1
> -1, 0, 1
>  1,-1,-1, 1
> -1, 0, 0, 0, 1
>  1, 0, 0,-1,-1, 1
>  1, 0,-1, 0,-1, 0, 1
> -1, 0, 2,-1, 0, 0,-1, 1
> 
> (n is from the top then down, and starts with n=1; and k is from 
> left to 
> right, and starts with k=2.)
> 
> 
> Now the terms of {c(n,k)} are easily found by recursion, but I 
> wonder 
> what the closed form formula is that gets this triangle. (Something 
> to do 
> with the Moebius function, perhaps?)
> 
> I don't believe this triangle is in the EIS either.
> 
> But I believe the left-most column is sequence A096433.
> 
> Anything more that can be said about this triangular array?
> I bet there is something somewhere in the literature about it.
>  
> thanks,
> Leroy Quet
___________________________________________________
Try the New Netscape Mail Today!
Virtually Spam-Free | More Storage | Import Your Contact List
http://mail.netscape.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://list.seqfan.eu/pipermail/seqfan/attachments/20060302/5295240f/attachment-0001.htm>