This site is supported by donations to The OEIS Foundation.
User:Ruud H.G. van Tol/Collatz
From OeisWiki
Contents
Add sequence
...
On A085060
For n == 1 (mod 2), a(n)= 3 * (a((n-1)/2) + 1). (???)
On A254070 (first 1 (mod 4) successor of 4n-3)
a(n) = my(x=3*n-2); x=(x>>valuation(x, 2))+1; (3/2)^(valuation(x, 2)-1)*x-1; a(n) = n=3*n-2; n>>=valuation(n, 2); (3/2)^(valuation(n++, 2)-1)*n-1; ? [ a(n) |n<-[1..20] ] % [1, 1, 17, 5, 13, 1, 29, 17, 25, 17, 161, 17, 37, 5, 65, 53, 49, 13, 125, 29]
On A350082 (Collatz trajectory)
Sequence of numbers that are not in this sequence:
[13, 21, 31, 35, 45, 49, 53, 61, 65, 67, 69, 77, 83, 85, 91, 93, 99, 101, 103, ...]
To do: Come up with a variant without the zeroes.
(m,v)
((2*m+1)*2^v - 1) => ((2*m+1)*3^v - 1) / 2
I'm currently exploring how presenting numbers x as m >= 0: x = m * 2^(v+1) + 2^v - 1. Even numbers: v = 0. Odd numbers: v >= 1. exposes more of how they behave under (3x+1)/2. With x in base-2, this is a split at the rightmost 0-bit, so v is the number of trailing 1-bits ("valuation"), and m is the "multiplier" in front. Example: 27 = 0b11_0_11 = 3 * 2^3 + (2^2 - 1). I'll also use an (m,v)-tuple-notation. Example: 27 = (3,2). See also A025480 (Grundy or nim-values). For v >= 1: m * 2^(v+1) + 2^v - 1 -> (3 * (m * 2^(v+1) + 2^v - 1) + 1) / 2 = 3 * m * 2^v + 3 * 2^(v-1) - 1 (is odd) -> ... -> (3^v * (m * 2 + 1) - 1) / 2. Alternative view: (2*m + 1) * 2^v - 1. Example for (m,v) = (1,2) : 11 = 1 * 2^3 + 2^2 - 1 = ( 1,2) -> 17 = 4 * 2^2 + 2^1 - 1 = ( 4,1) -> 26 = 13 * 2^1 + 2^0 - 1 = (13,0) -> 13 = (3,1). Or in a single step: 11 = (1,2) -> (3^2*(1*2+1)-1)/2 = 13 = (3,1). Next: (3,1) -> (3*7-1)/2 = 10 -> 5 = (1,1). Next: 4 -> 1 = (0,1). Example for (m,v) = (3,2) : 27 = 3 * 2^3 + 2^2 - 1 = ( 3,2) -> 41 = 10 * 2^2 + 2^1 - 1 = (10,1) -> 62 = 31 * 2^1 + 2^0 - 1 = (31,0) -> 31 = (0,5). Or in a single step: 27 = (3,2) -> (3^2*(3*2+1)-1)/2 = 31 = (0,5). Next: (0,5) -> (0+3^5*1-1)/2 = 121 = (30,1). Next: (3*61-1)/2 = 91 = (11,2).
(m,v)_2 -> (m,v)_3
m * 2^(v+1) + 2^v - 1 -> m * 3^v + (3^v - 1)/2 Examples: 27 = ( 3,2)_2 -> ( 3,2)_3 = 3* 9+( 9-1)/2 = 31 31 = ( 0,5)_2 -> ( 0,5)_3 = 0*243+(243-1)/2 = 121 121 = ( 30,1)_2 -> ( 30,1)_3 = 30* 3+( 3-1)/2 = 91 91 = ( 11,2)_2 -> ( 11,2)_3 = 11* 9+( 9-1)/2 = 103 103 = ( 6,3)_2 -> ( 6,3)_3 = 6* 27+( 27-1)/2 = 175 175 = ( 5,4)_2 -> ( 5,4)_3 = 5* 81+( 81-1)/2 = 445 445 = (111,1)_2 -> (111,1)_3 = 111* 3+( 3-1)/2 = 334 -> 167 167 = ( 10,3)_2 -> ( 10,3)_3 = 10* 27+( 27-1)/2 = 283 (etc.)
See also: A259663, and
Francis Laclé; 2-adic parity explorations of the 3n+1 problem; 2021;
https://hal.science/hal-03201180v2/document
(m,v) notation of powers of 3
n-even: 3^n -> ((3^n-1)/4, 1)_2 -> (3^n-1)/4 * 3^1 + (3^1-1)/2 = 3*(3^n-1)/4 + 1 Examples: 1 -> 1 9 -> 7 81 -> 61 729 -> 547 n-odd: 3^n -> ((3^n-3)/8, 2)_2 -> (3^n-3)/8 * 3^2 + (3^2-1)/2 = 9*(3^n-3)/8 + 4 Examples: 3 -> 4, 1 27 -> 31 243 -> 274, 137 2187 -> 2461 19683 -> 22144, 173
On A100982
a_iter(N) = { my(a=List([[0,0,2,1,1,0]]), p0=#a, p1=#a); for(p3=0,N-1 , my(p2=logint(3^p3,2)+1, m=if(logint(3^(p3+1),2)>p2,2,1)); for(p=p0,p1 , my(s=a[p][1]); for(i=0,if(s,valuation(s,2)-1,0) , my(t=[(a[p][1]+(1<<i))<<m,0,0,p2+m,0,p3+1]); listput(a,t) ) ); p0=p1+1; p1=#a ); for(i=2,#a , my(t=a[i][1], p2=a[i][4], p3=a[i][6], r=0); for(j=1,p2, r=if(bittest(t, p2-j), 3*r+1, r) / 2); a[i][2]=numerator(r); a[i][3]=-r * (2^p2) / (3^p3) % (2^p2); a[i][5]=a[i][3] * 3^p3 / 2^p2 + r ); Vec(a); } ? printp( Mat(a_iter(5)~) ) [ 0 0 2 1 1 0] [ 2 1 1 2 1 1] [ 12 5 3 4 2 2] [ 26 23 11 5 10 3] [ 28 19 23 5 20 3] [108 85 59 7 38 4] [116 73 7 7 5 4] [120 65 15 7 10 4] [218 319 123 8 118 5] [220 287 219 8 209 5] [234 283 199 8 190 5] [236 251 39 8 38 5] [242 259 79 8 76 5] [244 227 175 8 167 5] [248 211 95 8 91 5] Examples: 2 + i*2^ 1 -> 1 + i*3^ 0 1 + i*2^ 2 -> 1 + i*3^ 1 3 + i*2^ 4 -> 2 + i*3^ 2 11 + i*2^ 5 -> 10 + i*3^ 3 23 + i*2^ 5 -> 20 + i*3^ 3 59 + i*2^ 7 -> 38 + i*3^ 4 7 + i*2^ 7 -> 5 + i*3^ 4 15 + i*2^ 7 -> 10 + i*3^ 4 123 + i*2^ 8 -> 118 + i*3^ 5 219 + i*2^ 8 -> 209 + i*3^ 5 199 + i*2^ 8 -> 190 + i*3^ 5 39 + i*2^ 8 -> 38 + i*3^ 5 79 + i*2^ 8 -> 76 + i*3^ 5 175 + i*2^ 8 -> 167 + i*3^ 5 95 + i*2^ 8 -> 91 + i*3^ 5
Permutation of positive integers
? my(N=2^5, v=Vec(0,N), seen=Map(), i=0, m=1, n=1); while(i<N, v[i++]=n; mapput(~seen,n,0); n=if(n%2,n*3+1,n)/2; if(mapisdefined(seen,n),while(mapisdefined(seen,m+=2),);n=m));v % [1, 2, 3, 5, 8, 4, 7, 11, 17, 26, 13, 20, 10, 9, 14, 15, 23, 35, 53, 80, 40, 19, 29, 44, 22, 21, 32, 16, 25, 38, 27, 41]
(m, v) -> (m*3^v + (3^v-1)/2, 0)
? p(n,w=60) = { my(x=n, v0=1); while(1 , my(b=binary(x), v=valuation(x+1,2)); if(!v0, w-= v+1); v0=v; printf ("%6s%*s%12s.%s\n" , x , w, "" , if(v==#b, "", fromdigits(b[1..#b-v-1])) , if(!v, "", fromdigits(b[#b-v+1..-1])) ); if(1==x || x<n, break); if(x%2, x=(3*x+1)/2, v=valuation(x,2);w-=v-1;x>>=v) ); } ? p(111,28) 111 11.1111 : ( 3,4) = 3*2^5 + 2^4-1 = 111 167 1010.111 : ( 10,3) = 10*2^4 + 2^3-1 = 167 251 11111.11 : ( 31,2) = 31*2^3 + 2^2-1 = 251 377 1011110.1 : ( 94,1) = 94*2^2 + 2^1-1 = 377 566 100011011. : (283,0) = (3*3^4+(3^4-1)/2,0) = (243+40,0) 283 100011.11 : ... 425 1101010.1 638 100111111. 319 10.111111 479 111.11111 719 10110.1111 1079 1000011.111 1619 11001010.11 2429 1001011111.1 3644 11100011110. 911 11100.1111 1367 1010101.111 2051 100000000.11 3077 1100000001.1 4616 100100000100. 577 10010000.1 866 110110001. 433 1101100.1 650 101000101. 325 1010001.1 488 11110100. 61 1111.1
Rejected sequences
A370354 Numbers whose binary expansion encodes an admissible sequence in A100982. 0 0, 2, 12, 26, 28, 108, 116, 120, 218, 220, 234, 236, 242, 244, 248, 876, 884, 888, 940, 948, 952, 972, 980, 984, 996, 1000, 1008, 3508, 3512, 3540, 3544, 3556, 3560, 3568, 3764, 3768, 3796, 3800, 3812, 3816, 3824, 3892, 3896, 3924, 3928, 3940, 3944, 3952, 3988 OFFSET 1,2 COMMENTS Starting at the most significant bit, a 1 encodes multiplication by 3/2 and a 0 multiplication by 1/2. From a starting value of 1, a sequence is admissible once these steps reach a value less than or equal to 1, after at least one step. The number of 1-bits is called the order in A100982. For n >= 3, the terms are in A079946. LINKS Table of n, a(n) for n=1..49. Ruud H.G. van Tol, Table of n, a(n) for n = 1..10000 Ruud H.G. van Tol, Sequence on a lattice (svg). Ruud H.G. van Tol, Code to generate the svg. Ruud H.G. van Tol, PARI/GP code to generate the sequence in a chunk per order. Eric Weisstein's World of Mathematics, p-Good Path. Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], 2017. Mike Winkler, The Recursive Stopping Time Structure of the 3x + 1 Function, 2018. FORMULA a(n) == 0 (mod 2). For n >= 4, a(n) > 2^A000523(a(n)) * 3/2, because the terms are in A079946, and a(3) = 12. EXAMPLE a(3) = 12 is '1100' binary, (3/2 * 3/2 * 1/2) * 1/2 = 9/8 * 1/2 = 9/16. On the lattice (see svg link) this is EENN. PROG (PARI) isok(i) = my(q=1, p2=if(i, logint(i, 2)+1, 1)); for(b=1, p2, if(bittest(i, p2-b), q*=3); q/=2; q<1 && b<p2 && return(0)); q<=1; \\ show: [ i |i<-[0..2^10], isok(i) ] CROSSREFS Cf. A079946, A100982 (see the paths in the "tree view"). Sequence in context: A031048 A294554 A098707 * A152811 A294552 A294170 Adjacent sequences: A370351 A370352 A370353 * A370355 A370356 A370357 KEYWORD nonn,base,new AUTHOR Ruud H.G. van Tol, Feb 16 2024 A370484 Numerators of the 3x+1 specific addition constants in sync with A370354. 0 0, 1, 5, 23, 19, 85, 73, 65, 319, 287, 283, 251, 259, 227, 211, 1085, 989, 925, 977, 881, 817, 905, 809, 745, 761, 697, 665, 3767, 3511, 3479, 3223, 3287, 3031, 2903, 3443, 3187, 3155, 2899, 2963, 2707, 2579, 3227, 2971, 2939, 2683, 2747, 2491, 2363, 2795 OFFSET 1,3 COMMENTS This uses the admissible sequences of A100982 in 3x+1 context. To calculate a(n), start with x=0 and from the most significant bit of A370354(n), do x=(3*x+1)/2 if a bit is set, and x=x/2 if it isn't. Then the denominator is 2^A070939(A370354(n)), which is bigger than the numerator. Conjecture: all terms are distinct. LINKS Table of n, a(n) for n=1..49. Ruud H.G. van Tol, Table of n, a(n) for n = 1..10000 Ruud H.G. van Tol, Sequence on a lattice (svg). Ruud H.G. van Tol, PARI/GP code to generate the sequence in a chunk per order. FORMULA a(n) < 2^A070939(A370354(n)) (so numerator < denominator, because of A370354). EXAMPLE a(4) = 23, because A370354(4) = 26 = '11010' in base 2, and (((3*((3*(3*0+1)/2+1)/2)/2)+1)/2)/2 = 23 / 2^5. Alternatively, 2^0*3^2 + 2^1*3^1 + 2^3*3^0 = 9+6+8 = 23. Using A370935(4) = 11 and T(x) as mentioned in A014682, T^5(11) = ((((((((11 *3+1)/2) *3+1)/2) /2) *3+1)/2) /2) = (11 * 3^3 + 23) / 2^5 = 10, so the first lower or equal value in the Collatz trajectory of 11 is 10. PROG (PARI) alist(N) = { my(a=Vec(0, N), i=0, n=1); while(n<N, my(p2=logint(i++, 2), q=1, r=0); for(b=0, p2, if(bittest(i, p2-b), q*=3; r=3*r+(1<<b)); (q/=2)<1 && b<p2 && next(2)); if(q<=1, a[n++]=r)); a; } CROSSREFS Cf. A014682, A070939, A100982, A119733, A370354, A370935. Sequence in context: A233756 A002582 A368425 * A102723 A136146 A289278 Adjacent sequences: A370481 A370482 A370483 * A370485 A370486 A370487 KEYWORD nonn,frac,new AUTHOR Ruud H.G. van Tol, Feb 19 2024 A370935 Starting values of the reduced Collatz function (A014682) in sync with A370354. 0 2, 1, 3, 11, 23, 59, 7, 15, 123, 219, 199, 39, 79, 175, 95, 507, 347, 923, 583, 423, 999, 975, 815, 367, 735, 287, 575, 1019, 1787, 2907, 3675, 1435, 2203, 2587, 3143, 3911, 935, 1703, 3559, 231, 615, 463, 1231, 2351, 3119, 879, 1647, 2031, 3295, 4063, 1823 OFFSET 1,1 COMMENTS Each term represents a disjoint subset (of nonincreasing and progressively decreasing size) of the natural numbers (see Example section). Conjecture: this is a minimal covering system. An alternative value for a(1) is 0. LINKS Table of n, a(n) for n=1..51. Ruud H.G. van Tol, Table of n, a(n) for n = 1..10000 Ruud H.G. van Tol, PARI code that generates the sequence in chunks. Index entries for sequences related to 3x+1 (or Collatz) problem. FORMULA For n >= 3, a(n) == 3 (mod 4). With the number of halvings h = A070939(A370354(n)) and n >= 2, a(n) < 2^h. See also A243115. EXAMPLE With v2=a(n), i>=0, p3=A100982-order, p2=1+floor(p3*log(3)/log(2)), v3=(v2*3^p3 + A370484(n))/2^p2, this dropping table can be generated: n: v2 + i*2^p2 -> v3 + i*3^p3 =--==-------==----==-------== 1: 2 + i*2^ 1 -> 1 + i*3^ 0 2: 1 + i*2^ 2 -> 1 + i*3^ 1 3: 3 + i*2^ 4 -> 2 + i*3^ 2 4: 11 + i*2^ 5 -> 10 + i*3^ 3 5: 23 + i*2^ 5 -> 20 + i*3^ 3 6: 59 + i*2^ 7 -> 38 + i*3^ 4 ... PROG (PARI) alist(N) = my(a=Vec(2, N), i=0, n=1); while(n<N, my(p2=logint(i++, 2)+1, q=1, r=0); for(b=1, p2, if(bittest(i, p2-b), q*=3; r=3*r+1); (q/=2)<1 && b<p2 && next(2); r/=2); if(q<=1, my(p3= logint(2^p2, 3)); a[n++]= -numerator(r) / (3^p3) % (2^p2))); a; CROSSREFS Cf. A100982, A126241, A177789, A243115, A370354, A370484. Sequence in context: A119928 A215265 A036448 * A369242 A187111 A122050 Adjacent sequences: A370932 A370933 A370934 * A370936 A370937 A370938 KEYWORD nonn,new AUTHOR Ruud H.G. van Tol, Mar 06 2024 A374952 The k-th odd successor of the odd part of n in its 3x+1 trajectory, where k is the length of the rightmost run of 1's of n in binary. 0 1, 1, 1, 1, 1, 1, 13, 1, 7, 1, 13, 1, 5, 13, 5, 1, 13, 7, 11, 1, 1, 13, 5, 1, 19, 5, 31, 13, 11, 5, 121, 1, 25, 13, 5, 7, 7, 11, 67, 1, 31, 1, 49, 13, 17, 5, 121, 1, 37, 19, 29, 5, 5, 31, 47, 13, 43, 11, 67, 5, 23, 121, 91, 1, 49, 25, 19, 13, 13, 5, 121, 7, 55 OFFSET 1,7 COMMENTS Split the odd part of n in binary at the rightmost 0. Let v be the value to the left and k the number of trailing 1's, n = v * 2^(k+1) + 2^k -1 = (2*v+1) * 2^k -1. Write n as [v, k], with k > 0. Its first (3x+1)/2 successor is (3*((2*v+1)*2^k-1)+1)/2 = (2*(3*v+1)+1) * 2^(k-1) -1 = [3*v+1, k-1]. Then its k-th successor is [3^k*v + (3^k-1)/2, 0], and a(n) is the odd part of that. Of N initial terms, about N/4 are distinct and about N/30 are both distinct and greater than N. LINKS Table of n, a(n) for n=1..73. Ruud H.G. van Tol, Table of n, a(n) for n = 1..8192 Index entries for sequences related to 3x+1 (or Collatz) problem FORMULA a(2*n) = a(n). a(n) = A139391^A089309(n)(A000265(n)). a(n) = A000265(3^k*(m+1)/2^k-1), with m = A000265(n) and k = A007814(m+1) = A089309(n). EXAMPLE For n=46, first A000265(46) = 23 and from there A089309(n) = 3 further steps to odd are binary decimal step 10111 23 number 100011 35 1 110101 53 2 1010000 80 -> 5 3 Notice the rightmost 1 bits are trimmed one by one with each step to odd. Using the [v, k] notation from the comments: [1, 3] -> [4, 2], [13, 1], [40, 0] -> [1, 1], represents 23 -> 4*2^3+3 = 35, 13*2^2+1 = 53, 40*2^1 = 3^3*3-1 = 80 -> A000265(80) = 5. The trajectory of 27 when using this map, is 27, 31, 121, 91, 103, 175, 445, 167, 283, 319, 911, 577, 433, 325, 61, 23, 5, 1. PROG (PARI) a(n) = n>>=valuation(n, 2); my(k=valuation(n+1, 2)); n=(n>>k+1)*3^k-1; n>>valuation(n, 2); CROSSREFS Cf. A000265 (odd part of n), A007814, A085062, A089309, A110962, A139391 (next odd successor), A238206, A254070, A363270 (variant). Sequence in context: A116993 A010234 A111738 * A202134 A185409 A010235 Adjacent sequences: A374940 A374949 A374951 * A374953 A374955 A374956 KEYWORD nonn,changed AUTHOR Ruud H.G. van Tol, Jul 25 2024 STATUS proposed [Graph code] var url = "https://library.fridoverweij.com/codelab/math_editors/code_your_math_picture.html" function f (x) { return x * (ln(3)/ln(2)-1) } var fstr = f.toString().replace(/\s+/g," "); fstr = fstr.match(/(?<=[{]).*(?=[}])/).toString(); fstr = fstr.replace(/\s*return\s+/,""); fstr = fstr.replace(/\bln[(]/g,"log("); fstr = "A370484: y = " + fstr var w = 8, h = 5 initPicture(-0.9,w+.6,-0.9,h+.4) axes(1, 1, true) gridstroke = "lightgrey" grid() text([0,0], "0", "belowleft") fontsize = "12" text([-0.5,-0.5], url, "belowright") strokewidth = "1" stroke = "tomato" line([0,0],[w+.5,f(w+.5)]) fontstroke = stroke fontfill = fontstroke fontsize = "18" text([0.1,h+.1], fstr, "right") stroke = "blue" fontstroke = stroke fontfill = fontstroke fontsize = "14" line([0,0],[w+.5,0]) var v = ["0", "(1)/2²", "(5)/2⁴", "(23,19)/2⁵", "(85,73,65)/2⁷", "(319,287,283,251,259,227,211)/2⁸"]; fontstroke = "purple" fontfill = fontstroke pointsize = 3 var x0 = 0, y0 = 1 for (x=x0; x<=w; x++) { var y = floor(f(x))+1 line([x,0],[x,y]) if (y0 < y) { line([x,y0],[w+.5,y0]) } y0 = y point([x,y], "open") text([x-0.05-((x>0)*0.1),y+(x>3?0.1:0.15)], v[x], x>3?20:0) } text([-0.2,0.1], 0) text([-0.22,0.5], "/2") text([0.1,0.1], "*3/2+1/2") stroke = "purple" strokewidth = 2 path([[0,0.2],[0,0.8]],"arrow") path([[0.2,0],[0.8,0]],"arrow") [/Graph code] A370354_iter(N) = { my(a=Vec([[0]], N+1)); for(p3=0, N-1 , my(b=a[p3+1], m=if(logint(3^(p3+1), 2)>(1+logint(3^p3,2)), 2, 1), c=List()); foreach(b, t , for(i=0, if(t, valuation(t, 2)-1, 0) /* for all trailing zeros */ , listput( ~c, (t+(1<<i))<<m ) ); ); a[p3+2]=Vec(c); ); a; } /* * Iterative A370484-data generator, in a chunk per A100982-order. * N is the maximum order. * This order (p3) is effectively the count of 1-bits. */ A370484_iter(N) = { my( a=Vec([[0]], N+1), b=[0] ); for( p3=0, N-1 , my( p2=logint(3^p3, 2), c=List() ); foreach( b, t /* generate a A370354-chunk, but bit-reversed */ , forstep( p=p2, if(t, logint(t, 2)+1, 0), -1 , listput( ~c, bitor(t, 1<<p) ); ); ); b= c= Vec(c); /* b gets used in next round */ for( p=1, #c /* transform c into the next A370484-chunk */ , my( t= c[p], p2= logint(!t+t, 2), r= 0 ); for( i=0, p2 , if( bittest(t, i), r= r*3 + 2^i ); ); c[p]= r; ); a[p3+2]= c; ); a; } /* * Iterative A370935-data generator, in a chunk per A100982-order. * N is the maximum order, which is equivalent to the count of 1-bits. */ A370935_iter(N) = { my( a=Vec([[2]], N+1), b=[0] ); for( p3=0, N-1 , my( p2=logint(3^p3, 2), c=List() ); foreach( b, t /* generate a A370354-chunk, but bit-reversed */ , forstep( p=p2, if(t, logint(t, 2)+1, 0), -1 , listput( ~c, bitor(t, 1<<p) ); ); ); b= c= Vec(c); /* b gets used in next round */ my( t3=3^(p3+1), t2= 2^(logint(t3, 2)+1) ); for( p=1, #c /* transform c into the next A370935-chunk */ , my( t= c[p], p2= logint(!t+t, 2), r= 0 ); for( i=0, p2 , if( bittest(t, i), r= r*3 + 2^i ); ); c[p]= -r / t3 % t2; ); a[p3+2]= c; ); a; }