TOPICS
Search

Smarandache Function

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook

The Smarandache function mu(n) is the function first considered by Lucas (1883), Neuberg (1887), and Kempner (1918) and subsequently rediscovered by Smarandache (1980) that gives the smallest value for a given n at which n|mu(n)! (i.e., n divides mu(n) factorial). For example, the number 8 does not divide 1!, 2!, 3!, but does divide 4!=4·3·2·1=8·3, so mu(8)=4.

SmarandacheFunction

For n=1, 2, ..., mu(n) is given by 1, 2, 3, 4, 5, 3, 7, 4, 6, 5, 11, ... (OEIS A002034), where it should be noted that Sloane defines mu(1)=1, while Ashbacher (1995) and Russo (2000, p. 4) take mu(1)=0. The incrementally largest values of mu(n) are 1, 2, 3, 4, 5, 7, 11, 13, 17, 19, 23, 29, ... (OEIS A046022), which occur at the values where mu(n)=n. The incrementally smallest values of mu(n) relative to n are mu(n)/n = 1, 1/2, 1/3, 1/4, 1/6, 1/8, 1/12, 3/40, 1/15, 1/16, 1/24, 1/30, ... (OEIS A094404 and A094372), which occur at n=1, 6, 12, 20, 24, 40, 60, 80, 90, 112, 120, 180, ... (OEIS A094371).

Formulas exist for immediately computing mu(n) for special forms of n. The simplest cases are

mu(1)=1
(1)
mu(n!)=n
(2)
mu(p)=p
(3)
mu(p_1p_2...p_k)=p_k
(4)
mu(p^alpha)=palpha
(5)

where p is a prime, p_i are distinct primes, p_1<p_2<...<p_k, and alpha<=p (Kempner 1918). In addition,

mu(P_p)=M_p
(6)

if P_p is the nth even perfect number and M_p is the corresponding Mersenne prime (Ashbacher 1997; Ruiz 1999a). Finally, if p is a prime number and n>=2 an integer, then

mu(p^(p^n))=p^(n+1)-p^n+p
(7)

(Ruiz 1999b).

The case p^alpha for alpha>p is more complicated, but can be computed by an algorithm due to Kempner (1918). To begin, define a_j recursively by

a_(j+1)=pa_j+1
(8)

with a_1=1. This can be solved in closed form as

a_j=(p^j-1)/(p-1).
(9)

Now find the value of nu such that a_nu<=alpha<a_(nu+1), which is given by

nu=|_log_p[1+alpha(p-1)]_|,
(10)

where |_x_| is the floor function. Now compute the sequences k_i and r_i according to the Euclidean algorithm-like procedure

alpha=k_nua_nu+r_nu
(11)
r_nu=k_(nu-1)a_(nu-1)+r_(nu-1)
(12)
|
(13)
r_(lambda+2)=k_(lambda+1)a_(lambda+1)+r_(lambda+1)
(14)
r_(lambda+1)=k_lambdaa_lambda
(15)

i.e., until the remainder r_lambda=0. At each step, k_i is the integer part of r_i/a_i and r_i is the remainder. For example, in the first step, k_nu=|_alpha/a_nu_| and r_nu=alpha-k_nua_nu. Then

mu(p^alpha)=(p-1)alpha+sum_(i=nu)^lambdak_i
(16)

(Kempner 1918).

The value of mu(n) for general n is then given by

mu(p_1^(alpha_1)p_2^(alpha_2)...p_r^(alpha_r))=max[mu(p_1^(alpha_1)),mu(p_2^(alpha_2)),...,mu(p_r^(alpha_r))]
(17)

(Kempner 1918).

For all n

mu(n)>=gpf(n),
(18)

where gpf(n) is the greatest prime factor of n.

mu(n) can be computed by finding gpf(n) and testing if n divides gpf(n)!. If it does, then mu(n)=gpf(n). If it doesn't, then mu(n)>gpf(n) and Kempner's algorithm must be used. The set of n for which ngpf(n)! (i.e., n does not divide gpf(n)!) has density zero as proposed by Erdős (1991) and proved by Kastanas (1994), but for small n, there are quite a large number of values for which ngpf(n)!. The first few of these are 4, 8, 9, 12, 16, 18, 24, 25, 27, 32, 36, 45, 48, 49, 50, ... (OEIS A057109). Letting N(x) denote the number of positive integers 2<=n<=x such that ngpf(n)!, Akbik (1999) subsequently showed that

N(x)<<xexp(-1/4sqrt(lnx)).
(19)

This was subsequently improved by Ford (1999) and De Koninck and Doyon (2003), the former of which is unfortunately incorrect. Ford (1999) proposed the asymptotic formula

N(x)∼(sqrt(pi)(1+ln2))/(2^(3/4))(lnxlnlnx)^(3/4)x^(1-1/u_0)rho(u_0)
(20)

where rho(u) is the Dickman function, u_0 is defined implicitly through

lnx=u_0(x^(1/u_0^2)-1),
(21)

and the constant needs correction (Ivić 2003). Ivić (2003) subsequently showed that

N(x)=x(2+O(sqrt(lnlnx/lnx)))×int_2^xrho(lnx/lnt)(lnt)/(t^2)dt,
(22)

and, in terms of elementary functions,

N(x)=xexp[-sqrt(2lnxlnlnx)(1+O(lnlnlnx/lnlnx))].
(23)

Tutescu (1996) conjectured that mu(n) never takes the same value for two consecutive arguments, i.e., mu(n)!=mu(n+1) for any n. This holds up to at least n=10^9 (Weisstein, Mar. 3, 2004).

Multiple values of n can have the same value of k=mu(n), as summarized in the following table for small k.

kn such that mu(n)=k
11
22
33, 6
44, 8, 12, 24
55, 10, 15, 20, 30, 40, 60, 120
69, 16, 18, 36, 45, 48, 72, 80, 90, 144, 180, 240, 360, 720

Let a(k) denote the smallest inverse of mu(n), i.e., the smallest n for which mu(n)=k. Then a(k) is given by

a(k)=[gpf(k)]^(e+1),
(24)

where

e=sum_(i=1)^(|_log_(gpf(k))(n-1)_|)|_(n-1)/([gpf(k)]^i)_|
(25)

(J. Sondow, pers. comm., Jan. 17, 2005), where gpf(k) is the greatest prime factor of k and |_x_| is the floor function. For k=1, 2, ..., a(k) is given by 1, 2, 3, 4, 5, 9, 7, 32, 27, 25, 11, 243, ... (OEIS A046021). Some values of mu(n) first occur only for very large n. The sequence of incrementally largest values of a(k) is 1, 2, 3, 4, 5, 9, 32, 243, 4096, 59049, 177147, 134217728, ... (OEIS A092233), corresponding to n=1, 2, 3, 4, 5, 6, 8, 12, 16, 24, 27, 32, ... (OEIS A092232).

To find the number of n for which mu(n)=k, note that by definition, n is a divisor of mu(n)! but not of (mu(n)-1)!. Therefore, to find all n for which mu(n) has a given value, say all n with mu(n)=k, take the set of all divisors of k! and omit the divisors of (k-1)!. In particular, the number b(k) of n for which mu(n)=k for k>1 is exactly

b(k)=d(k!)-d((k-1)!),
(26)

where d(m) denotes the number of divisors of m, i.e., the divisor function sigma_0(m). Therefore, the numbers of integers n with mu(n)=1, 2, ... are given by 1, 1, 2, 4, 8, 14, 30, 36, 64, 110, ... (OEIS A038024).

In particular, equation (26) shows that the inverse Smarandache function a(n) always exists since for every n there is an m with mu(m)=n (hence a smallest one a(n)), since d(n!)-d((n-1)!)>0 for n>1.

Sondow (2006) showed that mu(k) unexpectedly arises in an irrationality bound for e, and conjectures that the inequality n^2<mu(n)! holds for almost all n, where "for almost all" means except for a set of density zero. The exceptions are 2, 3, 6, 8, 12, 15, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, ... (OEIS A122378).

Since gpf(n)=mu(n) for almost all n (Erdős 1991, Kastanas 1994), where gpf(n) is the greatest prime factor, an equivalent conjecture is that the inequality n^2<gpf(n)! holds for almost all n. The exceptions are 2, 3, 4, 6, 8, 9, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, ... (OEIS A122380).

D. Wilson points out that if

I(n,p)=(n-Sigma(n,p))/(p-1),
(27)

is the power of the prime p in n!, where Sigma(n,p) is the sum of the base-p digits of n, then it follows that

a(n)=min_(p|n)p^(I(n-1,p)+1),
(28)

where the minimum is taken over the primes p dividing n. This minimum appears to always be achieved when p is the greatest prime factor of n.

See also

Factorial, Greatest Prime Factor, Pseudosmarandache Function, Smarandache Ceil Function, Smarandache Constants, Smarandache-Kurepa Function, Smarandache Near-to-Primorial Function, Smarandache-Wagstaff Function

