[seqfan] Re: Stacking binary blocks 100, 010, 001, 111

[mail at fumba.eu]

Zitat von "M. F. Hasler" <seqfan at hasler.fr>:

> Yes, that's obviously:
> Numbers having digits {1,2,4 or 7} in base 8.
> So yes, it is a subsequence of numbers congruent to these modulo 8.
> To get the n-th term you can write n in base 4 and replace digits 0123 by
> 1247 and read the result in base 8
>
> In PARI/GP :
> is(n)=!#setminus(Set(digits(n,8)),[1,2,4,7])
> a(n,D=[1,2,4,7],b=8)=fromdigits(apply(d->D[d+1], digits(n,#D)),b)
> (This allows to produce the analog for any set of digits D and base b, by
> supplying either of these optional additional arguments.)
> --
> Maximilian
>

Hi Max and Seqfans,

The definition of the sequence and function "is(n)" are fine, but I  
don't believe the steps given for finding the n-th term are correct.  
For example, the a(4) = 17 but:

(a(n)) = [1, 2, 4, 7, 9, 10, 12, 15, 17, 18, 20, 23, 33, 34, 36, 39,  
57, 58, 60, 63, 73, 74, 76, 79, 81, 82, 84, 87, 97, 98, 100, 103, 121,  
122, 124, 127, 137, 138, 140, 143, 145, 146, 148, 151, 161, 162, 164,  
167, 185, 186, 188, 191, 265, 266, 268, 271, 273, 274, 276, 279, 289,  
290, 292, 295, 313, 314, 316, 319, 457, 458, 460, 463, 465, 466, ...]

I believe there is an entire playground (of stuff for me to explore)  
hidden in the above sequence, as every term can be associated with a  
floretion of some order.

Relationship between above sequence and floretions:

// quaternions, first order floretions
100 <-> 1 <-> i
010 <-> 2 <-> j
001 <-> 4 <-> k
111 <-> 7 <-> e (the unit)
// 2nd order floretions
100_100 <-> 9	<-> ii
010_100 <-> 10	<-> ji
001_100 <-> 12	<-> ki
111_100 <-> 15	<-> ei
100_010 <-> 17	<-> ij
010_010 <-> 18	<-> jj
001_010 <-> 20	<-> kj
111_010 <-> 23	<-> ej
100_001 <-> 33	<-> ik
010_001 <-> 34	<-> jk
001_001 <-> 36	<-> kk
111_001 <-> 39	<-> ek
100_111 <-> 57	<-> ie
010_111 <-> 58	<-> je
001_111 <-> 60	<-> ke
111_111 <-> 63	<-> ee (the unit)
// 3rd order floretions
...

Note there are 4 floretions order 1, 16 order 2, 64 order 3 etc.

So here's the details

As previously, I'm doing two things (in my free time, in no way  
"professionally"):
1. implementing floretion multiplication from a hardware standpoint  
(actual logic gates, etc.)
2. creating information preserving floretion algorithms used for image  
processing

Both points are interrelated- one of the main algorithms for the  
latter point became apparent while working on the first. As many of  
these image transforms are quite resource consuming once the  
resolution exceeds ca. 256x256, I decided to convert all my Python  
code to C++. However, being a beginner to C++, I chose "basic  
multiplication" in PARI first since the syntax is similar. This is  
where the sequence "Numbers with digits 1,2,4,7 when written in base  
8" is used. I would appreciate any optmizations / clean-up / testing  
of the code!

Example calls:
/* Corresponds to i*j, should return k */
multiply_floretions(a(2), a(3), pretty_printing=1)

/* Corresponds to ii*ji, should return -ke */
multiply_floretions(a(5), a(6),pretty_printing=1)

/* Corresponds to "e * ii" which is not defined because both
floretions are not of same order, should return error */
multiply_floretions(7, 9, pretty_printing=1)

/* Corresponds to "kjeiii * jijkii" */
multiply_floretions(a(1419), a(1510),pretty_printing=1)

Cheers,
Creigh


********* BEGIN PARI CODE ****************

/* Return 1 if n has only digits 1,2,4,7 written in base 8";
     otherwise 0
*/
is(n)=!#setminus(Set(digits(n,8)),[1,2,4,7]);


/*
    n-th term of "Numbers with digits 1,2,4,7 when written in base 8".
    Main sequence used to define floretion multiplication.
*/
a(n) =
{
    local(total_count, index);
    until(total_count == n+1, if(is(index)==1, total_count++); index++);
    index-1;
}


/*
    Return smallest power of 8 greater abs(n). This is the "order of the
    floretion". Two floretions can only be multiplied if they are of
    the same order.
*/
sp8(n)=
{
    n = abs(n);
    if (n == 1, return(1), return(ceil(log(n)/log(8))));
}


/*
    Perfom simple cyclic transformation: i->j, j->k, k->i, e->e
    This function is called by "is_cyclic"
*/
roll_3bits(x) =
{
    if (x==1, return(2),
        x==2, return(4),
	  x==4, return(1));
    return(7);
}


/*
    Returns 1 if the order of x_d, y_d (each one of the digits 1, 2,  
4, 7) is "cyclic", otherwise -1.
    E.g. 1*2 is cyclic since 1 <-> (1,0,0) <-> "i" and 2 <-> (0,1,0)  
<-> "j" and i*j
    is positive (seen as quaternions).
    This function is called by "flo_sign", see there for more info.  
The arguments x_d and y_d are taken
    from digits(x), digits(y) respectiviely.
*/
is_cyclic(x_d, y_d) =
{
    local(is_cyc);
    is_cyc = -1;
    if(bitand(roll_3bits(x_d), y_d) != 0, is_cyc = 1);
    is_cyc;
}

/* Function to determine the sign returned by function  
"multiply_floretions(x,y)".
     In the case of quaternions (i*j = k, j*i = -k, i*i = -e, etc), we can
     associate each with a binary block i <-> 100, j <-> 010, k <->  
001 and e <-> 111. E.g.
     i*j corresponds to multiply_floretions(1,2) (reading 3 bit blocks  
backwards). Thus,
     quaternions are 1st order floretions. Note i*j is cyclic  
(positive) and j*i anti-cyclic (negative).

     In general, we need to look at 3 bits at a time, e.g. applying  
the following masks:
     000000111: 1st mask
     000111000: 2nd mask
     111000000: 3rd mask
     ...      : nth mask
     to x and y.

     An easier way than applying the above masks (done here) is simply  
to loop over the digits of x and y, base 8. Here, multiplying is  
bitwise after "rolling", e.g.
     "k*i" <-> "4*1"
           <-> "001 * 100"
           <-> bitand(roll_right(001),100)
           <-> bitand(100,100) != 0, so "k*i" is cyclic, i.e. positive.

     Note additional checks such as x, y in (a(n)) and sp8(x) = sp8(y)
     should have been done beforehand- not redoing here.

*/
flo_sign(x,y) =
{	local(x_dig, y_dig, result_sign);
	result_sign = 1;
	x_dig = digits(x,8);
	y_dig = digits(y,8);
      for (i = 1, #x_dig, result_sign *= is_cyclic(x_dig[i], y_dig[i]));

	result_sign;
}


/*
    Called by "to_flo_string(x)". Used only for printing to screen in  
"floretion" format
*/
to_flo(some_digit) =
{
    result = "e";

    if(some_digit == 1, result = "i",
       some_digit == 2, result = "j",
       some_digit == 4, result = "k");
    result;
}


/*
    Used only for printing to screen in "floretion" format
*/
to_flo_string(x) =
{
    local(digits_base_8, result_string);
    digits_base_8 = digits(x,8);
    result_string = "";
    for (i = 1, length(digits_base_8), result_string =  
concat(to_flo(digits_base_8[i]), result_string));
    if (x < 0, result_string = concat("-", result_string));
    result_string;
}


/* Multiply two floretions x and y using bitwise operations.
     Both must be of same order! Note floretions of order 1 are
     just the quaternions
*/
multiply_floretions(x,y,pretty_printing=0)=
{
    /* Two basic checks */
    if (sp8(y) != sp8(x), printf("x and y cannot be multiplied as they  
are of different order: %d != %d  ", sp8(x), sp8(y)); return);
    if (is(x)*is(y) !=1, print("It appears x and y are not both  
floretions- choose only numbers whose digits base 8 are in the set {1,  
2, 4, 7}"));

    local(result_sign, final_result);
    result_sign = 1;

    if (x*y<0, result_sign = -1);
    result_sign *= flo_sign(x,y);

    /* Signs of x and y no longer needed */
    x = abs(x);
    y = abs(y);


    final_result = result_sign*bitneg(bitxor(x,y),3*sp8(y));

    if (pretty_printing, x = to_flo_string(x); y = to_flo_string(y);  
result_string = to_flo_string(final_result));
    if (pretty_printing, printf(" %s * %s = %s", x, y, result_string));
    final_result;
}