A100982 -id:A100982 - cp's OEIS frontend

A174795 Number of admissible sequences of order j; related to 5x+1 problem.

1, 2, 5, 14, 56, 202, 715, 3244, 12945, 49742, 238048, 996158, 3991995, 19676358, 84649176, 347993910, 1747681160, 7656026268, 32018897274, 162900330572, 722787262419, 3060338457400, 15718332812096, 70407433197686

Offset: 1

T.M.M. Laarhoven (t.laarhoven(AT)gmail.com), Mar 29 2010

nonn

			The unique admissible sequence of order 1 is 5/2, 1/2, 1/2.
The two admissible sequences of order 2 are 5/2, 5/2, 1/2, 1/2, 1/2 and 5/2, 1/2, 5/2, 1/2, 1/2.

Similar to A100982, but for the 5x+1 problem.

h[n_] := Module[{L = {{1}}}, For[i = 1, i <= n, i++, K = {}; S = 0; j = 1; While[5^i >= 2^(i + j - 1), If[5^(i - 1) >= 2^(i + j - 2), S = S + L[[i, j]]]; AppendTo[K, S]; j = j + 1]; AppendTo[L, K]; ]; Return[Map[Last, Drop[L, 1]]]]

n=20; a=vector(n); log52=log(5)/log(2);
{a[1]=1; for ( k=1, n-1, a[k+1]=sum( m=1,k,(-1)^(m-1)*binomial( floor( (k-m+1)*log52)+m-1,m)*a[k-m+1] );print1(a[k], ", ") );} \\ Vladimir M. Zarubin, Sep 25 2015

A sequence s(k), where k=1, 2, ..., n, is *admissible* if it satisfies s(k)=5/2 exactly j times, s(k)=1/2 exactly n-j times, s(1)*s(2)*...*s(n) < 1 but s(1)*s(2)*...*s(m) > 1 for all 1 < m < n.

a(1)=1 and a(k+1) = Sum_{m=1..k}(-1)^(m-1)*binomial(floor((k-m+1)*(log(5)/log(2)))+m-1, m)*a(k-m+1) for k >= 1. - Vladimir M. Zarubin, Sep 25 2015

A368514 Irregular triangle T(n,k) read by rows: similar to A009766 but length of rows grows like log(3)/log(2).

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 2, 0, 1, 3, 3, 1, 4, 7, 0, 1, 5, 12, 12, 0, 1, 6, 18, 30, 30, 1, 7, 25, 55, 85, 0, 1, 8, 33, 88, 173, 173, 1, 9, 42, 130, 303, 476, 0, 1, 10, 52, 182, 485, 961, 961, 0, 1, 11, 63, 245, 730, 1691, 2652, 2652, 1, 12, 75, 320, 1050, 2741, 5393, 8045, 0

Offset: 1

Ruud H.G. van Tol, Dec 28 2023

			Triangle T(n,k) begins:
 n|k:1|  2|  3|  4|  5|  6|  7|  8|...
--+---+---+---+---+---+---+---+---+---
 1|  1
 2|  1   0
 3|  1   1
 4|  1   2   0
 5|  1   3   3
 6|  1   4   7   0
 7|  1   5  12  12   0
 8|  1   6  18  30  30
 9|  1   7  25  55  85   0
10|  1   8  33  88 173 173
11|  1   9  42 130 303 476   0
12|  1  10  52 182 485 961 961   0
...

Ruud H.G. van Tol, Table of n, a(n) for n = 1..11858 (200 rows).
Ruud H.G. van Tol, Sequence on a lattice

Cf. A009766 (Catalan's triangle), A098294 (row lengths), A100982 (row sums).

Cf. A055998, A111396.

row(n) = my(v=Vec([1], logint(3^n, 2)+1-n), c=1); for(i=2, n, for(j=2, c, v[j]+=v[j-1]); c=logint(3^i,2)+1-i); v

rows(n) = my(v=vector(n, i, Vec([1], logint(3^i,2)+1-i))); for(i=3, n, for(j=2, #v[i-1], v[i][j]=v[i][j-1]+v[i-1][j])); v

Row length L(n) = A098294(n) = floor(n*log(3)/log(2)) + 1 - n.
T(n,1) = 1.
T(n+1,k) = T(n+1,k-1) + T(n,k) for 1 < k <= L(n).
T(n+1,L(n+1)) = 0 if L(n+1) > L(n).
T(n+1,2) = n-1.
T(n+3,3) = A055998(n-1) = (n-1)*(n+4)/2.
T(n+5,4) = A111396(n-1) = (n-1)*(n+6)*(n+7)/6.
T(n+1,k) = Sum_{j=1..k} T(n,j) for 1 <= k <= L(n).

Corrected by Ruud H.G. van Tol, Nov 29 2024

A182137 Size of the set of b for numbers of the form 2^n*x + b that cannot be the smallest element of a set giving a duration of infinite flight in the Collatz problem.

Original entry on oeis.org

1, 3, 6, 13, 28, 56, 115, 237, 474, 960, 1920, 3870, 7825, 15650, 31473, 63422, 126844, 254649, 509298, 1021248, 2050541, 4101082, 8219801, 16490635, 32981270, 66071490, 132455435, 264910870, 530485275, 1060970550, 2123841570, 4253619813, 8507239626, 17027951548, 34095896991, 68191793982, 136471574881, 272943149762, 546144278026, 1093108792776, 2186217585552

Offset: 1

Jérôme STORTI, Apr 14 2012

nonn

In the Collatz Problem A014682, it is possible to apply the algorithm to first degree polynomials like 2^n*x+b, where n is an integer and 0 <= b < 2^n. The iteration terminates by two cases:
1) a*x+b where a < 2^n: the polynomial is "minimized"
2) a*x+b where a is odd and a > 2^n, parity cannot be found. The polynomial cannot be minimized.
The sequence counts how many first degree polynomials end like first case for each n > 0.
The interest of this sequence is that every number that can be described by a minimized polynomial cannot be the smallest element of a set of value of T(n) = infinity.

			Example with 4x+b (0 <= b < 4):
4x is even, thus gives 2x, 2 < 4 (first case).
4x+1, is odd thus 3(4x+1)+1 = 12x+4 is even, thus (12x+4)/2/2=3x+1 3 < 4, first case.
4x+2 is even, (4x+2)/2=2x+1, 2 < 4, first case.
4x+3 with same way gives 9x+8. 9 is odd and 9 > 4, second case.
That explains why the second (n=2) term in sequence is 3.

Cf. A020914, A074473, A076227, A100982, A186109, A243115.

a[n_] := Module[{b, p0, p1, minimized = 0}, For[b = 1, b <= 2^n, b++, {p0, p1} = {b, 2^n}; While[Mod[p1, 2] == 0 && p1 >= 2^n, {p0, p1} = If[Mod[p0, 2] == 0, {p0/2, p1/2}, {3*p0+1, 3*p1}]; If[p1<2^n, minimized += 1]]]; minimized]; Table[Print[an = a[n]]; an, {n, 1, 40}] (* Jean-François Alcover, Feb 12 2014, translated from D. S. McNeil's Sage code *)

upto(P=18)= my(r=Vec([1, 1], P)); forstep(x=3,2^P,4, my(s=x, p=0); until(s<=x, s= if(s%2, 3*s+1, s)/2; if(p++ > P, next(2))); if((2^p>x), r[p]++)); for(i=2, #r, r[i]+= 2*r[i-1]); print(r); \\ Ruud H.G. van Tol, Mar 13 2023

def A182137(n):
    minimized = 0
    for b in range(2**n):
        p = [b, 2**n]
        while p[1] % 2 == 0 and p[1] >= 2**n:
            p[0],p[1] = [p[0]/2, p[1]/2] if p[0] % 2 == 0 else [3*p[0]+1, 3*p[1]]
        if p[1] < 2**n: minimized += 1
    return minimized # D. S. McNeil, Apr 14 2012

a(n) = 2^n - A076227(n) for n >= 2. - Ruud H.G. van Tol, Mar 13 2023

For n not in A020914, a(n) = 2*a(n-1). - Ruud H.G. van Tol, Apr 12 2023

More terms from D. S. McNeil, Apr 14 2012
a(31) from Jérôme STORTI, Apr 22 2012
a(32)-a(38) from Jérôme STORTI, Jul 21 2012
a(39) from Jérôme STORTI, Jul 26 2012
a(40) from Jérôme STORTI, Feb 08 2014
a(37) and a(39) corrected by Jérôme STORTI, Dec 29 2021

A293308 Number of permutations of zero-one words with A056576(n)-n zeros and n-1 ones.

Original entry on oeis.org

1, 2, 3, 10, 15, 56, 210, 330, 1287, 2002, 8008, 31824, 50388, 203490, 319770, 1307504, 2042975, 8436285, 34597290, 54627300, 225792840, 354817320, 1476337800, 6107086800, 9669554100, 40225345056, 63432274896, 265182149218, 416714805914, 1749695026860

Offset: 1

Frank Ellermann, Oct 05 2017

nonn

			a(4) = 5! / ( 2! * 3! ) = 5*4/2 = 10.
From _Mike Winkler_, Oct 30 2017: (Start)
The next table shows the output using the PARI function NextPermutation(a), (cf. PROG)
[0, 0, 1, 1, 1] 1
[0, 1, 0, 1, 1] 2
[0, 1, 1, 0, 1] 3
[0, 1, 1, 1, 0] 4
[1, 0, 0, 1, 1] 5
[1, 0, 1, 0, 1] 6
[1, 0, 1, 1, 0] 7
[1, 1, 0, 0, 1] 8
[1, 1, 0, 1, 0] 9
[1, 1, 1, 0, 0] 10
(End)

Michael De Vlieger, Table of n, a(n) for n = 1..2211
Mike Winkler, The algorithmic structure of the finite stopping time behavior of the 3x + 1 function, arXiv:1709.03385 [math.GM], Sep 2017. [see (17) on p. 9]

Cf. A056576, A100982.

Table[(# - 1)!/((# - n)!*(n - 1)!) &@ Floor[n Log[2, 3]], {n, 30}] (* Michael De Vlieger, Oct 06 2017 *)

/* method used in the linked paper arXiv:1709.03385 */
NextPermutation(a) = {i=#a-1; while(!(i<1 || a[i]a[i]), k--); t=a[k]; a[k]=a[i]; a[i]=t; for(k=i+1, (#a+i)/2, t=a[k]; a[k]=a[#a+1+i-k]; a[#a+1+i-k]=t); return(a)}
  /* example for n = 4 */
  {j=1; a=[0, 0, 1, 1, 1]; until(a==0, print(a" "j); j++; a=NextPermutation(a))} \\ Mike Winkler, Oct 30 2017

a(n) = ( A056576(n) - 1 )! / ( ( A056576(n) - n )! * ( n - 1)! )

A174796 Number of admissible sequences of order j; related to 7x+1 problem.

Original entry on oeis.org

1, 2, 7, 30, 143, 728, 3148, 15986, 86009, 478907, 2731365, 13131703, 72135374, 412835191, 2416852480, 14369476066, 72067537808, 409636973141, 2412844770335, 14479410843183, 87964452906330, 451313038006432

Offset: 1

T.M.M. Laarhoven (t.laarhoven(AT)gmail.com), Mar 29 2010

nonn

			The unique admissible sequence of order 1 is 7/2, 1/2, 1/2.
The two admissible sequences of order 2 are 7/2, 7/2, 1/2, 1/2, 1/2, 1/2 and 7/2, 1/2, 7/2, 1/2, 1/2, 1/2.

Similar to A100982 and A174795, but for the 7x+1 problem.

h[n_] := Module[{L = {{1}}}, For[i = 1, i <= n, i++, K = {}; S = 0; j = 1; While[7^i >= 2^(i + j - 1), If[7^(i - 1) >= 2^(i + j - 2), S = S + L[[i, j]]]; AppendTo[K, S]; j = j + 1]; AppendTo[L, K]; ]; Return[Map[Last, Drop[L, 1]]]]

n=20; a=vector(n); log72=log(7)/log(2);
{a[1]=1; for ( k=1, n-1, a[k+1]=sum( m=1,k,(-1)^(m-1)*binomial( floor( (k-m+1)*log72)+m-1,m)*a[k-m+1] ); print1(a[k], ", ") );} \\ Vladimir M. Zarubin, Sep 25 2015

A sequence s(k), where k=1, 2, ..., n, is *admissible* if it satisfies s(k)=7/2 exactly j times, s(k)=1/2 exactly n-j times, s(1)*s(2)*...*s(n) < 1 but s(1)*s(2)*...*s(m) > 1 for all 1 < m < n.

a(1) = 1 and a(k) = Sum_{m=1..k-1} (-1)^(m-1)*binomial(floor((k-m)*(log(7)/log(2)))+m-1, m)*a(k-m) for k >= 2. - Vladimir M. Zarubin, Sep 25 2015

A260591 a(n) is the number of odd numbers k < 2^n such that A260590(k) = n.

Original entry on oeis.org

0, 1, 0, 1, 2, 0, 3, 7, 0, 12, 0, 30, 85, 0, 173, 476, 0, 961, 0, 2652, 8045, 0, 17637, 51033, 0, 108950, 312455, 0, 663535, 0, 1900470, 5936673, 0, 13472296, 39993895, 0, 87986917, 0, 257978502, 820236724, 0, 1899474678, 5723030586, 0, 12809477536, 38036848410, 0, 84141805077, 0, 248369601964

Offset: 1

Joseph K. Horn, O. Praem, and Robert G. Wilson v, Jul 29 2015

nonn

a(n) is either 0 or about c^(n-1) with c = log(3)/log(2).
Nonzero values give A100982. - Ruud H.G. van Tol, Nov 25 2021
A close variant of this sequence, that starts at offset 0, but with a(0)=0 and a(1)=1, maps it to the count of dropping patterns of 2^n+c(2^n), with the c(2^n) as mentioned with A177789. The positions of the zeros of that variant sequence might be a close variant of A054414, again with a(0)=0 (not properly checked yet). - Ruud H.G. van Tol, Nov 28 2021
It appears that the proportion of zeros is 1-log(2)/log(3) = 36.907...%. - Jesse Randall, Oct 10 2024

			a(1) = 0 since there exists no odd number whose msa is 1;
a(2) = 1 since there is only one odd number, 5 with k=2 2k+1, with k less than 2^2 whose msa is 2;
a(3) = 0 since there exists no odd number whose msa is 3;
a(4) = 1 since there is only one number, 1, less than 2^(4+1) whose msa is 4;
a(5) = 2 since there are two numbers, 11 & 23, less than 2^(4+1) whose msa is 4; etc.

Cf. A260590, A054414, A100982, A186009, A186008, A177789, A346640.

msa[n_] := If[ OddQ@ n, (3n + 1)/2, n/2]; f[n_] := Block[{k = 2n + 1}, Length@ NestWhileList[ msa@# &, k, # >= k &] - 1]; g[n_] := Length@ Select[ Range[ 2^(n - 1)], f@# == n &]; Array[ g, 20]

a(31) onwards from Jesse Randall, Sep 09 2024

cp's OEIS Frontend

A174795 Number of admissible sequences of order j; related to 5x+1 problem.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A368514 Irregular triangle T(n,k) read by rows: similar to A009766 but length of rows grows like log(3)/log(2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

PARI

Formula

Extensions

A182137 Size of the set of b for numbers of the form 2^n*x + b that cannot be the smallest element of a set giving a duration of infinite flight in the Collatz problem.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A293308 Number of permutations of zero-one words with A056576(n)-n zeros and n-1 ones.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A174796 Number of admissible sequences of order j; related to 7x+1 problem.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

A260591 a(n) is the number of odd numbers k < 2^n such that A260590(k) = n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions