Congruent Products Under XOR.

[Antti Karttunen]

franktaw at netscape.net wrote:

> I think you have ahold of the wrong end of the stick here.
>  
> if 2*i XOR 5*i = 3*i, then 2*i XOR 3*i = 5*i.

Yes of course!, these "magical properties" of XOR-operation always take 
me by the surprise. 8^>
(This 2*i XOR 5*i came as an attempt to give a "Hannasque" 
interpretation for (4*i XOR 2*i XOR 1*i),
i.e. carryless multiplication with "7".)

> What I'm seeing here is cases where a*i and b*i have no common bits, 
> so a*i XOR b*i = (a+b)*i.

New perspective, have to take a deeper look.

I also wrote in the previous message:

> <>http://www.research.att.com/~njas/sequences/A062052 (which actually 
> seems to be a subset of A115774, BTW)

> <>Numbers with 2 odd integers in their Collatz (or 3x+1) trajectory.
>     5, 10, 20, 21, 40, 42, 80, 84, 85, 160, 168, 170, 320, 336, 340, 
> 341, 640, 672, 680, 682, 1280, 1344, 1360, 1364, 1365, 2560, 2688, 
> 2720, 2728, 2730, 5120, 5376, 5440, 5456, 5460, 5461, 10240, 10752, 
> 10880, 10912, 10920, 10922, 20480, 21504, 21760, 21824 (list 
> <http://www.research.att.com/%7Enjas/sequences/table?a=62052&fmt=4>)
>
> The Collatz (or 3x+1) function is f(x) = x/2 if x is even, 3x+1 if x 
> is odd.
> The Collatz trajectory of n is obtained by applying f repeatedly to n 
> until 1 is reached.
> Sequence is 2-automatic.
>
> means just integers which are either (A) odd, and when multiplied by 3 
> result an integer of the form (2^k) - 1
> (so 3x+1 results a two's power, which gets successively halved until 
> only 1 remains, the second odd number
> in the trajectory). or (B) case (A) multiplied by some power of two.
>
> so, when collecting only the odd numbers of A062052: 
> 5,21,85,341,1365,5461, ...
> and searching with them, we get: 
> http://www.research.att.com/~njas/sequences/A002450
>
> (4^n - 1)/3.
>     0, 1, 5, 21, 85, 341, 1365, 5461, 21845, 87381, 349525, 1398101, 
> 5592405, 22369621, 89478485, 357913941, 1431655765, 5726623061, 
> 22906492245, 91625968981, 366503875925, 1466015503701, 5864062014805, 
> 23456248059221, 93824992236885
>
>
> (In binary the terms are 1, 101, 10101, 1010101, etc. - John McNamara 
> (mistermac39(AT)yahoo.com), Jan 16 2002)
> as might be expected...

Now, it seems that odd terms in A062052 (i.e. the terms of A002450 after 
1) seem to occur only at indices
which are squares: 1, 4, 9, 16, 25, 36, etc.
so it shouldn't be two hard to develop a direct formula (or at least a 
recursion) for the terms of A062052.

However, it's NOT this easy:

(define (A002450 n) (/ (- (expt 4 n) 1) 3))
(define (A062052_incorrect n)
  (let ((sqrt_floored (floor->exact (sqrt n))))
    (* (A002450 (+ 1 sqrt_floored)) (expt 2 (- n (expt sqrt_floored 2))))
  )
)



Terveisin,

Antti