|
| |
|
|
A059097
|
|
Numbers n such that the binomial coefficient C(2n,n) is not divisible by the square of an odd prime.
|
|
4
|
|
|
|
0, 1, 2, 3, 4, 6, 7, 9, 10, 11, 12, 21, 22, 28, 29, 30, 31, 36, 37, 54, 55, 57, 58, 110, 171, 784, 786
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Probably finite. Erdos believed there were no more terms.
The power of p that divides n! is (n-s)/(p-1), where s is the sum of the "digits" in the base-p representation of n (see Gouvea). - N. J. A. Sloane, Nov 26, 2005
Comments from David W. Wilson, Nov 21 2005: "The exponent e of prime p in n! can be computed as follows (in pseudo-C):
int e(int p, int n) { int s = 0; while (n > 0) { n /= p; s += n; } return s; }
The exponent of p in C(2n, n) is then f(p, n) = e(p, 2*n) - 2*e(p, n).
We can then use the following function to check if n is in the sequence:
bool isGood(int n) { for (int p = 3; p <= n; p += 2) { if (!isPrime(p)) continue; if (f(p, n) >= 2) return false; } return true; }"
|
|
|
REFERENCES
|
F. Q. Gouvea, p-Adic Numbers, Springer-Verlag, 1993; see p. 100.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, first ed, chap 5, prob 96.
R. K. Guy, Unsolved problems in Number Theory, section B33.
|
|
|
LINKS
|
Table of n, a(n) for n=1..27.
|
|
|
EXAMPLE
|
C(12,6)=924, which is not divisible by the square of an odd prime, so 6 is in the sequence.
|
|
|
MATHEMATICA
|
l = {}; Do[m = Binomial[2n, n]; While[EvenQ[m], m = m/2]; If[MoebiusMu[m] != 0, l = {l, n}], {n, 1000}]; Flatten[l] (Alonso del Arte, Nov 11 2005)
Alonso del Arte, Nov 11 2005: The following is an implementation of David W. Wilson's algorithm in Mma:
expoPF[p_, n_] := Module[{s, x}, x = n; s = 0; While[x > 0, x = Floor[x/p]; s = s + x]; s]
expoP2nCn[p_, n_] := expoPF[p, 2*n] - 2*expoPF[p, n]
goodQ[ n_ ] := TrueQ[ Module[ {flag, i}, flag = True; i = 2; While[ flag && Prime[ i ] < n, If[ expoP2nCn[ Prime[ i ], n ] > 1, flag = False ]; i++ ]; flag ] ]
Select[ Range[ 1000 ], goodQ[ # ] & ]
|
|
|
CROSSREFS
|
Cf. A000984. Cf. also A081391, n such that C[2n, n] has only one prime divisor of which exponent equals one.
Sequence in context: A047519 A070118 A070124 * A047301 A186275 A214857
Adjacent sequences: A059094 A059095 A059096 * A059098 A059099 A059100
|
|
|
KEYWORD
|
nonn,fini
|
|
|
AUTHOR
|
Jud McCranie, Jan 01 2001
|
|
|
EXTENSIONS
|
No other terms for n<=157430. - Naohiro Nomoto, May 12 2002
No other terms for n<=2^31 - 1. - Jack Brennen, Nov 21 2005
|
|
|
STATUS
|
approved
|
| |
|
|
