Sequence A115774: 15*i = 23 X i, a connection to Collatz conjecture related sequence. Was: Re: Congruent Products Under XOR.

[Antti Karttunen]

I submitted last night this among other sequences:

>
> %I A115774
> %S A115774 
> 0,5,10,20,21,40,42,80,84,85,160,168,170,320,336,340,341,640,645,672,
> %T A115774 
> 680,682,1280,1285,1290,1344,1360,1364,1365,2560,2565,2570,2580,2581,
> %U A115774 
> 2688,2693,2720,2728,2730,5120,5125,5130,5140,5141,5160,5162,5376
> %N A115774 Integers i such that 15*i = A048720bi(23,i).
> %C A115774 Here * stands for ordinary multiplication, and A048720 is 
> the carryless (GF(2)[X]) multiplication.
> %H A115774 <a 
> href="http://www.research.att.com/~njas/sequences/Sindx_Ge.html#GF2X">Index 
> entries for sequences operating on GF(2)[X]-polynomials</a>
> %Y A115774 A048717, A115767, A115770.  Subset of A115772 ? A115776 
> gives the terms of A115772 which do not occur here.  Differs from 
> A062052 for the first time at n=18,  where A115774(18)=645 while 
> A062052(18)=672.  A115775 shows this sequence in binary.
> %K A115774 nonn
> %O A115774 0,2
> %A A115774 Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), 
> Jan 30 2006
>
Actually, the connection to Collatz seems to be easier than what it 
first looks like, after one realizes that
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. 	
	+0
12


	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>)


	OFFSET 	

1,1

	

	COMMENT 	

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.
(Formerly M3914 N1608) 	
	+0
75


	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 looking the binary representation of A115774:

%I A115775
%S A115775 0,101,1010,10100,10101,101000,101010,1010000,1010100,1010101,
%T A115775 
10100000,10101000,10101010,101000000,101010000,101010100,101010101,
%U A115775 
1010000000,1010000101,1010100000,1010101000,1010101010,10100000000
the first differing member ^ is that, 645 with a binary expansion 
1010000101.


Now 23 is 10111 in binary, as 15 is 1111, and from then on, it's some 
dirty work
with the carry bits.

(Maybe continued some day, unless somebody wants to prove all of these.)


Terveisin,

Antti