Congruent Products Under XOR; Fibbinary Numbers

[Antti Karttunen]

Here is a more interesting case:

http://www.research.att.com/~njas/sequences/A048717
"Binary expansion matches ((0)*00(1*)11)*(0*)."
0, 3, 6, 7, 12, 14, 15, 24, 28, 30, 31, 48, 51, 56, 60, ...

1-bits occur only in groups of two or more, separated from
other such groups by at least two 0-bits.

All terms satisfy rule150(n) = 3*n.

Note that here rule150(n) = A048727(n) = (4*n XOR 2*n XOR n)
(And similarly rule90(n) = A048725(n) = (4*n XOR n)
in the sequences of the same vintage. Yes, I should clean these
seqs to the modern OEIS standards!)

Now here it is not a question of simple masks with disjoint 1-bits,
but an interplay with carry bits, which (when A048717(n) is multiplied by 3)
produces the same effect as if it had been "Xmultiplied" (without carry 
bits) by 7
(i.e. GF(2)[X] polynomial x^2 + x + 1, if we keep the polynomial 
interpretation).

Note that the subset of this:
http://www.research.att.com/~njas/sequences/A048719
"Binary expansion matches ((0)*0011)*(0*)."
0, 3, 6, 12, 24, 48, 51, 96, 99, 102, 192, 195, 198, ...
1-bits occur only in pairs, separated from other such pairs by at least 
two 0-bits.

All terms satisfy both rule150(n) = 3*n and rule90(n) = 5*n.


can be stated in similar terms as Paul gave, but as a _conjunction_ of 
two such clauses:

Intersection of "Integers n such that: 5*n XOR 2*n = 3*n."
and "Integers n such that: 4*n XOR n = 5*n."

The latter clause by itself should produce
http://www.research.att.com/~njas/sequences/A048716
(Well, at least all the members of A048716 satisfy that clause, and I 
don't see any
"extra solutions" now...)


but what will the former clause ("Integers n such that: 5*n XOR 2*n = 3*n.")
produce alone? (Also A048719 ?)

Terveisin,

Antti Karttunen


Paul D. Hanna wrote:

>Dean (and Seqfans), 
>      Thanks for catching my mistake.  
>It seems obvious (now) that the conjecture is false - in fact, 
>there are so many exceptions I wonder how I missed them. 
>A better conjecture may be: 
>there exists an infinite set of integers n that satisfy 
>p*n XOR q*n = (p XOR q)*n for all positive integers p,q, r. 
>I find no exceptions to this guess. 
> 
>Yet my focus was primarily on what different values of {p,q,r} 
>define the same sequence that satisfies p*n XOR q*n = r*n 
>when GCD(p,q) is odd.  This remains a mystery to me. 
>  
>
To which franktaw at netscape.net wrote:

>Yes, this is true.  Take n = 2^k for any k.  More generally, n can be
>any integer whose 1 bits are all separated by at least the number of
>bits in p and q.  Or even more generally, the set of distances between
>1 bits in n and the set of distances between 1 bits in (p OR q) should
>be disjoint.  This doesn't quite cover all the cases, but it gets most
>of them.  Another class of solutions is any time p=q (p=0 or q=0 would
>also work, if we allowed zero).  One solution that doesn't fit either
>class is p=19, q=67, n=3; look at it in binary and you'll see that
>it's really a combination of the two classes.
>
>  
>
Paul continues:

>Perhaps Ralf Stephan's comment offers a clue; 
>the binary mask, such as ((0)*0001)*(0*) that match A048718(n),  
>may determine which {p, q, r} define equivalent sequences. 
> 
>Thanks, 
>      Paul 
> 
>  
>
>>>As a generalization, consider the sequences defined by:
>>>"Numbers n such that: p*n XOR q*n = r*n."  for positive integers 
>>>      
>>>
>>p, q, r.
>>    
>>
>>>Q: For what p, q, r, does the above definition generate sequences 
>>>      
>>>
>>not {0}?
>>    
>>
>>>A: Iff  r = p XOR q (conjecture).
>>>
>>>Can anyone prove this conjecture?
>>>      
>>>
>>It's not true.  Let  p=2,  q=3,  and  r=5.  Then  n=3  is in the 
>>sequence,
>>since  2*3 XOR 3*3 = 6 XOR 9 = 15 = 5*3.  But  2 XOR 3 = 1,  not 5.
>>
>>Dean Hickerson
>>    
>>
>
>  
>