Portions of this entry contributed by Jonathan Sondow (author's link)

Explore with Wolfram|Alpha

References

Akbik, S. "On a Density Problem of Erdős." Int. J. Math. Sci. 22, 655-658, 1999.Ashbacher, C. An Introduction to the Smarandache Function. Cedar Rapids, IA: Decisionmark, 1995.Ashbacher, C. "Problem 4616." School Sci. Math. 97, 221, 1997.Begay, A. "Smarandache Ceil Functions." Bulletin Pure Appl. Sci. India 16E, 227-229, 1997.De Koninck, J.-M. and Doyon, N. "On a Thin Set of Integers Involving the Largest Prime Factor Function." Int. J. Math. Math. Sci., No. 19, 1185-1192, 2003.Dumitrescu, C. and Seleacu, V. The Smarandache Function. Vail, AZ: Erhus University Press, 1996.Erdős, P. "Problem 6674." Amer. Math. Monthly 98, 965, 1991.Finch, S. "The Average Value of the Smarandache Function." Smarandache Notions J. 10, 95-96, 1999. http://www.gallup.unm.edu/~smarandache/SNBook10.pdf.Finch, S. "Moments of the Smarandache Function." Smarandache Notions J. 11, 140-141, 2000. http://www.gallup.unm.edu/~smarandache/SNBook11.pdf.Finch, S. R. "Golomb-Dickman Constant." §5.4 in Mathematical Constants. Cambridge, England: Cambridge University Press, pp. 284-292, 2003.Ford, K. "The Normal Behavior of the Smarandache Function." Smarandache Notions J. 10, 81-86, 1999. http://www.gallup.unm.edu/~smarandache/SNBook10.pdf."Functions in Number Theory." http://www.gallup.unm.edu/~smarandache/FUNCT1.TXT.Hungerbühler, N. and Specker, E. "A Generalization of the Smarandache Function to Several Variables." Integers: Electronic J. Combin. Number Th. 6, #A23, 2006 http://www.integers-ejcnt.org/vol6.html.Ibstedt, H. Surfing on the Ocean of Numbers--A Few Smarandache Notions and Similar Topics. Lupton, AZ: Erhus University Press, pp. 27-30, 1997.Ivić, A. "On a Problem of Erdős Involving the Largest Prime Factor of n." 5 Nov 2003. http://arxiv.org/abs/math.NT/0311056.Kastanas, I. "Solution to Problem 6674: The Smallest Factorial That Is a Multiple of n." Amer. Math. Monthly 101, 179, 1994.Kempner, A. J. "Miscellanea." Amer. Math. Monthly 25, 201-210, 1918.Lucas, E. "Question Nr. 288." Mathesis 3, 232, 1883.Neuberg, J. "Solutions de questions proposées, Question Nr. 288." Mathesis 7, 68-69, 1887.Ruiz, S. M. "Smarandache Function Applied to Perfect Numbers." Smarandache Notions J. 10, 114-155, 1999a.Ruiz, S. M. "A Result Obtained Using Smarandache Function." Smarandache Notions J. 10, 123-124, 1999b.Russo, F. A Set of New Smarandache Functions, Sequences, and Conjectures in Numer Theory. Lupton, AZ: American Research Press, 2000.Sandor, J. "On Certain Inequalities Involving the Smarandache Function." Abstracts of Papers Presented to the Amer. Math. Soc. 17, 583, 1996.Sloane, N. J. A. Sequences A002034/M0453, A038024, A046021, A046022, A057109, A092232, A092233, A094371, A094372, A094404, A122378, and A122380 in "The On-Line Encyclopedia of Integer Sequences."Smarandache, F. "A Function in Number Theory." Analele Univ. Timisoara, Ser. St. Math. 43, 79-88, 1980.Smarandache, F. Collected Papers, Vol. 1. Bucharest, Romania: Tempus, 1996.Smarandache, F. Collected Papers, Vol. 2. Kishinev, Moldova: Kishinev University Press, 1997.Sondow, J. "A Geometric Proof that e Is Irrational and a New Measure of Its Irrationality." Amer. Math. Monthly 113, 637-641, 2006.Tutescu, L. "On a Conjecture Concerning the Smarandache Function." Abstracts of Papers Presented to the Amer. Math. Soc. 17, 583, 1996.

Referenced on Wolfram|Alpha

Smarandache Function

Cite this as:

Sondow, Jonathan and Weisstein, Eric W. "Smarandache Function." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SmarandacheFunction.html

Subject classifications