A279683 -id:A279683 - cp's OEIS frontend

A330718 a(n) = numerator(Sum_{k=1..n} (2^k-2)/k).

0, 1, 3, 13, 25, 137, 245, 871, 517, 4629, 8349, 45517, 83317, 1074679, 1992127, 7424789, 13901189, 78403447, 147940327, 280060651, 531718651, 11133725681, 21243819521, 40621501691, 15565330735, 388375065019, 248882304985, 479199924517, 923951191477, 2973006070891

Offset: 1

Amiram Eldar and Thomas Ordowski, Dec 28 2019

If p > 3 is prime, then p^2 | a(p).
Note the similarity to Wolstenholme's theorem.
Conjecture: for n > 3, if n^2 | a(n), then n is prime.
Are there the weak pseudoprimes m such that m | a(m)?
Primes p such that p^3 | a(p) are probably A088164.
If p is an odd prime, then a(p+1) == A330719(p+1) (mod p).
If p > 3 is a prime, then p^2 | numerator(Sum_{k=1..p+1} F(k)), where F(n) = Sum_{k=1..n} (2^(k-1)-1)/k. Cf. A027612 (a weaker divisibility).

			Numerators of 0, 1, 3, 13/2, 25/2, 137/6, 245/6, ...

G. C. Greubel, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Wolstenholme's Theorem

Cf. A000265, A001008, A007663, A088164, A159353, A225101, A279683, A290347, A330719.

[Numerator( &+[(2^k -2)/k: k in [1..n]] ): n in [1..30]]; // G. C. Greubel, Dec 28 2019

seq(numer(add((2^k -2)/k, k = 1..n)), n = 1..30); # G. C. Greubel, Dec 28 2019

Numerator @ Accumulate @ Array[(2^# - 2)/# &, 30]
Table[Numerator[Simplify[-(2^(n+1)*LerchPhi[2,1,n+1] +Pi*I +2*HarmonicNumber[n])]], {n,30}] (* G. C. Greubel, Dec 28 2019 *)

a(n) = numerator(sum(k=1, n, (2^k-2)/k)); \\ Michel Marcus, Dec 28 2019

[numerator( sum((2^k -2)/k for k in (1..n)) ) for n in (1..30)] # G. C. Greubel, Dec 28 2019

a(n) = numerator(Sum_{k=1..n} (2^(k-1)-1)/k).
a(n+1) = numerator(a(n)/A330719(n) + A225101(n+1)/(2*A159353(n+1))).
a(p) = a(p-1) + A007663(n)*A330719(p-1) for p = prime(n) > 2.
a(n) = numerator(-(2^(n+1)*LerchPhi(2,1,n+1) + Pi*i + 2*HarmonicNumber(n))). - G. C. Greubel, Dec 28 2019
a(n) = numerator(A279683(n)/n!) for n > 0. - Amiram Eldar and Thomas Ordowski, Jan 15 2020
For n > 1, a(n) = A000265(A290347(n)). - Thomas Ordowski, Mar 29 2025

A330719 a(n) = denominator(Sum_{k=1..n} (2^(k-1) - 1)/k).

Original entry on oeis.org

1, 2, 2, 4, 4, 12, 12, 24, 8, 40, 40, 120, 120, 840, 840, 1680, 1680, 5040, 5040, 5040, 5040, 55440, 55440, 55440, 11088, 144144, 48048, 48048, 48048, 80080, 80080, 160160, 160160, 2722720, 544544, 4900896, 4900896, 93117024, 93117024, 465585120, 465585120, 465585120

Offset: 1

Amiram Eldar and Thomas Ordowski, Dec 28 2019

Conjecture: if p is an odd prime, then p | A330718(p+1) - a(p+1).
Below 10^6 there is only one pseudoprime, namely 25. Are there others?
Primes p such that p^2 | A330718(p+1) - a(p+1) are 3, 5, 45827, ...

			Denominators of 0, 1/2, 3/2, 13/4, 25/4, 137/12, 245/12, ...

Metin Sariyar, Table of n, a(n) for n = 1..500

Cf. A000265, A002805, A064169, A279683, A290348, A330718.

[Denominator( &+[(2^(k-1)-1)/k: k in [1..n]] ): n in [1..45]]; // G. C. Greubel, Dec 28 2019

seq(denom(add((2^(k-1)-1)/k, k = 1..n)), n = 1..45); # G. C. Greubel, Dec 28 2019

Denominator@Accumulate@Array[(2^(#-1) -1)/# &, 45]
Table[Denominator[-(2^n*LerchPhi[2, 1, n+1] +Pi*I/2 +HarmonicNumber[n])], {n, 45}] (* G. C. Greubel, Dec 28 2019 *)

a(n) = denominator(sum(k=1, n, (2^(k-1)-1)/k)); \\ Michel Marcus, Dec 28 2019

[denominator( sum((2^(k-1)-1)/k for k in (1..n)) ) for n in (1..45)] # G. C. Greubel, Dec 28 2019

a(n) = denominator(-(2^n*LerchPhi(2,1,n+1) + Pi*i/2 + HarmonicNumber(n))). - G. C. Greubel, Dec 28 2019
a(n) = denominator(A279683(n)/n!) for n > 0. - Amiram Eldar and Thomas Ordowski, Jan 15 2020
A000265(a(n)) = A290348(n). - Thomas Ordowski, Mar 29 2025

A212395 Number of move operations required to sort all permutations of [n] by insertion sort.

Original entry on oeis.org

0, 0, 3, 23, 164, 1252, 10512, 97344, 990432, 11010528, 132966720, 1734793920, 24330205440, 365150833920, 5840673108480, 99204809356800, 1783428104908800, 33833306484633600, 675513065777356800, 14160039606855475200, 310935875030323200000

Offset: 0

Alois P. Heinz, May 14 2012

nonn

a(n) is n! times the average number of move operations (A212396, A212397) required by an insertion sort of n (distinct) elements.

			a(0) = a(1) = 0 because 0 or 1 elements are already sorted.
a(2) = 3: [1,2] is sorted and [2,1] needs 3 moves.
a(3) = 23: [1,2,3]->(0), [1,3,2]->(3), [2,1,3]->(3), [2,3,1]->(4), [3,1,2]->(6), [3,2,1]->(7); sum of all moves gives 0+3+3+4+6+7 = 23.

Alois P. Heinz, Table of n, a(n) for n = 0..448
Wikipedia, Insertion sort
Index entries for sequences related to sorting

Cf. A001008, A002805, A159324, A212396, A212397, A279683.

a:= proc(n) option remember;
      `if`(n=0, 0, a(n-1)*n + (n-1)! * (n-1)*(n+4)/2)
    end:
seq(a(n), n=0..30);
# second Maple program:
a:= proc(n) option remember; `if`(n<3, [0$2, 3][n+1],
      ((2*n^3+3*n^2-13*n+4)*a(n-1) -(n+4)*
       (n-1)^3*a(n-2)) / ((n-2)*(3+n)))
    end:
seq(a(n), n=0..30);

a[n_] := n!*(n*(n+7)/4 - 2*HarmonicNumber[n]); Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 01 2017, from 2nd formula *)

a(n) = a(n-1)*n + (n-1)! * (n-1)*(n+4)/2 for n>0, a(0) = 0.
a(n) = n! * (n*(n+7)/4 - 2*H(n)) with n-th harmonic number H(n) = Sum_{k=1..n} 1/k = A001008(n)/A002805(n).
a(n) = ((2*n^3+3*n^2-13*n+4)*a(n-1)-(n+4)*(n-1)^3*a(n-2))/((n-2)*(3+n)) for n>2.

A280970 Number of comparisons required to sort all permutations of [n] by MTF sort.

Original entry on oeis.org

0, 0, 3, 25, 208, 1928, 20328, 244536, 3347328, 51858432, 902874240, 17523066240, 375931514880, 8842225904640, 226294152053760, 6258916573056000, 185978410684416000, 5906514709831680000, 199606607730561024000, 7150186413112651776000, 270578540735613960192000

Offset: 0

Alois P. Heinz, Jan 11 2017

nonn

MTF sort is an (inefficient) sorting algorithm: the first element that is smaller than its predecessor is moved to front repeatedly until the sequence is sorted. Comparisons of adjacent elements always begin at the front and are continued until the last or the next element to be moved is found.

Alois P. Heinz, Table of n, a(n) for n = 0..404
Project Euler, Problem 523: First Sort I
Wikipedia, Sorting algorithm
Index entries for sequences related to sorting

Cf. A279683.

a:= proc(n) option remember;
      `if`(n<2, 0, a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2))
    end:
seq(a(n), n=0..20);
# second Maple program:
a:= proc(n) option remember;
     `if`(n<7, [0$2, 3, 25, 208, 1928, 20328][n+1],
     ((4*n^2-23*n+2)*a(n-1)-(5*n^3-28*n^2-n+54)*a(n-2)
      +(2*n-4)*(n^3-2*n^2-24*n+52)*a(n-3)
      -(4*n-8)*(n-4)*(n-3)^2*a(n-4))/(n-6))
    end:
seq(a(n), n=0..20);

Flatten[{0, Simplify[Table[n!*(n*(n-5)/4 - Pi*I - 1 - 2^(1+n)*LerchPhi[2, 1, 1+n]) , {n, 1, 20}]]}] (* Vaclav Kotesovec, Jan 12 2017 *)

a(n) = a(n-1)*n + (n-1)! * (2^n+(n-3)*n/2) for n>1, a(0) = a(1) = 0.

a(n) ~ (n-1)! * 2^(n+1). - Vaclav Kotesovec, Jan 12 2017

cp's OEIS Frontend

A330718 a(n) = numerator(Sum_{k=1..n} (2^k-2)/k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A330719 a(n) = denominator(Sum_{k=1..n} (2^(k-1) - 1)/k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A212395 Number of move operations required to sort all permutations of [n] by insertion sort.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A280970 Number of comparisons required to sort all permutations of [n] by MTF sort.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula