[seqfan] Re: Project: sequences obtained from Gaussian Integers via Penney's binary method of encoding?

[Antti Karttunen]

On Sat Aug 20 23:14:57 CEST 2016 Don Reble wrote in
http://list.seqfan.eu/pipermail/seqfan/2016-August/016647.html

>> Consider the method of expressing Gaussian Integers as sums of powers of
>> (-1 + i) (with coefficients just either 0 or 1).

>    See also Knuth, The Art of Computer Programming,
>    vol. 2, 2nd ed., pp 189-190.

Thanks, I looked at that page (thanks to some pirates on the net).
Knuth writes: "Another 'binary' complex number system maybe be obtained by
using the base i-1, as suggested by W. Penney [JACM 12 (1965), 247 - 248]."
(So maybe we should call it Penney's binary encoding, or just base (i-1)
encoding?)

The "quater-imaginary system" of Knuth (presented just before, on the same
page 189, using base 2i) might have more regular encodings, as "... so
conversion to and from quater-imaginary notation reduces to conversion to
and from negative quaternary representation of the real and imaginary
parts. The interesting property of this system is that it allows
multiplication and division of complex number to be done in a fairly
uniform manner without treating real and imaginary parts separately".
(I guess Marc LeBrun's binary interleaving sequences come also handy here?)


Best,

Antti


>--
> Don Reble  djr at nk.ca



On Sat, Aug 20, 2016 at 10:31 PM, Antti Karttunen <antti.karttunen at gmail.com>
wrote:
>
>
>
> Here's an old idea from my attic:
>
> Consider the method of expressing Gaussian Integers as sums of powers of
(-1 + i) (with coefficients just either 0 or 1).
> I call this "Hungarian binary method", as I first saw it at this web
page: http://szdg.lpds.sztaki.hu/szdg/desc_numsys_es.php
> (but please tell if it is much older and discovered in some other
country!)
>
> By hand calculation, I get the following values for some small binary
vectors:
>
> 0000 = 0
> 0001 = 1
> 0010 = -1 + i
> 0011 = i
> 0100 = -2i
> 0101 = 1 - 2i
> 0110 = -1 - i
> 0111 = -i
> 1000 = 2 + 2i = (-1+i)^3
> 1001 = 3 + 2i
> 1010 = 1 + 3i
> 1011 = 2 + 3i
> 1100 = 2
> 1101 = 3
> 1110 = 1 + i
> 1111 = 2 + i
> 10000 = (-1+i)^4 = 1 + -4i + -6 + 4i + 1 = 2 -6 = -4
>
> so with these we finally get:
> 11101 = -1 (for a moment I was afraid that it would not appear at all!)
>
> Would it make sense to express with this system all kind of functions
whose domains and/or ranges are Gaussian Integers?
> (As OEIS sequences, I mean).
>
> That is, in a slightly similar way as functions whose domain and/or range
are polynomials over GF(2) have been submitted via their encoded binary
representation, found under index entry
http://oeis.org/wiki/Index_to_OEIS:_Section_Ge#GF2X
>
> Or are there better ones for Gaussian Integers? I'm not thinking here
about how easy it is for human beings to search the terms, but in terms of
some vaguely felt elegance/inelegance of the sequences encoded with it.
That -1 appears so "late" (encoded by binary representation of 29) in this
system feels a bit worrisome.
>
> In any case, as long as bitwise-AND(x,y) = 0 (x and y have no 1-bits in
common positions when encoded), then Gaussian_Integer_interpretation(x+y) =
Gaussian_Integer_interpretation(x) + Gaussian_Integer_interpretation(y).
>
>
> For the starters, could somebody generate a list of numbers whose binary
representations map via this particular encoding to Gaussian primes? (I
don't have appropriate mathematical software at my reach, or cannot use it
properly).
>
>
>
> Best regards,
>
> Antti
>
>