login
Smallest number with exactly n divisors.
(Formerly M1026)
218

%I M1026 #121 Aug 17 2024 22:28:47

%S 1,2,4,6,16,12,64,24,36,48,1024,60,4096,192,144,120,65536,180,262144,

%T 240,576,3072,4194304,360,1296,12288,900,960,268435456,720,1073741824,

%U 840,9216,196608,5184,1260,68719476736,786432,36864,1680,1099511627776,2880

%N Smallest number with exactly n divisors.

%C A number n is called ordinary iff a(n)=A037019(n). Brown shows that the ordinary numbers have density 1 and all squarefree numbers are ordinary. See A072066 for the extraordinary or exceptional numbers. - _M. F. Hasler_, Oct 14 2014

%C All terms are in A025487. Therefore, a(n) is even for n > 1. - _David A. Corneth_, Jun 23 2017 [corrected by _Charles R Greathouse IV_, Jul 05 2023]

%D M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 840.

%D L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, p. 52.

%D J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 86.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Matthew House, <a href="/A005179/b005179.txt">Table of n, a(n) for n = 1..3322</a> (terms 1..2000 from Don Reble)

%H M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].

%H R. Brown, <a href="http://dx.doi.org/10.1016/j.jnt.2005.04.004">The minimal number with a given number of divisors</a>, Journal of Number Theory 116 (2006) 150-158.

%H M. E. Grost, <a href="http://www.jstor.org/stable/2315183">The smallest number with a given number of divisors</a>, Amer. Math. Monthly, 75 (1968), 725-729.

%H J. Roberts, <a href="/A007415/a007415.pdf">Lure of the Integers</a>, Annotated scanned copy of pp. 81, 86 with notes.

%H Anna K. Savvopoulou and Christopher M. Wedrychowicz, <a href="http://dx.doi.org/10.1007/s11139-014-9572-9">On the smallest number with a given number of divisors</a>, The Ramanujan Journal, 2015, Vol. 37, pp. 51-64.

%H David Singmaster, <a href="/A005178/a005178.pdf">Letter to N. J. A. Sloane</a>, Oct 03 1982.

%H T. Verhoeff, <a href="http://www.cs.uwaterloo.ca/journals/JIS/trapzoid.html">Rectangular and Trapezoidal Arrangements</a>, J. Integer Sequences, Vol. 2, 1999, #99.1.6.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Divisor.html">Divisor</a>

%H R. G. Wilson v, <a href="/A005179/a005179.pdf">Letter to N. J. A. Sloane</a>, Dec 17 1991.

%F a(p) = 2^(p-1) for primes p: a(A000040(n)) = A061286(n); a(p^2) = 6^(p-1) for primes p: a(A001248(n)) = A061234(n); a(p*q) = 2^(q-1)*3^(p-1) for primes p<=q: a(A001358(n)) = A096932(n); a(p*m*q) = 2^(q-1) * 3^(m-1) * 5^(p-1) for primes p<m<q: A005179(A007304(n)) = A061299(n). - _Reinhard Zumkeller_, Jul 15 2004

%F a(p^n) = (2*3...*p_n)^(p-1) for p > log p_n / log 2. Unpublished proof from Andrzej Schinzel. - _Thomas Ordowski_, Jul 22 2005

%F If p is a prime and n=p^k then a(p^k)=(2*3*...*s_k)^(p-1) where (s_k) is the numbers of the form q^(p^j) for every q and j>=0, according to Grost (1968), Theorem 4. For example, if p=2 then a(2^k) is the product of the first k members of the A050376 sequence: number of the form q^(2^j) for j>=0, according to Ramanujan (1915). - _Thomas Ordowski_, Aug 30 2005

%F a(2^k) = A037992(k). - _Thomas Ordowski_, Aug 30 2005

%F a(n) <= A037019(n) with equality except for n in A072066. - _M. F. Hasler_, Jun 15 2022

%p A005179_list := proc(SearchLimit, ListLength)

%p local L, m, i, d; m := 1;

%p L := array(1..ListLength,[seq(0,i=1..ListLength)]);

%p for i from 1 to SearchLimit while m <= ListLength do

%p d := numtheory[tau](i);

%p if d <= ListLength and 0 = L[d] then L[d] := i;

%p m := m + 1; fi

%p od:

%p print(L) end: A005179_list(65537,18);

%p # If a '0' appears in the list the search limit has to be increased. - _Peter Luschny_, Mar 09 2011

%p # alternative

%p # Construct list of ordered lists of factorizations of n with

%p # minimum divisors mind.

%p # Returns a list with A001055(n) entries if called with mind=2.

%p # Example: print(ofact(10^3,2))

%p ofact := proc(n,mind)

%p local fcts,d,rec,r ;

%p fcts := [] ;

%p for d in numtheory[divisors](n) do

%p if d >= mind then

%p if d = n then

%p fcts := [op(fcts),[n]] ;

%p else

%p # recursive call supposed one more factor fixed now

%p rec := procname(n/d,max(d,mind)) ;

%p for r in rec do

%p fcts := [op(fcts),[d,op(r)]] ;

%p end do:

%p end if;

%p end if;

%p end do:

%p return fcts ;

%p end proc:

%p A005179 := proc(n)

%p local Lexp,a,eList,cand,maxxrt ;

%p if n = 1 then

%p return 1;

%p end if;

%p Lexp := ofact(n,2) ;

%p a := 0 ;

%p for eList in Lexp do

%p maxxrt := ListTools[Reverse](eList) ;

%p cand := mul( ithprime(i)^ ( op(i,maxxrt)-1),i=1..nops(maxxrt)) ;

%p if a =0 or cand < a then

%p a := cand ;

%p end if;

%p end do:

%p a ;

%p end proc:

%p seq(A005179(n),n=1..40) ; # _R. J. Mathar_, Jun 06 2024

%t a = Table[ 0, {43} ]; Do[ d = Length[ Divisors[ n ]]; If[ d < 44 && a[[ d ]] == 0, a[[ d]] = n], {n, 1, 1099511627776} ]; a

%t (* Second program: *)

%t Function[s, Map[Lookup[s, #] &, Range[First@ Complement[Range@ Max@ #, #] - 1]] &@ Keys@ s]@ Map[First, KeySort@ PositionIndex@ Table[DivisorSigma[0, n], {n, 10^7}]] (* _Michael De Vlieger_, Dec 11 2016, Version 10 *)

%t mp[1, m_] := {{}}; mp[n_, 1] := {{}}; mp[n_?PrimeQ, m_] := If[m < n, {}, {{n}}]; mp[n_, m_] := Join @@ Table[Map[Prepend[#, d] &, mp[n/d, d]], {d, Select[Rest[Divisors[n]], # <= m &]}]; mp[n_] := mp[n, n]; Table[mulpar = mp[n] - 1; Min[Table[Product[Prime[s]^mulpar[[j, s]], {s, 1, Length[mulpar[[j]]]}], {j, 1, Length[mulpar]}]], {n, 1, 100}] (* _Vaclav Kotesovec_, Apr 04 2021 *)

%o (PARI) (prodR(n,maxf)=my(dfs=divisors(n),a=[],r); for(i=2,#dfs, if( dfs[i]<=maxf, if(dfs[i]==n, a=concat(a,[[n]]), r=prodR(n/dfs[i],min(dfs[i],maxf)); for(j=1,#r, a=concat(a,[concat(dfs[i],r[j])]))))); a); A005179(n)=my(pf=prodR(n,n),a=1,b); for(i=1,#pf, b=prod(j=1,length(pf[i]),prime(j)^(pf[i][j]-1)); if(b<a || i==1, a=b)); a

%o for(n=1,100, print1(A005179(n)", ")) \\ _R. J. Mathar_, May 26 2008, edited by _M. F. Hasler_, Oct 11 2014

%o (Haskell)

%o import Data.List (elemIndex)

%o import Data.Maybe (fromJust)

%o a005179 n = succ $ fromJust $ elemIndex n $ map a000005 [1..]

%o -- _Reinhard Zumkeller_, Apr 01 2011

%o (Python)

%o from math import prod

%o from sympy import isprime, divisors, prime

%o def A005179(n):

%o def mult_factors(n):

%o if isprime(n):

%o return [(n,)]

%o c = []

%o for d in divisors(n,generator=True):

%o if 1<d<n:

%o for a in mult_factors(n//d):

%o c.append(tuple(sorted((d,)+a)))

%o return list(set(c))

%o return min((prod(prime(i)**(j-1) for i,j in enumerate(reversed(d),1)) for d in mult_factors(n)),default=1) # _Chai Wah Wu_, Aug 17 2024

%Y Cf. A000005, A007416, A099316, A003586, A025487, A099311, A099313, A050376, A037992, A061799, A262981, A262983.

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_, David Singmaster

%E More terms from _David W. Wilson_