|
%I M0453 N0167 #229 Sep 07 2023 03:59:35
%S 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,
%T 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,
%U 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
%N Kempner numbers: smallest positive integer m such that n divides m!.
%C Sometimes named after Florentin Smarandache, although studied 60 years earlier by Aubrey Kempner and 35 years before that by Lucas.
%C 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
%C 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
%C a(n) is the degree of lowest degree monic polynomial over Z that vanishes identically on the integers mod n [Newman].
%C Smallest k such that n divides product of k consecutive integers starting with n + 1. - _Amarnath Murthy_, Oct 26 2002
%C If m and n are any integers with n > 1, then |e - m/n| > 1/(a(n) + 1)! (see Sondow 2006).
%C Degree of minimal linear recurrence satisfied by Bell numbers (A000110) read modulo n. [Lunnon et al.] - _N. J. A. Sloane_, Feb 07 2009
%D E. Lucas, Question Nr. 288, Mathesis 3 (1883), 232.
%D R. Muller, Unsolved problems related to Smarandache Function, Number Theory Publishing Company, Phoenix, AZ, ISBN 1-879585-37-5, 1993.
%D J. Neuberg, Solutions des questions proposées, Question Nr. 288, Mathesis 7 (1887), 68-69.
%D Donald J. Newman, A Problem Seminar. Problem 17, Springer-Verlag, 1982.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D 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.
%H Alois P. Heinz, <a href="/A002034/b002034.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from T. D. Noe)
%H Charles Ashbacher, <a href="https://web.archive.org/web/20170222073259/http://www.gallup.unm.edu/~smarandache/Ashbacher-SmFu.pdf">An Introduction to the Smarandache Function</a>, Erhus Univ. Press, Vail, 62 pages, 1995 [WaybackMachine cached version added by _Felix Fröhlich_, Sep 10 2018].
%H Constantin Dumitrescu, <a href="https://web.archive.org/web/20170222073346/http://www.gallup.unm.edu/~smarandache/SN/ScArt5/BriefHistory.pdf">A brief history of the "Smarandache function"</a>, Bull. Pure Appl. Sci. Sec. E, Math., Vol. 12, No. 1-2 (1993), pp. 77-82 [WaybackMachine cached version added by _Felix Fröhlich_, Sep 10 2018].
%H Constantin Dumitrescu and Vasile Seleacu, <a href="https://web.archive.org/web/20150912034132/http://www.gallup.unm.edu/~smarandache/Dumitrescu-SmFunction.pdf">The Smarandache Function</a>, Erhus Univ. Press, Vail, 137 pages, 1996 [WaybackMachine cached version added by _Felix Fröhlich_, Sep 10 2018].
%H Jason Earls, <a href="https://pdfs.semanticscholar.org/4559/ac50797ddeda688576630c4d92229440a0a3.pdf#page=243">The Smarandache sum of composites between factors function</a>, in Smarandache Notions Journal, Vol. 14, No. 1 (2004), p. 246.
%H Paul Erdős and Ilias Kastanas, <a href="http://www.jstor.org/stable/2324376">Solution 6674: The smallest factorial that is a multiple of n</a>, Amer. Math. Monthly, Vol. 101, No. 2 (1994) p. 179.
%H Steven R. Finch, <a href="https://doi.org/10.5281/zenodo.8879">The average value of the Smarandache function</a>, Smarandache Notions Journal, Vol. 10, No. 1-3 (1999), pp. 95-96.
%H Mats Granvik, <a href="/A002034/a002034_2.txt">Mathematica program to check the conjectured formula</a>, Feb 28 2021.
%H Norbert Hungerbühler and Ernst Specker, <a href="http://www.emis.de/journals/INTEGERS/papers/g23/g23.Abstract.html">A generalization of the Smarandache Function to several variables</a>, INTEGERS, Vol. 6 (2006), #A23
%H Aleksandar Ivić, <a href="http://arXiv.org/abs/math/0311056">On a problem of Erdős involving the largest prime factor of n</a>, arXiv:math/0311056 [math.NT], 2003-2004.
%H Aubrey J. Kempner, <a href="http://www.jstor.org/stable/2972639">Miscellanea</a>, 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.)
%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1983__84__45_0">Sur quelques problèmes relatifs au vote pondéré</a>, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), pp. 45-63.
%H Xiumei Li and Min Sha, <a href="https://arxiv.org/abs/1907.00370">A proof of Sondow's conjecture on the Smarandache function</a>, arXiv preprint arXiv:1907.00370 [math.NT], 2019-2020. Amer. Math. Monthly, 127:10 (2020), 939-943.
%H W. F. Lunnon et al., <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa35/aa3511.pdf">Arithmetic properties of Bell numbers to a composite modulus I</a>, Acta Arith., Vol. 35 (1979), pp. 1-16. [From _N. J. A. Sloane_, Feb 07 2009]
%H Jon Perry, <a href="http://fs.unm.edu/SN/CalculatingSmaraNumbers.pdf">Calculating the Smarandache Numbers</a>, Smarandache Notions Journal, Vol. 14, No. 1 (2004), pp. 124-127.
%H Project Euler, <a href="https://projecteuler.net/problem=549">Problem 549: Divisibility of factorials</a>.
%H Sebastián Martín Ruiz, <a href="http://doi.org/10.5281/zenodo.8919">A Congruence with Smarandache's Function</a>, Smarandache Notions Journal, Vol. 10, No. 1-3 (1999), pp. 130-132.
%H József Sándor, <a href="https://pdfs.semanticscholar.org/177f/0a19d067aef7a92a1d2c947d60eb375d455c.pdf">The Smarandache minimum and maximum functions</a>, Scientia Magna, Vol. 1, No. 2 (2005), pp. 162-166. See p. 164.
%H Jonathan Sondow, <a href="http://arxiv.org/abs/0704.1282"> A geometric proof that e is irrational and a new measure of its irrationality</a>, Amer. Math. Monthly, Vol. 113 (2006), pp. 637-641 and Vol. 114 (2007), p. 659.
%H Jonathan Sondow and Kyle Schalm, <a href="http://arxiv.org/abs/0709.0671">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</a>, Gems in Experimental Mathematics (T. Amdeberhan, L. A. Medina, and V. H. Moll, eds.), Contemporary Mathematics, Vol. 517, Amer. Math. Soc., Providence, RI, 2010.
%H Jonathan Sondow and Eric W. Weisstein, <a href="http://mathworld.wolfram.com/SmarandacheFunction.html">MathWorld: Smarandache Function</a>.
%H J. Thompson, <a href="/A002034/a002034.pdf">A propriety (sic) of smarandache function, Abstract 878-11-758</a>, Notices Amer. Math. Soc., Vol. 14 (1993), p. 41. [Annotated scanned copy]
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Kempner_function">Kempner function</a>.
%H <a href="/index/Fa#factorial">Index entries for sequences related to factorial numbers</a>.
%F A000142(a(n)) = A092495(n). - _Reinhard Zumkeller_, Aug 24 2011
%F From _Joerg Arndt_, Jul 14 2012: (Start)
%F The following identities were given by Kempner (1918):
%F a(1) = 1.
%F a(n!) = n.
%F a(p) = p for p prime.
%F a(p1 * p2 * ... * pu) = pu if p1 < p2 < ... < pu are distinct primes.
%F a(p^k) = p * k for p prime and k <= p.
%F 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) ).
%F (End)
%F 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
%F 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
%F It appears that a(2^m - 1) is the largest prime factor of 2^m - 1 (A005420).
%F a(n!) = n for all n > 0 and a(p) = p if p is prime. - _Jonathan Sondow_, Dec 23 2004
%F 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
%F Limit_{n->oo} (1/n) * Sum_{k=2..n} log(a(k))/log(k) = A084945 (Finch, 1999). - _Amiram Eldar_, Jul 04 2021
%e 1! = 1, but clearly 8 does not divide 1.
%e 2! = 2, but 8 does not divide 2.
%e 3! = 6, but 8 does not divide 6.
%e 4! = 24, and 8 does divide 24. Hence a(8) = 4.
%e However, 9 does not divide 24.
%e 5! = 120, but 9 does not divide 120.
%e 6! = 720, and 9 does divide 720. Hence a(9) = 6.
%p 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
%p g:= proc(p,u)
%p local i,t;
%p t:= 0;
%p for i from 1 while t < u do
%p t:= t + 1 + padic[ordp](i,p);
%p od;
%p p*(i-1)
%p end;
%p A002034:= x -> max(map(g@op, ifactors(x)[2])); # _Robert Israel_, Apr 20 2014
%t Do[m = 1; While[ !IntegerQ[m!/n], m++ ]; Print[m], {n, 85}] (* or for larger n's *)
%t 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 *)
%t With[{facts = Range[100]!}, Flatten[Table[Position[facts, _?(Divisible[#, n] &), {1}, 1], {n, 90}]]] (* _Harvey P. Dale_, May 24 2013 *)
%o (PARI) a(n)=if(n<0,0,s=1; while(s!%n>0,s++); s)
%o (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
%o (PARI) valp(n,p)=my(s);while(n\=p,s+=n);s
%o K(p,e)=if(e<=p,return(e*p));my(t=e*(p-1)\p*p);while(valp(t+=p,p)<e,);t
%o a(n)=my(f=factor(n),m=1);for(i=1,#f~,m=max(K(f[i,1],f[i,2]),m));m \\ _Charles R Greathouse IV_, Jul 30 2013
%o (Haskell)
%o import Data.List (elemIndex)
%o import Data.Maybe (fromJust)
%o a002034 1 = 1
%o a002034 n = fromJust (a092495 n `elemIndex` a000142_list)
%o -- _Reinhard Zumkeller_, Aug 24 2011
%o (Python)
%o from sympy import factorial
%o def a(n):
%o m=1
%o while True:
%o if factorial(m)%n==0: return m
%o else: m+=1
%o [a(n) for n in range(1, 101)] # _Indranil Ghosh_, Apr 24 2017
%o (Python)
%o from sympy import factorint
%o def valp(n, p):
%o s = 0
%o while n: n //= p; s += n
%o return s
%o def K(p, e):
%o if e <= p: return e*p
%o t = e*(p-1)//p*p
%o while valp(t, p) < e: t += p
%o return t
%o def A002034(n):
%o return 1 if n == 1 else max(K(p, e) for p, e in factorint(n).items())
%o print([A002034(n) for n in range(1, 85)]) # _Michael S. Branicky_, Jun 09 2022 after _Charles R Greathouse IV_
%Y 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).
%Y See A339594-A339596 for higher-dimensional generalizations.
%K nonn,nice,easy
%O 1,2
%A _N. J. A. Sloane_
%E Error in 45th term corrected by _David W. Wilson_, May 15 1997
|
