Mitch Harris - cp's OEIS frontend

A179118 Number of Collatz steps to reach 1 starting with 2^n + 1.

1, 7, 5, 19, 12, 26, 27, 121, 122, 35, 36, 156, 113, 52, 53, 98, 99, 100, 101, 102, 72, 166, 167, 168, 169, 170, 171, 247, 173, 187, 188, 251, 252, 178, 179, 317, 243, 195, 196, 153, 154, 155, 156, 400, 326, 495, 496, 161, 162, 331, 332, 408, 471, 410, 411, 337, 338, 339, 340, 553

Offset: 0

Mitch Harris, Jan 04 2011

There are many long runs of consecutive terms that increase by 1 (see second conjecture in A277109). For n < 40000, the longest run has 1030 terms starting from a(33237) = 244868 and ending with a(34266) = 245897. - Dmitry Kamenetsky, Sep 30 2016

			a(1)=7 because the trajectory of 2^1+1=3 is (3,10,5,16,8,4,2,1).

Dmitry Kamenetsky, Table of n, a(n) for n = 0..9999 (terms n = 1...1000 from Mitch Harris)
MathOverflow, Introduced on Mathoverflow by Henrik Rüping

Cf. A000051, A006577, A070976, A074472, A075486, A193688 (starting with 2^n-1), , A179118, A277109.

CollatzNext[n_] := If[Mod[n, 2] == 0, n/2, 3 n + 1]; CollatzPath[n_] := CollatzPath[n] = Module[{k = n, l = {}}, While[k != 1, k = CollatzNext[k]; l = Append[l, k]]; l]; Collatz[n_] := Length[CollatzPath[n]]; Table[Collatz[2^n+1],{n,1,50}]
f[n_] := Length@ NestWhileList[If[OddQ@ #, 3 # + 1, #/2] &, 2^n + 1, # > 1 &] - 1; Array[f, 60] (* Robert G. Wilson v, Jan 05 2011 *)
Array[-1 + Length@ NestWhileList[If[EvenQ@ #, #/2, 3 # + 1] &, 2^# + 1, # > 1 &] &, 60, 0] (* Michael De Vlieger, Nov 25 2018 *)

nbsteps(n)= s=n; c=0; while(s>1, s=if(s%2, 3*s+1, s/2); c++); c;
a(n) = nbsteps(2^n+1); \\ Michel Marcus, Oct 28 2018

def steps(a):
  if a==1:     return 0
  elif a%2==0: return 1+steps(a//2)
  else:        return 1+steps(a*3+1)
for n in range(60):
  print(n, steps((1<

a(n) = A006577(2^n+1) = A006577(A000051(n)).

a(n) = A075486(n) - 1. - T. D. Noe, Jan 17 2013

a(0)=1 prepended by Alois P. Heinz, Dec 12 2018

A117152 Sum of product of Fibonacci and triangular numbers.

Original entry on oeis.org

0, 0, 1, 7, 25, 75, 195, 468, 1056, 2280, 4755, 9650, 19154, 37328, 71635, 135685, 254125, 471317, 866669, 1581620, 2866970, 5165630, 9256871, 16507092, 29304660, 51812160, 91264885, 160207603, 280340161, 489117135, 851054535

Offset: 0

Mitch Harris, Feb 28 2006

A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003

Cf. A086926, A014286.

Binomial[n, 2]Fibonacci[n + 2] - n Fibonacci[n + 3] + Fibonacci[n + 5] - 5

a(n) = sum(k=2, n, k*(k-1)*fibonacci(k)/2); \\ Michel Marcus, Feb 28 2019

a(n) = Sum_{k=2..n} C(k,2)*F(k), where F(n) = A000045(n), the Fibonacci numbers and C(n, 2) = A000217(n-1), the triangular numbers, n(n-1)/2.
a(n) = C(n,2) F(n+2) - n F(n+3) + F(n+5) - 5.
G.f.: x^2(1 + 3x + x^3)/((1 - x)(1 - x - x^2)^3).
a(n)-a(n-1) = A086926(n). - R. J. Mathar, May 16 2025

A114716 Number of linear extensions of a 3 X 2 X n lattice.

Original entry on oeis.org

1, 5, 2452, 4877756, 20071150430, 129586764260850, 1138355914222027660, 12513844842339741519760, 163186564770917385358723138, 2434438822161210367337209525489, 40488679486377745566571570522228550, 736610570835499716578578298705683198672

Offset: 0

Mitch Harris, Dec 27 2005; corrected May 25 2006

Stanley, R., Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Alois P. Heinz, Table of n, a(n) for n = 0..45

Cf. A114717.

b:= proc(u, v, w, x, y, z) option remember;
      `if`({u, v, w, x, y, z}={0}, 1,
      `if`(u>v and u>x, b(u-1, v, w, x, y, z), 0)+
      `if`(v>w and v>y, b(u, v-1, w, x, y, z), 0)+
      `if`(w>z, b(u, v, w-1, x, y, z), 0)+
      `if`(x>y, b(u, v, w, x-1, y, z), 0)+
      `if`(y>z, b(u, v, w, x, y-1, z), 0)+
      `if`(z>0, b(u, v, w, x, y, z-1), 0))
    end:
a:= n-> b(n$6):
seq(a(n), n=0..12);  # Alois P. Heinz, Apr 26 2012

b[u_, v_, w_, x_, y_, z_] := b[u, v, w, x, y, z] =
If[Union[{u, v, w, x, y, z}] == {0}, 1,
If[u>v && u>x, b[u-1, v, w, x, y, z], 0] +
If[v>w && v>y, b[u, v-1, w, x, y, z], 0] +
If[w>z, b[u, v, w-1, x, y, z], 0] +
If[x>y, b[u, v, w, x-1, y, z], 0] +
If[y>z, b[u, v, w, x, y-1, z], 0] +
If[z>0, b[u, v, w, x, y, z-1], 0]];
a[n_] := b[n, n, n, n, n, n]; Table[a[n], {n, 0, 12}] (* Jean-François Alcover, May 29 2015, after Alois P. Heinz *)

a(6)-a(11) from Alois P. Heinz, Apr 26 2012

A114714 Number of linear extensions of a 2 X 2 X n lattice.

Original entry on oeis.org

1, 2, 48, 2452, 183958, 17454844, 1941406508, 242201554680, 32959299267334, 4801233680739724, 738810565910888784, 118929992674840615128, 19880920716640427983476, 3431624482227380273056728, 608880419873586515669564728, 110654016191338341346670548240

Offset: 0

Mitch Harris, Dec 27 2005

The additional terms were found using dynamic programming to count the maximal chains in the distributive lattice of order-preserving functions from the chain of length n to J(P), where J is the lattice of downsets of the poset P = 2x2. - Nick Krempel, Jul 08 2010

Stanley, R., Enumerative Combinatorics, Vol. 2, Prop. 7.10.3 and Vol. 1, Sec 3.5, Chains in Distributive Lattices.

Alois P. Heinz, Table of n, a(n) for n = 0..180 (first 41 terms from Nick Krempel)

Cf. A114717.

b:= proc(x, y, u, w) option remember;
      `if`(x=0 and y=0 and u=0 and w=0, 1, `if`(x>y and x>u,
       b(x-1, y, u, w), 0)+ `if`(y>w, b(x, y-1, u, w), 0)+
      `if`(u>w, b(x, y, u-1, w), 0)+ `if`(w>0, b(x, y, u, w-1), 0))
    end:
a:= n-> b(n$4):
seq(a(n), n=0..20);  # Alois P. Heinz, Apr 27 2012

b[x_, y_, u_, w_] := b[x, y, u, w] = If[x == 0 && y == 0 && u == 0 && w == 0, 1, If[x>y && x>u, b[x-1, y, u, w], 0] + If[y>w, b[x, y-1, u, w], 0] + If[u>w, b[x, y, u-1, w], 0] + If[w>0, b[x, y, u, w-1], 0]]; a[n_] := b[n, n, n, n]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 29 2015, after Alois P. Heinz *)

More terms from Nick Krempel, Jul 08 2010

A114715 Number A(n,m) of linear extensions of a 2 X n X m lattice; square array A(n,m), n>=1, m>=1, read by antidiagonals.

Original entry on oeis.org

1, 2, 2, 5, 48, 5, 14, 2452, 2452, 14, 42, 183958, 4877756, 183958, 42, 132, 17454844, 20071150430, 20071150430, 17454844, 132, 429, 1941406508, 129586764260850, 6708527580006468, 129586764260850, 1941406508, 429

Offset: 1

Mitch Harris, Dec 27 2005

			Square array A(n,m) begins:
   1,      2,           5,               14, ...
   2,     48,        2452,           183958, ...
   5,   2452,     4877756,      20071150430, ...
  14, 183958, 20071150430, 6708527580006468, ...

Stanley, R., Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Alois P. Heinz, Antidiagonals n = 1..12, flattened

Cf. A000108, A114714, A114716, A114717.

Main diagonal gives A370257.

b := proc(l) option remember; local n; n:= nops(l);
      `if`({seq(l[i][], i=1..n)}={0}, 1, add(`if`(l[i][1]>l[i][2] and
       l[i][1]>l[i+1][1], b(subsop(i=[l[i][1]-1, l[i][2]], l)), 0),
       i=1..n-1)+ add(`if`(l[i][2]>l[i+1][2], b(subsop(i=[l[i][1],
       l[i][2]-1], l)), 0), i=1..n-1)+ `if`(l[n][1]>l[n][2],
       b(subsop(n=[l[n][1]-1, l[n][2]], l)), 0)+ `if`(l[n][2]>0,
       b(subsop(n=[l[n][1], l[n][2]-1], l)), 0))
     end:
A:= (n, m)-> `if`(m>=n, b([[m$2]$n]), b([[n$2]$m])):
seq(seq(A(n, d+1-n), n=1..d), d=1..8);  # Alois P. Heinz, Jun 29 2012

b[l_List] := b[l] = With[{n = Length[l]}, If[Union[Table[l[[i]], {i, 1, n}] // Flatten] == {0}, 1, Sum[If[l[[i, 1]] > l[[i, 2]] && l[[i, 1]] > l[[i+1, 1]], b[ReplacePart[l, i -> {l[[i, 1]]-1, l[[i, 2]]}]], 0], {i, 1, n-1}] + Sum[If[l[[i, 2]] > l[[i+1, 2]], b[ReplacePart[l, i -> {l[[i, 1]], l[[i, 2]]-1}]], 0], {i, 1, n-1}] + If[l[[n, 1]] > l[[n, 2]], b[ReplacePart[l, n -> {l[[n, 1]]-1, l[[n, 2]]} ]], 0] + If[l[[n, 2]] > 0, b[ReplacePart[l, n -> {l[[n, 1]], l[[n, 2]]-1}]], 0]]] ; A[n_, m_] := If[m >= n, b[Array[{m, m}&, n]], b[Array[{n, n}&, m]]]; Table[ Table[A[n, d+1-n], {n, 1, d}], {d, 1, 8}] // Flatten (* Jean-François Alcover, Mar 11 2015, after Alois P. Heinz *)

A(n,1) = A(1,n) = A000108(n).
A(n,2) = A(2,n) = A114714(n).
A(n,3) = A(3,n) = A114716(n).

Edited by Alois P. Heinz, Jun 29 2012

A114717 Number of linear extensions of the divisor lattice of n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 5, 1, 2, 2, 1, 1, 5, 1, 5, 2, 2, 1, 14, 1, 2, 1, 5, 1, 48, 1, 1, 2, 2, 2, 42, 1, 2, 2, 14, 1, 48, 1, 5, 5, 2, 1, 42, 1, 5, 2, 5, 1, 14, 2, 14, 2, 2, 1, 2452, 1, 2, 5, 1, 2, 48, 1, 5, 2, 48, 1, 462, 1, 2, 5, 5, 2, 48, 1, 42, 1, 2, 1, 2452, 2, 2, 2, 14, 1, 2452, 2

Offset: 1

Mitch Harris and Antti Karttunen, Dec 27 2005

nonn

Notice that only the powers of the primes determine a(n), so a(12) = a(75) = 5.
For prime powers, the lattice is a chain, so there is 1 linear extension.
a(p^1*q^n) = A000108(n+1), the Catalan numbers.
Alternatively, the number of ways to arrange the divisors of n in such a way that no divisor has any of its own divisors following it. E.g., for 12, the following five arrangements are possible: 1,2,3,4,6,12; 1,2,3,6,4,12; 1,2,4,3,6,12; 1,3,2,4,6,12 and 1,3,2,6,4,12. But 1,2,6,4,3,12 is not possible because 3 divides 6 but follows it. Thus a(12)=5. - Antti Karttunen, Jan 11 2006
For n = p1^r1 * p2^r2, the lattice is a grid (r1+1)*(r2+1), whose linear extensions are counted by ((r1+1)*(r2+1))!/Product_{k=0..r2} (r1+1+k)!/k!. Cf. A060854.

R. Stanley, Enumerative Combinatorics, Vol. 2, Proposition 7.10.3 and Vol. 1, Sec 3.5 Chains in Distributive Lattices.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Graham Brightwell and Peter Winkler, Counting linear extensions, Order 8 (1991), no. 3, 225-242.
Gary Pruesse and Frank Ruskey, Generating linear extensions fast, SIAM J. Comput. 23 (1994), no. 2, 373-386.
Index entries for sequences computed from exponents in factorization of n

Cf. A060854, A114714, A114715, A114716, A119842.

with(numtheory):
b:= proc(s) option remember;
      `if`(nops(s)<2, 1, add(`if`(nops(select(y->
       irem(y, x)=0, s))=1, b(s minus {x}), 0), x=s))
    end:
a:= proc(n) local l, m;
      l:= sort(ifactors(n)[2], (x, y)-> x[2]>y[2]);
      m:= mul(ithprime(i)^l[i][2], i=1..nops(l));
      b(divisors(m) minus {1, m})
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 29 2012

b[s_List] := b[s] = If[Length[s]<2, 1, Sum[If[Length[Select[s, Mod[#, x] == 0 &]] == 1, b[Complement[s, {x}]], 0], {x, s}]]; a[n_] := Module[{l, m}, l = Sort[ FactorInteger[n], #1[[2]] > #2[[2]] &]; m = Product[Prime[i]^l[[i]][[2]], {i, 1, Length[l]}]; b[Divisors[m] // Rest // Most]]; Table[a[n], {n, 1, 100}] (* Jean-François Alcover, May 28 2015, after Alois P. Heinz *)

A107661 Array read by antidiagonals: T(n,m) = Sum m^max(k,n-k),k=0..n.

Original entry on oeis.org

1, 1, 2, 1, 4, 3, 1, 6, 10, 4, 1, 8, 21, 24, 5, 1, 10, 36, 72, 52, 6, 1, 12, 55, 160, 225, 112, 7, 1, 14, 78, 300, 656, 702, 232, 8, 1, 16, 105, 504, 1525, 2688, 2133, 480, 9, 1, 18, 136, 784, 3060, 7750, 10816, 6480, 976, 10, 1, 20, 171, 1152, 5537, 18576, 38875

Offset: 0

Mitch Harris

			The array starts in row n=0 and column m=1 as:
    1,    1,    1,    1,    1,    1,...
    2,    4,    6,    8,   10,   12,...
    3,   10,   21,   36,   55,   78,...
    4,   24,   72,  160,  300,  504,...
    5,   52,  225,  656, 1525, 3060,...
    6,  112,  702, 2688, 7750,18576,...
    7,  232, 2133,10816,38875,111672,...
    8,  480, 6480,43520,195000,671328,...

Cf. A107659, A107660, A014105 (3rd row), A181617 (4th row)

a(2n) = m^n(2(m^(n+1)-1)/(m-1)-1), a(2n+1) = 2m^(n+1)(m^(n+1)-1)/(m-1)

T(5,m) = m^2*(2*m^2+2*m+1). - R. J. Mathar, Aug 16 2013

A107660 Sum 3^max(k,n-k),k=0..n.

Original entry on oeis.org

1, 6, 21, 72, 225, 702, 2133, 6480, 19521, 58806, 176661, 530712, 1592865, 4780782, 14344533, 43040160, 129127041, 387400806, 1162222101, 3486725352, 10460235105, 31380882462, 94142824533, 282429005040, 847287546561

Offset: 0

Mitch Harris

Third column of A107661.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Cf. A107659, A107661.

CoefficientList[Series[(1 + 3 x) / ((1 - 3 x) (1 - 3 x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 17 2013 *)

G.f.: (1+3*x)/((1-3*x)*(1-3*x^2)).
a(2n) = 3^(2n+1) - 2*3^n; a(2n+1) = 9^(n+1) - 3^(n+1).
a(n) = A167993(n+2) + 3*A167993(n+1). - R. J. Mathar, Aug 16 2013

A107659 a(n) = Sum_{k=0..n} 2^max(k, n-k).

Original entry on oeis.org

1, 4, 10, 24, 52, 112, 232, 480, 976, 1984, 4000, 8064, 16192, 32512, 65152, 130560, 261376, 523264, 1047040, 2095104, 4191232, 8384512, 16771072, 33546240, 67096576, 134201344, 268410880, 536838144, 1073692672, 2147418112

Offset: 0

Mitch Harris

Define an infinite array by m(n,k) = 2^n-n+k for n>=k>=0 (in the lower left triangle) and by m(n,k) = 2^k+k-n for k>=n>=0 (in the upper right triangle). The antidiagonal sums of this array are a(n) = sum_{k=0..n} m(n-k,k). - J. M. Bergot, Aug 16 2013

			G.f. = 1 + 4*x + 10*x^2 + 24*x^3 + 52*x^4 + 112*x^5 + 232*x^6 + 480*x^7 + ... - _Michael Somos_, Jun 24 2018

Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Cf. A027383, A052955.

Table[Sum[2^Max[k,n-k],{k,0,n}],{n,0,30}] (* or *) LinearRecurrence[ {2,2,-4},{1,4,10},30] (* Harvey P. Dale, Nov 10 2013 *)
a[ n_] := 2^(n + 2) - (2 + Mod[n + 1, 2]) 2^Quotient[n + 1, 2]; (* Michael Somos, Jun 24 2018 *)

{a(n) = 2^(n+2) - (2 + (n+1)%2) * 2^((n+1)\2)}; /* Michael Somos, Jun 24 2018 */

a(2n) = 2^n(2^(n+2)-3), a(2n+1) = 2^n(2^(n+3)-4).
G.f.: (1+2*x)/[(1-2*x)*(1-2*x^2)].
a(n) = A122746(n) +2*A122746(n-1). - R. J. Mathar, Aug 16 2013
a(0)=1, a(1)=4, a(2)=10, a(n)=2*a(n-1)+2*a(n-2)-4*a(n-3). - Harvey P. Dale, Nov 10 2013
a(n) = 2^(n+2) - (2 + mod(n+1, 2)) * 2^floor((n+1)/2). - Michael Somos, Jun 24 2018
a(n) = - (2^(n+2)) * A052955(-n-3) for all n in Z. - Michael Somos, Jun 24 2018

A109011 a(n) = gcd(n,8).

Original entry on oeis.org

8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4

Offset: 0

Mitch Harris

Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,1).

Cf. A010877, A109004.

a[n_]:= GCD[n,8]; Array[a, 100, 0] (* Stefano Spezia, Nov 19 2018 *)

a(n) = gcd(n, 8) \\ David A. Corneth, Nov 19 2018

a(n) = 1 + [2|n] + 2*[4|n] + 4*[8|n], where [x|y] = 1 when x divides y, 0 otherwise.
a(n) = a(n-8).
Multiplicative with a(p^e) = gcd(p^e, 8). - David W. Wilson, Jun 12 2005
G.f.: ( -8 - x - 2*x^2 - x^3 - 4*x^4 - x^5 - 2*x^6 - x^7 ) / ( (x-1)*(1+x)*(x^2+1)*(x^4+1) ). - R. J. Mathar, Apr 04 2011
Dirichlet g.f.: zeta(s)*(1 + 1/2^s + 2/4^s + 4/8^s). - R. J. Mathar, Apr 04 2011
a(n) = 2^(-(101*m^7 - 2464*m^6 + 23786*m^ 5 -115360*m^4 + 293909*m^3 - 371056*m^2 + 186204*m - 15120)/5040) where m = (n mod 8). - Luce ETIENNE, Nov 18 2018

cp's OEIS Frontend

User: Mitch Harris

A179118 Number of Collatz steps to reach 1 starting with 2^n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A117152 Sum of product of Fibonacci and triangular numbers.

Views

Author

Keywords

References

Crossrefs

Programs

Mathematica

PARI

Formula

A114716 Number of linear extensions of a 3 X 2 X n lattice.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A114714 Number of linear extensions of a 2 X 2 X n lattice.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A114715 Number A(n,m) of linear extensions of a 2 X n X m lattice; square array A(n,m), n>=1, m>=1, read by antidiagonals.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A114717 Number of linear extensions of the divisor lattice of n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

A107661 Array read by antidiagonals: T(n,m) = Sum m^max(k,n-k),k=0..n.

Views

Author

Keywords

Examples

Crossrefs

Formula