half-baked generalized convolution sequence transforms

Tue Jun 12 12:09:02 CEST 2001

Marc LeBrun wrote:

>
> 10. But now here's a completely different generalized convolution transform
> using binary bitwise operations (switching to 1-based instead of 0-based
> indexing).
>
> Let's say that j "masks" i just when
>
>    i AND j  =  i
>
> or, equivalently,
>
>    i IOR j  =  j.
>
> Here the complement of i in j is just the ordinary difference--but only
> when j masks i is it defined!  So instead of summing over divisors we sum
> over "bivisors" (or whatever you want to call the binary "maskees").

Here's the corresponding Maple code, if it helps anyone. Could you Mark also
tell me, whether I got it as you intended?

(Same code can also be found in
http://www.megabaud.fi/~karttu/matikka/findnext.txt
and some procedures like ANDnos by Neil from
http://www.research.att.com/~njas/sequences/transforms.txt
Note how I directly modeled this after MOBIUSi (sum over divisors) transform given

in above collection. There are more efficient methods to do this...)

# Does it Mask (j over i)?

dim := proc(j,i) if(ANDnos(j,i) = i) then 1 else 0; fi; end;

# MASKTRANS(a) is equivalent to MASKCONV(a,A000012), where A000012 is all-1's
sequence.

MASKTRANS :=proc(a) local c,i,j,n;
  if whattype(a) <> list then RETURN([]); fi;
  n := nops(a);
  c := [];
  for j from 0 to n-1
   do
       c := [ op(c), sum( ' dim(j,i)*a[i+1] ', 'i'=0..j)];
   od;
  RETURN(c);
end;

MASKCONV :=proc(a,b) local c,i,j,n;
  if whattype(a) <> list then RETURN([]); fi;
  if whattype(b) <> list then RETURN([]); fi;
  n := min(nops(a),nops(b));
  c := [];
  for j from 0 to n-1
   do
       c := [ op(c), sum( ' dim(j,i)*a[i+1]*b[(j-i)+1] ', 'i'=0..j)];
   od;
  RETURN(c);
end;

>
>
> Using this new template, a direct transform using "all 1s" has an inverse
> transform which is the sequence
>
>        t(n)
>    (-1)
>
> where t(n) is A010060, the Thue-Morse sequence
>
>    0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,...
>
> (I think this signed sequence itself is also in EIS...but just try
> searching for signed forms
> of the all 1s sequence without going blind!)

A010060 := [seq((wt(j) mod 2),j=0..63)]; # (wt given in Neil's transformation
collection, gives the number of 1-bits in n)
 --> [0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,...]

Iseq := [seq((-1)^(wt(j) mod 2),j=0..63)]; -->
[1,-1,-1,1,-1,1,1,-1,-1,1,1,-1,1,-1,-1,1,-1,1,1,-1,1,-1,-1,1,1,-1,-1,1,...]

>
>
> 11. Applying the direct Thue-Morse "mask" transform to the all 1s sequence
> gives A001316
>
>    1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,...
>
> "Gould's sequence: Sum_{k=0..n} (C(n,k) mod 2).". which also could be
> described  as "2 to the number of 1 bits in n".

MASKTRANS(A000012) = MASKCONV(A000012,A000012);
--> [1,2,2,4,2,4,4,8,2,4,4,8,4,8,8,16,2,4,4,8,4,8,8,16,4,8,8,16,...

>
>
> The inverse transform applied to the natural numbers hits on A060146
>
>    0,1,2,0,4,0,0,0,8,0,0,0,0,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,0,...
>
> "Nim-Binomial transform of the natural numbers"...so I guess we have
> another name for this transform!  (This sequence was recently added on
> March 6 by John W. Layman--anyone familiar with this work?)

A001477 := [seq(j,j=0..35)]; --> [0,1,2,3,4,5,6,7,8,9,10,11,12, ...];
MASKCONV(A001477,Iseq);
-> [0,1,2,0,4,0,0,0,8,0,0,0,0,0,0,0,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,32,0,0,0,...]

>
>
> Applying the mask transform to the natural numbers gives the new sequence
>
>    0,1,2,6,4,10,12,28,8,18,20,44,24,52,56,120,16,34,36,76,40,84,88,...

MASKTRANS(A001477); = MASKCONV(A000012,A001477); = MASKCONV(A001477,A000012);
--> [0,1,2,6,4,10,12,28,8,18,20,44,24,52,56,120,16,34,...]

>
> The left-shifting eigensequence of the Thue-Morse transform is kind of
> intriguing
>
>    1,1,2,3,7,8,17,27,66,67,135,204,479,553,1182,1889,4641,4642,9285,...
>
> (for a good time, compare with its first difference!<;-)

> MASKTRANS([1,1,2,3,7,8,17,27,66,67,135,204,479,553,1182,1889,4641,4642,9285]);
[1, 2, 3, 7, 8, 17, 27, 66, 67, 135, 204, 479, 553, 1182, 1889, 4641, 4642, 9285,
13929]

> DIFF([1,1,2,3,7,8,17,27,66,67,135,204,479,553,1182,1889,4641,4642,9285]);
[0, 1, 1, 4, 1, 9, 10, 39, 1, 68, 69, 275, 74, 629, 707, 2752, 1, 4643]

>
>
> This transfrom somewhat counter-intuitively connects three sequences in a
> chain: from A006519 "Highest power of 2 dividing n." to A053644 "Largest
> power of 2 less than or equal to n" to A048678 "Binary expansion of
> nonnegative integers expanded to Zeckendorffian format with rewrite rules
> 0->0, 1->01." (jumping between the rightmost, leftmost and middlemost 1 bits).

Hmm, here I noticed that I need to prepend 0 to some of the sequences
to get it working:

A048678 := [seq(rewrite_0to0_1to01(n),n=0..64)];
-->
[0,1,2,5,4,9,10,21,8,17,18,37,20,41,42,85,16,33,34,69,36,73,74,149,40,81,82,...]
A053644pre0 := MASKCONV(A048678,Iseq);
-->
[0,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,32,...]

A055975pre0 := MASKCONV(A053644pre0,Iseq);
-->
[0,1,2,-1,4,-1,-2,1,8,-1,-2,1,-4,1,2,-1,16,-1,-2,1,-4,1,2,-1,-8,1,2,-1,4,-1,-2,1,32,-1,-2,1,-4,...]

A006519pre0 := map(abs,A055975pre0);
-->
[0,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,16,1,2,1,4,1,2,1,8,1,2,1,4,1,2,1,32,1,2,1,4,1,2,1,8,1,2,1,4,1,...]

Or going the other way:
MASKTRANS(A055975pre0);
--> [0,1,2,2,4,4,4,4,8,8,8,8,8,8,8,8,16,16,16,16,16,16,16,16,16,16,16,...]
MASKTRANS(MASKTRANS(A055975pre0));
-->
[0,1,2,5,4,9,10,21,8,17,18,37,20,41,42,85,16,33,34,69,36,73,74,149,40,81,82,...]

Note, that it is not A006519 from which the chain starts, but its signed variant
A055975
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A055975

prepended with 0 i.e., [0,1,2,-1,4,1,-2,-1,8,1,2,-1,-4,1,-2,-1,16,...].

>
>
> The Gray Code A003188 has an interesting transform whose only non-zero
> members are 1x and 3x the powers of 2... and so on, ad infinitem (including
> other transforms defined on this same template).

Do you mean this:

A003188 := [seq(XORnos(j,floor(j/2)),j=0..65)];
A003188 :=
[0,1,3,2,6,7,5,4,12,13,15,14,10,11,9,8,24,25,27,26,30,31,29,28,20,21,23,22,18,19,17,16,48,49,...]

MASKCONV(A003188,Iseq)
-->
[0,1,3,-2,6,0,-4,0,12,0,0,0,-8,0,0,0,24,0,0,0,0,0,0,0,-16,0,0,0,0,0,0,0,48,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,-32,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,96,0]

> If you're interested, please let me know...

Yes, certainly! BTW, is there any online or other easily
accessible document which would explain all that numbral stuff?

Terveisin,

Antti Karttunen