A088164 -id:A088164 - cp's OEIS frontend

A267824 Composite numbers n such that binomial(2n-1, n-1) == 1 (mod n^2).

283686649, 4514260853041

Offset: 1

Jonathan Sondow, Jan 25 2016

Babbage proved the congruence holds if n > 2 is prime.
See A088164 and A263882 for references, links, and additional comments.
Conjecture: n is a term if and only if n = A088164(i)^2 for some i >= 1 (cf. McIntosh, 1995, p. 385). - Felix Fröhlich, Jan 27 2016
The "if" part of the conjecture is true: see the McIntosh reference. - Jonathan Sondow, Jan 28 2016
The above conjecture implies that this sequence and A228562 are disjoint. - Felix Fröhlich, Jan 27 2016
Composites c such that A281302(c) > 1. - Felix Fröhlich, Feb 21 2018

			a(1) = 16843^2 and a(2) = 2124679^2 are squares of Wolstenholme primes A088164.

Richard J. McIntosh, On the converse of Wolstenholme's Theorem, Acta Arithmetica, 71 (1995), 381-389.
J. Sondow, Extending Babbage's (non-)primality tests, in Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, 269-277, CANT 2015 and 2016, New York, 2017; arXiv:1812.07650 [math.NT], 2018.

Cf. A000984, A034602, A082180, A088164, A099905, A099906, A099907, A099908, A136327, A177783, A212557, A228562, A242473, A244214, A244919, A246130, A246132, A246133, A246134, A260209, A260210, A263429, A263882, A281302.

A260209 Values A such that p=prime(n) satisfies binomial(2p-1, p-1) == 1 + A*p (mod p^4).

Original entry on oeis.org

1, 3, 25, 245, 121, 169, 867, 3249, 6877, 9251, 961, 15059, 57154, 61017, 68479, 106742, 201898, 208376, 107736, 176435, 330398, 237158, 158447, 213867, 903264, 856884, 21218, 755634, 1259386, 944906, 161290, 531991, 150152, 656914, 1287658, 592826, 640874

Offset: 1

Felix Fröhlich, Jul 19 2015

nonn

p is a Wolstenholme prime (A088164) iff a(n) == 0. This holds for n = 1944 and n = 157504.
When performing a search for Wolstenholme primes, one can choose an integer constant c >= 0 and record all primes p with A <= c in order to get a larger data set.
The values here asymptotically appear to grow more quickly than those in A260210.
It appears that a(n)/A260210(n) = A001248(n) for all n.

Felix Fröhlich, Table of n, a(n) for n = 1..10000

Cf. A088164, A241014, A244801, A250406, A258367, A260210.

f[n_] := Block[{p = Prime@ n}, (Mod[ Binomial[2p - 1, p - 1], p^4] - 1)/p]; Array[f, 37] (* Robert G. Wilson v, Jul 29 2015 *)

a(n) = p=prime(n); (lift(Mod(binomial(2*p-1, p-1), p^4))-1)/p

A260210 A034602(n) modulo prime(n).

Original entry on oeis.org

1, 5, 1, 1, 3, 9, 13, 11, 1, 11, 34, 33, 31, 38, 58, 56, 24, 35, 62, 38, 23, 27, 96, 84, 2, 66, 106, 74, 10, 31, 8, 34, 58, 26, 26, 144, 150, 140, 167, 137, 31, 107, 78, 157, 1, 103, 165, 97, 111, 60, 196, 48, 97, 259, 155, 175, 244, 13, 269, 34, 184, 222, 54

Offset: 3

Felix Fröhlich, Jul 19 2015

nonn

p is a Wolstenholme prime (A088164) iff a(n) = 0. This holds for n = 1944 and n = 157504.
When performing a search for Wolstenholme primes, one can choose an integer constant c >= 0 and record all primes with a(n) <= c in order to get a larger data set.
The values here appear to have a nicer asymptotic growth behavior than those in A260209.
It appears that A260209(n)/a(n) = A001248(n).
The formula only returns integers for primes greater than 3. - Robert G. Wilson v, Jul 29 2015

Felix Fröhlich, Table of n, a(n) for n = 3..10000

