Ruud H.G. van Tol on Mon, 03 Jan 2022 17:28:40 +0100

[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

 Collatz partitions

• To: pari-users@pari.math.u-bordeaux.fr
• Subject: Collatz partitions
• From: "Ruud H.G. van Tol" <rvtol@isolution.nl>
• Date: Mon, 3 Jan 2022 17:28:40 +0100
• Delivery-date: Mon, 03 Jan 2022 17:28:40 +0100
• Dkim-signature: v=1; a=rsa-sha256; c=simple/simple; d=isolution.nl; s=soverin; t=1641227315; bh=J0+UQcYhlBjAGVdIlHHI/ehH0x+WrVhYAGbpX9K770s=; h=Date:To:From:Subject:From; b=pSMuzEOHCFuBS0Cet6eVoK+x5tlt/ZQnzr+BLiY6JnpdLrVHBIimCx1Xf7ciSdmF9 oorDg1CoyUeKr7qCM9s+V76PQFvJRVFgCyQR75Ft8+ZcQTFqerO058BJ2dkER5+roz 2REnJzajM0+NveSwuA9f77irGK38+39lN90d4TnDFhzeiOJsmdaqmCrwKJ5J4G5PTs /CjyOLKfcofyXS82qii3A5ZXQ6VQ3spD8zkrlY+fPtgzKFce9uUwGkkHAXZH4yi5ON 4cnr1Y2vRaP2Z72QkYQjAVke80BHOH6426xfelQ9vAK6ppUaB4D0IX4YsKAhX2SioU FyBMCqquwu2RA==

```
My "Collatz sieve" formula:

2^p2 * i + c2 -> 3^p3 * i + c3 (i >= 0)

- - - - -

`c2` = 0, represents all evens:
2^(1) * i + (0) -> 3^(0) * i + (0)
or as a vector: [p2,c2,p3,c3] = [1,0,0,0]

Each odd `c2` represents a "partition",
identified by its smallest element (`c2`).

Each partition has a single offset (2^`p2`)
to generate the next elements.

partition_c2(n == 0) = `c2`
partition_c2(n >  0) = partition_c2(n-1) + 2^`p2(c2)`

- - - - -

For any odd `c2`:
- each `p2` is the minimal power-of-2
where 2^`p2` > 3^`p3`: floor(1+p3*log(3)/log(2))
- so each `p3` is the maximal power-of-3
where 3^`p3` < 2^`p2`: floor(p2*log(2)/log(3))

? [ [3^p3, (my(p2=floor(1+p3*log(3)/log(2)))*0+ 2^p2)] | p3 <- [0..5] ]
[[1, 2], [3, 4], [9, 16], [27, 32], [81, 128], [243, 256]]

? [ [2^p2, (my(p3=floor(p2*log(2)/log(3)))*0+ 3^p3)] | p2 <- [0..5] ]
[[1, 1], [2, 1], [4, 3], [8, 3], [16, 9], [32, 27]]

(so that [8, 3] will never be involved)

- - - - -

My next aim is (still) to show how to efficiently
limit the search space
when going back from c3 to c2.

There is an optimal (first-lower) c3 for every c2,
but there are 1-or-more c2 (partitions) for each c3.

--
Greetings, Ruud

- - - - -

/*
How to (optimally) go from c2 to c3:
1. c3 is the first-lower (odd or even) value
in the trajectory of c2;
2. p3 is the number of triplings involved;
3. p2 is the number of halvings involved
(for odd c2: the first power-of-2 greater than p3);

This maps any value to a lower value, etc.
*/
c2_c3( c2= 0 )= {
\\ evens: 2^(1)*x+(0) -> 3^(0)*x+(0)
if( (c2 < 1), return([1,0,0,0]) );

my( p2= valuation(c2,2) );
c2/= 2^p2; \\oddify

\\ 2^(2)*(x+i)+1 -> 3^(1)*(x+i)+1 (i >= 0)
if
( (1 == (c2 % 4))
, return([ 2, c2, 1, 3*(c2-1)/4 +1 ])
);

my( p3= 0, c3= c2 );
while
( (c3 >= c2)
, c3= (3 * c3 + 1) / 2;
p2++;
p3++;
while
( !(c3 % 2)
, c3/= 2;
p2++;
if( (c3 <= c2), break); \\dropper
);
);
[ p2, c2, p3, c3 ];
}

/*
Map zero (which represents all evens)
and any odd > 0,
to its (unique, optimal) "Collatz sieve" formula:
*/
show_c2_c3( x= 0, N= 29 )= {
if
( x && !(x%2)
, error("x must be either 0, or an odd, so not (",x,")");
);

my( n0= if( x, (x-1)/2, 0 ) );

for
( n= n0, n0 + N
, my( [p2,c2,p3,c3]= c2_c3( if( n, (n-1)*2+1, 0 ) ) );
if
( (c2 <= 2^p2)  \\hide duplicates
, printf
( "%3s| (%5sx + %3s) -> (%4sx + %3s)  (%s, ...)\n"
, n, Str("2^",p2), c2, Str("3^",p3), c3
, strprintf
( "%3s, %3s+ 1*2^%2s, %3s+ 2*2^%2s"
, c2, c2, p2, c2, p2
);
);
);
);
} \\ Example: show_c2_c3(0,91)

- - - - - --

```