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

Graeme McRae graememcrae at gmail.com
Mon Aug 22 04:07:31 CEST 2016


I can see that the number of symbols for each place value must equal the
square of the magnitude of the base, if the number system has any chance of
covering all the Gaussian integers. In other words, the number of different
n-digit numbers in this base must be about equal to the area of a circle of
radius |base|^n. So this particular base(2+i) has the interesting property
of allowing all 4 units plus zero (5 symbols in all), being this |base| is
sqrt(5).

A little experimentation using a crude tool (Excel) told me the numbers in
this base have unique values, so they must cover the Gaussian integers
completely. If I knew more math, I'm sure it would be obvious to me why
that's the case. :)

The distance you can get from the origin using a 7-digit base(2+i) number
can't exceed 5^0+5^(1/2)+5^1+5^(3/2)+5^2+5^(5/2)+5^3, or about 225.3, so I
thought it would be fun to see how far the "biggest" of these base(2+i)
numbers can get from the origin.

There are 62500 base(2+i) 7-digit numbers, but of course you only need to
check a quarter of them if you consider there are four rotations, (or an
eighth, if you consider reflections), and even fewer when you realize the
number can't have any zero-digits (else a unit in some direction would
extend it from the origin)...

...so 1 1 i i i i -1 in this base turns out to be -196+85i, the 7-digit
number farthest from the origin, at a distance of sqrt(45641), or about
213.6, about 95% of that upper bound of 225.3.

Thanks, Joerg Arndt, for drawing my attention to this interesting number
base.


--Graeme McRae
Palmdale, CA

On Sun, Aug 21, 2016 at 3:05 PM, Antti Karttunen <antti.karttunen at gmail.com>
wrote:

> Wow, this must be synchronicity:
>
> I was doing various "post-submission checks" for a batch of unrelated new
> sequences (concerning factorial base), and a part of these checks is
> clicking the left and the right hand neighbours on the "Sequence in
> context" links (as to be 100% sure that I didn't submit a duplicate, or
> maybe more for just to look if there is anything interesting "nearby"), and
> what I will find this time:
>
> https://oeis.org/A066321 "Binary representation of base i-1 expansion of
> n:
> replace i-1 by 2 in base i-1 expansion of n."  from Marc LeBrun, Dec 14
> 2001 !
>
>
> Maybe these should have an index entry? "base i-1" is not really a good
> term to search for.
>
>
> Cheers,
>
> Antti
>
>
> On Sun, Aug 21, 2016 at 9:41 AM, Antti Karttunen <
> antti.karttunen at gmail.com>
> wrote:
>
> > 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
> > >
> > >
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list