|
|
A002034
|
|
Kempner numbers: smallest positive integer m such that n divides m!.
(Formerly M0453 N0167)
|
|
133
|
|
|
1, 2, 3, 4, 5, 3, 7, 4, 6, 5, 11, 4, 13, 7, 5, 6, 17, 6, 19, 5, 7, 11, 23, 4, 10, 13, 9, 7, 29, 5, 31, 8, 11, 17, 7, 6, 37, 19, 13, 5, 41, 7, 43, 11, 6, 23, 47, 6, 14, 10, 17, 13, 53, 9, 11, 7, 19, 29, 59, 5, 61, 31, 7, 8, 13, 11, 67, 17, 23, 7, 71, 6, 73, 37, 10, 19, 11, 13, 79, 6, 9, 41, 83, 7
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Sometimes named after Florentin Smarandache, although studied 60 years earlier by Aubrey Kempner and 35 years before that by Lucas.
Kempner originally defined a(1) to be 0, and there are good reasons to prefer that (see Hungerbühler and Specker), but we shall stay with the by-now traditional value a(1) = 1. - N. J. A. Sloane, Jan 02 2021
Kempner gave an algorithm to compute a(n) from the prime factorization of n. Partial solutions were given earlier by Lucas in 1883 and Neuberg in 1887. - Jonathan Sondow, Dec 23 2004
a(n) is the degree of lowest degree monic polynomial over Z that vanishes identically on the integers mod n [Newman].
Smallest k such that n divides product of k consecutive integers starting with n + 1. - Amarnath Murthy, Oct 26 2002
If m and n are any integers with n > 1, then |e - m/n| > 1/(a(n) + 1)! (see Sondow 2006).
Degree of minimal linear recurrence satisfied by Bell numbers (A000110) read modulo n. [Lunnon et al.] - N. J. A. Sloane, Feb 07 2009
|
|
REFERENCES
|
E. Lucas, Question Nr. 288, Mathesis 3 (1883), 232.
R. Muller, Unsolved problems related to Smarandache Function, Number Theory Publishing Company, Phoenix, AZ, ISBN 1-879585-37-5, 1993.
J. Neuberg, Solutions des questions proposées, Question Nr. 288, Mathesis 7 (1887), 68-69.
Donald J. Newman, A Problem Seminar. Problem 17, Springer-Verlag, 1982.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
Florentin Smarandache, A Function in the Number Theory, Analele Univ. Timisoara, Fascicle 1, Vol. XVIII, 1980, pp. 79-88; Smarandache Function J., Vol. 1, No. 1-3 (1990), pp. 3-17.
|
|
LINKS
|
Aubrey J. Kempner, Miscellanea, The American Mathematical Monthly, Vol. 25, No. 5 (May, 1918), pp. 201-210. (See Section II, Concerning the smallest integer m! divisible by a given integer n.)
Jonathan Sondow and Kyle Schalm, Which partial sums of the Taylor series for e are convergents to e? (and a link to the primes 2, 5, 13, 37, 463), II, Gems in Experimental Mathematics (T. Amdeberhan, L. A. Medina, and V. H. Moll, eds.), Contemporary Mathematics, Vol. 517, Amer. Math. Soc., Providence, RI, 2010.
|
|
FORMULA
|
The following identities were given by Kempner (1918):
a(1) = 1.
a(n!) = n.
a(p) = p for p prime.
a(p1 * p2 * ... * pu) = pu if p1 < p2 < ... < pu are distinct primes.
a(p^k) = p * k for p prime and k <= p.
Let n = p1^e1 * p2^e2 * ... * pu^eu be the canonical factorization of n, then a(n) = max( a(p1^e1), a(p2^e2), ..., a(pu^eu) ).
(End)
Clearly a(n) >= P(n), the largest prime factor of n (= A006530). a(n) = P(n) for almost all n (Erdős and Kastanas 1994, Ivic 2004). The exceptions are A057109. a(n) = P(n) if and only if a(n) is prime because if a(n) > P(n) and a(n) were prime, then since n divides a(n)!, n would also divide (a(n)-1)!, contradicting minimality of a(n). - Jonathan Sondow, Jan 10 2005
If p is prime then a(p^k) = k*p for 0 <= k <= p. Hence it appears also that if n = 2^m * p(1)^e(1) * ... * p(r)^e(r) and if there exists b, 1 <= b <= r, such that Max(2 * m + 2, p(i) * e(i), 1 <= i <= r) = p(b) * e(b) with e(b) <= p(b) then a(n) = e(b) * p(b). E.g.: a(2145986896455317997802121296896) = a(2^10 * 3^3 * 7^9 * 11^9 * 13^8) = 13 * 8 = 104, since 8 * 13 = Max (2 * 10 + 2, 3 * 3, 7 * 9, 11 * 9, 13 * 8) and 8 <= 13. - Benoit Cloitre, Sep 01 2002
It appears that a(2^m - 1) is the largest prime factor of 2^m - 1 (A005420).
a(n!) = n for all n > 0 and a(p) = p if p is prime. - Jonathan Sondow, Dec 23 2004
Conjecture: a(n) = 1 + n - Sum_{k=1..n} Sum_{m=1..n} cos(-2*Pi*k/n*m!)/n. Formula verified for the first 500 terms. - Mats Granvik, Feb 26 2021
Limit_{n->oo} (1/n) * Sum_{k=2..n} log(a(k))/log(k) = A084945 (Finch, 1999). - Amiram Eldar, Jul 04 2021
|
|
EXAMPLE
|
1! = 1, but clearly 8 does not divide 1.
2! = 2, but 8 does not divide 2.
3! = 6, but 8 does not divide 6.
4! = 24, and 8 does divide 24. Hence a(8) = 4.
However, 9 does not divide 24.
5! = 120, but 9 does not divide 120.
6! = 720, and 9 does divide 720. Hence a(9) = 6.
|
|
MAPLE
|
a:=proc(n) local b: b:=proc(m) if type(m!/n, integer) then m else fi end: [seq(b(m), m=1..100)][1]: end: seq(a(n), n=1..84); # Emeric Deutsch, Aug 01 2005
g:= proc(p, u)
local i, t;
t:= 0;
for i from 1 while t < u do
t:= t + 1 + padic[ordp](i, p);
od;
p*(i-1)
end;
|
|
MATHEMATICA
|
Do[m = 1; While[ !IntegerQ[m!/n], m++ ]; Print[m], {n, 85}] (* or for larger n's *)
Kempner[1] := 1; Kempner[n_] := Max[Kempner @@@ FactorInteger[n]]; Kempner[p_, 1] := p; Kempner[p_, alpha_] := Kempner[p, alpha] = Module[{a, k, r, i, nu, k0 = alpha(p - 1)}, i = nu = Floor[Log[p, 1 + k0]]; a[1] = 1; a[n_] := (p^n - 1)/(p - 1); k[nu] = Quotient[alpha, a[nu]]; r[nu] = alpha - k[nu]a[nu]; While[r[i] > 0, k[i - 1] = Quotient[r[i], a[i - 1]]; r[i - 1] = r[i] - k[i - 1]a[i - 1]; i-- ]; k0 + Plus @@ k /@ Range[i, nu]]; Table[ Kempner[n], {n, 85}] (* Eric W. Weisstein, based on a formula of Kempner's, May 17 2004 *)
With[{facts = Range[100]!}, Flatten[Table[Position[facts, _?(Divisible[#, n] &), {1}, 1], {n, 90}]]] (* Harvey P. Dale, May 24 2013 *)
|
|
PROG
|
(PARI) a(n)=if(n<0, 0, s=1; while(s!%n>0, s++); s)
(PARI) a(n)=my(s=factor(n)[, 1], k=s[#s], f=Mod(k!, n)); while(f, f*=k++); k \\ Charles R Greathouse IV, Feb 28 2012
(PARI) valp(n, p)=my(s); while(n\=p, s+=n); s
K(p, e)=if(e<=p, return(e*p)); my(t=e*(p-1)\p*p); while(valp(t+=p, p)<e, ); t
(Haskell)
import Data.List (elemIndex)
import Data.Maybe (fromJust)
a002034 1 = 1
a002034 n = fromJust (a092495 n `elemIndex` a000142_list)
(Python)
from sympy import factorial
def a(n):
m=1
while True:
if factorial(m)%n==0: return m
else: m+=1
(Python)
from sympy import factorint
def valp(n, p):
s = 0
while n: n //= p; s += n
return s
def K(p, e):
if e <= p: return e*p
t = e*(p-1)//p*p
while valp(t, p) < e: t += p
return t
return 1 if n == 1 else max(K(p, e) for p, e in factorint(n).items())
|
|
CROSSREFS
|
Cf. A000142, A001113, A006530, A007672, A046022, A057109, A064759, A084945, A094371, A094372, A094404, A122378, A122379, A122416, A122417, A248937 (Fermi-Dirac analog: use unique representation of n > 1 as a product of distinct terms of A050376).
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|