login
Least number with exactly n odd divisors.
59

%I #84 Aug 17 2024 22:29:03

%S 1,3,9,15,81,45,729,105,225,405,59049,315,531441,3645,2025,945,

%T 43046721,1575,387420489,2835,18225,295245,31381059609,3465,50625,

%U 2657205,11025,25515,22876792454961,14175,205891132094649,10395,1476225,215233605

%N Least number with exactly n odd divisors.

%C Also least odd number with exactly n divisors. - _Lekraj Beedassy_, Aug 30 2006

%C a(2n-1) = {1, 9, 81, 729, 225, 59049, ...} are the squares. A122842(n) = sqrt(a(2n-1)) = {1, 3, 9, 27, 15, 243, 729, 45, 6561, 19683, 135, 177147, 225, 105, 4782969, 14348907, 1215, ...}. - _Alexander Adamchuk_, Sep 13 2006

%C Also the least number k such that there are n partitions of k whose elements are consecutive integers. I.e., 1=1, 3=1+2=3, 9=2+3+4=4+5=9, 15=1+2+3+4+5=4+5+6=7+8=15, etc. - _Robert G. Wilson v_, Jun 02 2007

%C The politeness of an integer, A069283(n), is defined to be the number of its nontrivial runsum representations, and the sequence 3, 9, 15, 81, 45, 729, 105, ... represents the least integers to have a politeness of 1, 2, 3, 4, ... This is also the sequence of smallest integers with n+1 odd divisors and so apart from the leading 1, is precisely this sequence. - _Ant King_, Sep 23 2009

%C a(n) is also the least number k with the property that the symmetric representation of sigma(k) has n subparts. - _Omar E. Pol_, Dec 31 2016

%H Don Reble, <a href="/A038547/b038547.txt">Table of n, a(n) for n = 1..2000</a>

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

%F a(p) = 3^(p-1) for primes p. - _Zak Seidov_, Apr 18 2006

%F a(n) = A119265(n,n). - _Reinhard Zumkeller_, May 11 2006

%F It was suggested by _Alexander Adamchuk_ that for all n >= 1, we have a(3^(n-1)) = (p(n)#/2)^2 = (A002110(n)/2)^2 = A070826(n)^2. But this is false! E.g., (p(n)#/2)^2 = 3^2 * 5^2 * 7^2 * ... * 23^2 * 29^2 does indeed have 3^9 odd factors, but it is greater than 3^8 * 5^2 * 7^2 * ... * 23^2 which has 9*3*3*3*3*3*3*3 = 9*3^7 = 3^9 odd factors. - _Richard Sabey_, Oct 06 2007

%F a(A053640(m)) = a(A000005(A053624(m))) = A053624(m). - _Rick L. Shepherd_, Apr 20 2008

%F a(p^k) = Product_{i=1..k} prime(i+1)^(p-1), p prime and k >= 0, only when p_(k+1) < 3^p. - _Hartmut F. W. Hoft_, Nov 03 2022

%e a(2^3) = 105 = 3*5 while a(2^4) = 945 = 3^3 * 5 * 7. There are 5 partition lists for the exponents of numbers with 16 odd divisors; they are {1, 1, 1, 1}, {3, 1, 1}, {3, 3}, {7, 1}, and {15} that result in the 5 numbers 1155, 945, 3375, 10935, and 14348907. Number a(3^8) = a(6561) = 3^2 * 5^2 * ... * 19^2 * 23^2 = 12442607161209225 while a(3^9) = a(19683) = 3^8 * 5^2 * ... * 19^2 * 23^2 = 9070660620521525025. The numbers a(5^52) = 3^4 * 5^4 * 7^4 * ... and a(5^53) = 3^24 * 5^4 * 7^4 * ... have 393 and 402 digits, respectively. - _Hartmut F. W. Hoft_, Nov 03 2022

%t Table[Select[Range[1,532000,2],DivisorSigma[0,#]==k+1 &,1],{k,0,15}]//Flatten (* _Ant King_, Nov 28 2010 *)

%t 2#-1&/@With[{ds=DivisorSigma[0,Range[1,600000,2]]},Table[Position[ds,n,1,1],{n,16}]]//Flatten (* The program is not suitable for generating terms beyond a(16) *) (* _Harvey P. Dale_, Jun 06 2017 *)

%t (* direct computation of A038547(n) *)

%t (* Function by _Vaclav Kotesovec_in A005179, Apr 04 2021, modified for odd divisors *)

%t mp[1, m_] := {{}}; mp[n_, 1] := {{}}; mp[n_?PrimeQ, m_] := If[m<n, {}, {{n}}];

%t mp[n_, m_] := Join@@Table[Map[Prepend[#, d]&, mp[n/d, d]], {d, Select[Rest[Divisors[n]], #<=m&]}];

%t mp[n_]:=mp[n,n];

%t a038547[bound_] := Module[{mulpar}, Table[mulpar=mp[n]-1; Min[Table[Product[Prime[s+1]^mulpar[[j, s]], {s, 1, Length[mulpar[[j]]]}], {j, 1, Length[mulpar]}]], {n, 1, bound}]]

%t a038547[34] (* _Hartmut F. W. Hoft_, Mar 05 2023 *)

%o (PARI) for(nd=1,15,forstep(k=1,10^66,2,if(nd==numdiv(k),print1(k,", ");break())))

%o (Haskell)

%o import Data.List (find)

%o import Data.Maybe (fromJust)

%o a038547 n = fromJust $ find ((== n) . length . divisors) [1,3..]

%o where divisors m = filter ((== 0) . mod m) [1..m]

%o -- _Reinhard Zumkeller_, Feb 24 2011

%o (Python)

%o from math import prod

%o from sympy import isprime, divisors, prime

%o def A038547(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),2)) for d in mult_factors(n)),default=1) # _Chai Wah Wu_, Aug 17 2024

%Y A122842 = sqrt( a(2n-1) ).

%Y Cf. A001227, A005179, A002110, A070826, A000005, A053640, A053624, A237593, A279387.

%Y Row 1 of A266531. - _Omar E. Pol_, Dec 31 2016

%Y Cf. A006093, A076274, A080577.

%K nonn,nice

%O 1,2

%A _Tom Verhoeff_

%E Corrected by _Ron Knott_, Feb 22 2001

%E a(30) from _Zak Seidov_, Apr 18 2006

%E a(32)-a(34) from _Lekraj Beedassy_, Aug 30 2006