Cf. A034602, A088164, A241014, A244801, A250406, A258367, A260209.

f[n_] := Block[{p = Prime@ n}, (Mod[ Binomial[2p - 1, p - 1], p^4] - 1)/p^3]; Array[f, 60, 3] (* Robert G. Wilson v, Jul 29 2015 *)

a(n) = p=prime(n); lift(Mod(binomial(2*p-1, p-1)\p^3, p))

A034602(n)/prime(n) = A260209(n)/prime(n)^2, for n>2. - Robert G. Wilson v, Jul 29 2015

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

A244214 a(n) = binomial(2*c-1, c-1) (mod c^3), where c is the n-th composite.

Original entry on oeis.org

35, 30, 291, 253, 378, 782, 2404, 1260, 291, 3378, 410, 7899, 3996, 6030, 126, 10988, 11188, 5180, 19712, 8483, 5334, 34394, 1841, 21410, 20580, 39556, 38810, 64260, 35972, 66060, 36504, 61326, 1716, 123628, 49140, 63748, 124392, 20091, 99388, 157767, 24392

Offset: 1

Felix Fröhlich, Jun 23 2014

nonn

A counterexample to the converse of Wolstenholme's theorem (CWT) must have a(n) = 1. No such counterexample is known and if CWT holds, then a(n) > 1 for all n. If the square of a prime p is a counterexample to CWT, that prime satisfies the Wolstenholme congruence modulo p^6 (Cf. McIntosh (1995), p. 387).

Felix Fröhlich, Table of n, a(n) for n = 1..10000
C. Helou and G. Terjanian, On Wolstenholme's theorem and its converse, Journal of Number Theory, Volume 128, Issue 3 (2008), 475-499.
R. J. McIntosh, On the converse of Wolstenholme's Theorem, Acta Arithmetica, 71 (1995), 381-389.
V. Trevisan and K. Weber, Testing the converse of Wolstenholme's theorem, Matematica Contemporanea, 21 (2001), 275-286.
Wikipedia, Wolstenholme's theorem

Cf. A088164, A228562.

Mod[Binomial[2#-1,#-1],#^3]&/@Select[Range[100],CompositeQ] (* Harvey P. Dale, May 03 2023 *)

forcomposite(c=1, 100, print1(lift(Mod(binomial(2*c-1, c-1), c^3)), ", "))

Edited by Felix Fröhlich, May 27 2021

A263882 Babbage quotients b_p = (binomial(2p-1, p-1) - 1)/p^2 with p = prime(n).

Original entry on oeis.org

1, 5, 35, 2915, 30771, 4037381, 48954659, 7782070631, 17875901604959, 242158352370063, 637739431824553035, 126348774791431208099, 1794903484322270273951, 367972191114796344623951, 1116504994413003106003899551, 3498520498083111051973370669639

Offset: 2

Jonathan Sondow, Nov 22 2015

nonn

Charles Babbage proved in 1819 that b_p is an integer for prime p > 2. In 1862 Wolstenholme proved that the Wolstenholme quotient W_p = b_p / p is an integer for prime p > 3; see A034602.

The quotient b_n is an integer for composite n in A267824. No composite n is known for which W_n is an integer.

			a(2) = (binomial(2*3-1,3-1) - 1)/3^2 = (binomial(5,2) - 1)/9 = (10-1)/9 = 1.

R. K. Guy, Unsolved Problems in Number Theory, Sect. B31.

Robert Israel, Table of n, a(n) for n = 2..260
C. Babbage, Demonstration of a theorem relating to prime numbers, Edinburgh Philosophical Journal, 1 (1819), 46-49.
R. Mestrovic, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2011), arXiv:1111.3057 [math.NT], 2011.
J. Sondow, Extending Babbage's (non-)primality tests, in Combinatorial and Additive Number Theory II, Springer Proc. in Math. & Stat., Vol. 220, 269-277, CANT 2015 and 2016, New York, 2017; arXiv:1812.07650 [math.NT], 2018.
Wikipedia, Wolstenholme's theorem
J. Wolstenholme, On certain properties of prime numbers, Quarterly Journal of Pure and Applied Mathematics, 5 (1862), 35-39.

Cf. A034602, A088164, A099906, A267824.

[(Binomial(2*NthPrime(n)-1, NthPrime(n)-1)-1)/NthPrime(n)^2: n in [2..20]]; // Vincenzo Librandi, Nov 25 2015

map(p -> (binomial(2*p-1,p-1)-1)/p^2, select(isprime,[seq(i,i=3..100,2)])); # Robert Israel, Nov 24 2015

Table[(Binomial[2*Prime[n] - 1, Prime[n] - 1] - 1)/Prime[n]^2, {n, 2, 17}]
Table[(Binomial[2p-1,p-1]-1)/p^2,{p,Prime[Range[2,20]]}] (* Harvey P. Dale, Jul 20 2019 *)

a(n) = prime(n)*A034602(n) for n > 2.

a(PrimePi(A088164(n))) == 0 mod A088164(n)^2.

A298946 a(n) = binomial(2*c-1, c-1) (mod c^4), where c is the n-th composite number.

Original entry on oeis.org

35, 462, 2339, 4627, 2378, 4238, 5148, 1260, 57635, 85026, 64410, 100509, 163716, 171918, 93876, 309780, 148969, 444220, 370712, 532771, 652200, 938386, 816466, 907874, 569300, 1107298, 2470810, 2953692, 887812, 1341810, 2956584, 1941390, 589961, 6248628

Offset: 1

Felix Fröhlich, Jan 30 2018

nonn

Composites c where a(n) = 1 could be called "Wolstenholme pseudoprimes". Do any such composites exist?

A necessary condition for c to be a "Wolstenholme pseudoprime" would be that it is a term of A228562 or A267824.

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

Cf. A088164, A228562, A244214, A267824, A281302, A298944, A298945.

R:= NULL:
count:= 0: F:= 10;
for n from 4 while count < 100 do
  F:= F * (4*n-2)/n;
  if not isprime(n) then
     count:= count+1;
     R:= R, F mod (n^4);
  fi
od:
R; # Robert Israel, Feb 02 2018

Table[Mod[Binomial[2 c - 1, c - 1], c^4], {c, Select[Range@ 50, CompositeQ]}] (* Michael De Vlieger, Feb 01 2018 *)

forcomposite(c=1, 200, print1(lift(Mod(binomial(2*c-1, c-1), c^4)), ", "))

from sympy import binomial, composite
def A298946(n):
    c = composite(n)
    return binomial(2*c-1,c-1) % c**4 # Chai Wah Wu, Feb 02 2018

A177783 Wolstenholme quotient of prime p=A000040(n), i.e., such integer m

Original entry on oeis.org

3, 6, 6, 7, 10, 14, 18, 20, 16, 24, 17, 38, 39, 19, 29, 28, 12, 53, 31, 19, 53, 58, 48, 42, 1, 33, 53, 37, 5, 81, 4, 17, 29, 13, 13, 72, 75, 70, 173, 159, 111, 150, 39, 178, 106, 163, 196, 163, 172, 30, 98, 24, 177, 261, 212, 223, 122, 147, 276, 17, 92, 111, 27, 209, 241

Offset: 3

Max Alekseyev, May 13 2010

nonn

a(n) = 0 iff A000040(n) is a Wolstenholme prime (given by A088164).

For n>2 and p=A000040(n), H(p^2-p) == H(p^2-1) == a(n)*p (mod p^2).

David W. Boyd, A p-adic study of the partial sums of the harmonic series, Experimental Math., Vol. 3 (1994), No. 4, 287-302.
R. Mestrovic, Wolstenholme's theorem: Its Generalizations and Extensions in the last hundred and fifty years (1862-2011), arXiv:1111.3057 [math.NT], 2011.
R. Mestrovic, On a Congruence Modulo n^3 Involving Two Consecutive Sums of Powers, Journal of Integer Sequences, Vol. 17 (2014), 14.8.4.
Jianqiang Zhao, Bernoulli numbers, Wolstenholme's theorem, and p^5 variations of Lucas' theorem, Journal of Number Theory, Volume 123, Issue 1, March 2007, Pages 18-26.

Cf. A034602, A072984, A087754, A092101, A092103, A092193, A128673.

{ a(n) = my(p); p=prime(n); ((binomial(2*p-1,p)-1)/2/p^3)%p }

a(n) = H(p-1)/p^2 mod p = A001008(p-1)/A002805(p-1)/p^2 mod p = A034602(n)/2 mod p = (binomial(2*p-1,p)-1)/(2*p^3) mod p, where p = A000040(n).
a(n) = (-1/3)*B(p-3) mod p, with p=prime(n) and B(n) is the n-th Bernoulli number. - Michel Marcus, Feb 05 2016
a(n) = A087754(n)/4 mod A000040(n).

Edited by Max Alekseyev, May 16 2010

A242473 Binomial(2p-1,p-1) modulo p^4, with p=prime(n).

Original entry on oeis.org

3, 10, 126, 1716, 1332, 2198, 14740, 61732, 158172, 268280, 29792, 557184, 2343315, 2623732, 3218514, 5657327, 11911983, 12710937, 7218313, 12526886, 24119055, 18735483, 13151102, 19034164, 87616609, 86545285, 2185455, 80852839, 137273075, 106774379, 20483831, 69690822, 20570825

Offset: 1

Felix Fröhlich, May 26 2014

nonn

A value of 1 indicates a Wolstenholme prime.

Chai Wah Wu, Table of n, a(n) for n = 1..10000

Cf. A088164, A099905, A099906, A099907. Subsequence of A099908.

Table[Mod[Binomial[2p-1,p-1],p^4],{p,Prime[Range[30]]}] (* Harvey P. Dale, Jun 26 2017 *)

forprime(n=2, 10^2, m=(binomial(2*n-1, n-1)%n^4); print1(m, ", "));

from _future_ import division
from sympy import isprime
A242473_list, b = [], 1
for n in range(1,10**4):
    if isprime(n):
        A242473_list.append(b % n**4)
    b = b*2*(2*n+1)//(n+1) # Chai Wah Wu, Jan 26 2016

from sympy import Mod, binomial, prime
def A242473(n): return int(Mod(binomial(2*(p:=prime(n))-1,p-1,evaluate=False),p**4)) # Chai Wah Wu, Apr 24 2025

A244919 For odd prime p, largest k such that binomial(2p-1, p-1) is congruent to 1 modulo p^k.

Original entry on oeis.org

2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3

Offset: 2

Felix Fröhlich, Jul 08 2014

nonn

Wolstenholme's theorem implies that k >= 3 for all p > 3. The prime p is a Wolstenholme prime if and only if k > 3. For the primes up to 10^9 this holds only for p = 16843 and p = 2124679, where in each case a(n) = 4 (i.e. a(1944) = 4 and a(157504) = 4).

R. J. McIntosh, On the converse of Wolstenholme's theorem, Acta Arith., Volume 71, Issue 4 (1995), 381-389.
R. J. McIntosh and E. L. Roettger, A search for Fibonacci-Wieferich and Wolstenholme primes, Math. Comp., 76 (2007), 2087-2094.

Cf. A034602, A088164.

forprime(p=3, 10^3, k=1; while(Mod(binomial(2*p-1, p-1), p^k)==1, j=k; k++); if(Mod(binomial(2*p-1, p-1), p^k)!=1, print1(j, ", ")))

cp's OEIS Frontend

A267824 Composite numbers n such that binomial(2n-1, n-1) == 1 (mod n^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A260209 Values A such that p=prime(n) satisfies binomial(2p-1, p-1) == 1 + A*p (mod p^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A260210 A034602(n) modulo prime(n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

A244214 a(n) = binomial(2*c-1, c-1) (mod c^3), where c is the n-th composite.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A263882 Babbage quotients b_p = (binomial(2p-1, p-1) - 1)/p^2 with p = prime(n).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula

A298946 a(n) = binomial(2*c-1, c-1) (mod c^4), where c is the n-th composite number.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

A177783 Wolstenholme quotient of prime p=A000040(n), i.e., such integer m