A330718 -id:A330718 - cp's OEIS frontend

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

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

A108866 Numerator of Sum_{k=1..n} 2^k/k.

Original entry on oeis.org

0, 2, 4, 20, 32, 256, 416, 4832, 8192, 42496, 74752, 1467392, 2650112, 62836736, 115552256, 42790912, 79691776, 2535587840, 4766040064, 170851041280, 1617069867008, 3070050172928, 5843921666048, 256460544016384, 490390373269504, 4697678227177472, 9016382767235072

Offset: 0

N. J. A. Sloane, Jul 12 2005

Conjecture: for n > 3, numerator(-2/n + Sum_{k=1..n} 2^k/k) == 0 (mod n^2) if and only if n is prime. See my formula below. Cf. A332786. - Thomas Ordowski, Mar 02 2020

			The initial values of the sum are 2, 4, 20/3, 32/3, 256/15, 416/15, 4832/105, 8192/105, 42496/315, 74752/315, 1467392/3465, 2650112/3465, 62836736/45045, 115552256/45045, 42790912/9009, 79691776/9009, 2535587840/153153, 4766040064/153153, 170851041280/2909907, ...

A. M. Robert, A Course in p-adic Analysis, Springer, 2000; see p. 278.

Harvey P. Dale, Table of n, a(n) for n = 0..1000 [a(0) = 0 adapted by _Georg Fischer_, Mar 07 2020]

Cf. A087910. The denominators are A229726 (repeated).

Join[{0},Accumulate[Table[2^n/n,{n,30}]]//Numerator] (* Harvey P. Dale, Oct 28 2018 *)

a(n) = numerator(sum(k=1, n, 2^k/k)); \\ Michel Marcus, Mar 07 2020

a(n) = numerator(Sum_{k=1..n} (2^k-2)/k + Sum_{k=1..n} 2/k). This formula is a heuristic of my conjecture in the comments section. Cf. A330718. - Thomas Ordowski, Mar 02 2020

a(0) corrected by A.H.M. Smeets, Mar 06 2020

A279683 Number of move operations required to sort all permutations of [n] by MTF sort.

Original entry on oeis.org

0, 0, 1, 9, 78, 750, 8220, 102900, 1463280, 23451120, 419942880, 8331634080, 181689298560, 4323472433280, 111534141438720, 3101254066310400, 92468631077222400, 2943141763622860800, 99596858633182310400, 3570677764371119001600, 135190500045467682816000

Offset: 0

Alois P. Heinz, Dec 16 2016

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.

Conjecture: primes p such that p^4 divides a(p) are the Wolstenholme primes A088164. - Amiram Eldar and Thomas Ordowski, Jan 15 2020

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

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. A000142, A212395, A240797, A280970, A330718, A330719.

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

a[0] = 0; a[n_] := a[n] = a[n-1]*n + (n-1)!*(2^(n-1) - 1);
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, May 30 2018 *)

a(n) = a(n-1)*n + (n-1)! * (2^(n-1)-1) for n>0, a(0) = 0.
a(n) = (4*n-3)*a(n-1)-(n-1)*(5*n-7)*a(n-2)+(2*n-2)*(n-2)^2*a(n-3) for n>2.
a(n) ~ 2^n * (n-1)!. - Vaclav Kotesovec, Dec 25 2016
a(n) = n! * Sum_{k=1..n} (2^(k-1)-1)/k = A000142(n)*A330718(n)/A330719(n), for n > 0. - Amiram Eldar and Thomas Ordowski, Jan 15 2020

A290347 Numerators of the Harary index for the n-halved cube graph.

Original entry on oeis.org

0, 1, 6, 26, 100, 1096, 3920, 13936, 16544, 296256, 1068672, 11652352, 42658304, 1100471296, 4079876096, 15205967872, 56939270144, 642281037824, 2423854317568, 9177027411968, 34846713511936, 1459319692460032, 5568939824513024, 21297365878571008

Offset: 1

Eric W. Weisstein, Jul 28 2017

For p > 3, if p is prime, then p^2 divides a(p). Conjecture: for n > 3, if n^2 divides a(n), then n is prime. Primes p such that p^3 diviedes a(p) are probably A088164. - Thomas Ordowski, Mar 30 2025

			First few terms are 0, 1, 6, 26, 100, 1096/3, 3920/3, 13936/3, 16544, 296256/5, ....

Eric Weisstein's World of Mathematics, Harary Index
Eric Weisstein's World of Mathematics, Halved Cube Graph

Cf. A000265, A088164, A290348 (denominators), A330718.

Table[-2^(n - 1) HarmonicNumber[n] - 2^(2 n - 1) Re[LerchPhi[2, 1, n + 1]], {n, 20}] // Numerator

a(n) = -2^(n-1)*HarmonicNumber(n)-2^(2*n-1)*Re(LerchPhi(2,1,n+1)).

For n > 1, A000265(a(n)) = A330718(n). - Thomas Ordowski, Mar 30 2025

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

Original entry on oeis.org

0, 3, 3, 61, 25, 137, 343, 32663, 2357, 74689, 66671, 5299069, 2416531, 115545821, 106974277, 637525199, 74575583, 1588674349, 4496071973, 3234136824109, 1535024393629, 5843920343363, 5575228585159, 1961561381531581, 93953561866435, 9016382638527647, 2888981280567587, 200248741591132607, 96525489421136333

Offset: 1

Thomas Ordowski, Feb 24 2020

If p > 3 is a prime, then p^2 | a(p).
Does the above statement follow from Wolstenholme's theorem?
If p is a Wolstenholme prime (A088164), then p^3 | a(p).
However, it should be noted that also 7^3 | a(7).
Conjecture: there are no pseudoprimes m such that m^2 | a(m).
Is 7^2 the only weak pseudoprime (i.e., a composite m such that m | a(m))?

			a(5) = numerator(-1/5 + 1/1+2/2+4/3+8/4+16/5) = numerator(128/15 - 1/5) = numerator(25/3) = 25.

Robert Israel, Table of n, a(n) for n = 1..1367

Cf. A001008, A088164, A108866, A330718.

f:= proc(n) local k; numer(-1/n + add(2^(k-1)/k,k=1..n)) end proc:
map(f, [$1..30]); # Robert Israel, Sep 15 2024

n = 30; Numerator[Accumulate @ Table[(2^(k-1))/k, {k, 1, n}] - 1/Range[n]] (* Amiram Eldar, Feb 24 2020 *)

a(n) = numerator(-1/n + sum(k=1, n, 2^(k-1)/k)); \\ Michel Marcus, Feb 24 2020

a(n) = numerator(-2/n + S(n))/2 for odd n and a(n) = numerator(-2/n + S(n)) for even n, where S(n) = Sum_{k=1..n} 2^k/k, see A108866 / A229726.

a(n) = numerator(Sum_{k=1..n} (2^(k-1)-1)/k + Sum_{k=1..n-1} 1/k), see A330718 / A330719 and A001008 / A002805.

More terms from Amiram Eldar, Feb 24 2020

A331343 a(n) = lcm(1,2,...,n) * Sum_{k=1..n} (2^(k-1) - 1) / k.

Original entry on oeis.org

0, 1, 9, 39, 375, 685, 8575, 30485, 162855, 291627, 5785857, 10514427, 250200951, 461037291, 854622483, 3185234481, 101381371377, 190598779657, 6833215763803, 12935721409039, 24559552771039, 46750514134519, 2051664357879617, 3923102768811707, 37581323659852375

Offset: 1

Amiram Eldar and Thomas Ordowski, Jan 14 2020

nonn

By Wolstenholme's theorem, if p > 3 is a prime, then p^3 | a(p).
Conjecture: for n > 3, if n^3 | a(n), then n is prime. If so, there are no such pseudoprimes.
Problem: are there weak pseudoprimes m such that m^2 | a(m)? None up to 5*10^4.
Composite numbers m such that m | a(m) are 9, 25, 49, 99, 121, 125, 169, 221, 289, 343, 357, 361, 399, 529, 665, 841, 961, 1331, 1369, 1443, 1681, 1849, 2183, ...  Cf. A082180.
Prime numbers p such that p^4 | a(p) are probably only the Wolstenholme primes A088164.

Wikipedia, Wolstenholme's theorem.

Cf. A003418, A025529, A082180, A088164, A330718, A330719.

[Lcm([1..n])*&+[(2^(k-1)-1)/k:k in [1..n]]:n in [1..25]]; // Marius A. Burtea, Jan 14 2020

a[n_] := LCM @@ Range[n] * Sum[(2^(k-1) - 1) / k, {k, 1, n}]; Array[a, 25]

a(n) = lcm([1..n])*sum(k=1, n, (2^(k-1) - 1) / k); \\ Michel Marcus, Jan 14 2020

a(n) = A003418(n) * A330718(n) / A330719(n).

cp's OEIS Frontend

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

A108866 Numerator of Sum_{k=1..n} 2^k/k.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A279683 Number of move operations required to sort all permutations of [n] by MTF sort.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A290347 Numerators of the Harary index for the n-halved cube graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A331343 a(n) = lcm(1,2,...,n) * Sum_{k=1..n} (2^(k-1) - 1) / k.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula