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

[Joerg Arndt]

To partly answer both emails:

An index for "Nonstandard numeration systems" would be
welcome.  It should not contain any of the standard bases.
Base -2, bases -x, , base -1+i, and bases x+y*i would be a good start.


Symmetry of the numeration systems I mentioned:
each of my curve corresponds to a tile which
really is the fundamental tile if a complex numeration
system and ALL of these have maximal symmetry
(e.g., all tiles-plus (see paper) for the (3.6.3.6)-grid
have sixfold symmetry).


For the "integral" complex numeration systems (systems, where every
complex integer has a unique representation in them) for base B = x+y*i
a necessary condition is that the "digits" are a complete residue systems
modulo B.

This condition is NOT sufficient however: if all (small) neighborhoods
of zero of the fundamental tile do contain elements NOT in the tile
then the numeration system is not integral.  See figure 3.3-H on page
25 of my paper for what I think is the easiest example.

This is against my intuition (that tells me "complete residue system"
should be good enough).  If anyone can enlighten me, I'd be glad.
I'd be very glad for an algorithm that uses (just) the base B
and the digits to determine whether a given numeration system
is integral.  This might be of the form "try to expand a certain
set of number in the numeration system and see if that fails".


"...you only need to check a quarter of them..."
Careful!  At least on the triangular grid (together
with the mentioned counter-example) this would not
be enough!

Best regards,   jj

P.S.: A Student of mine is working on a algorithm/program to search
directly for the tiles.  This turned out to be more tricky than one
naively assumes, even on the square grid.  No success so far and time
is running out pretty darn quick.


* Graeme McRae <graememcrae at gmail.com> [Aug 22. 2016 08:17]:
> 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/
> >
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/