A003586 3-smooth numbers: numbers of the form 2^i*3^j with i, j >= 0.
1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 27, 32, 36, 48, 54, 64, 72, 81, 96, 108, 128, 144, 162, 192, 216, 243, 256, 288, 324, 384, 432, 486, 512, 576, 648, 729, 768, 864, 972, 1024, 1152, 1296, 1458, 1536, 1728, 1944, 2048, 2187, 2304, 2592, 2916, 3072, 3456, 3888
Offset: 1
References
- J.-M. De Koninck & A. Mercier, 1001 Problèmes en Théorie Classique des Nombres, Problème 654 pp. 85, 287-8, Ellipses Paris 2004.
- S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962, p. xxiv.
- R. Tijdeman, Some applications of Diophantine approximation, pp. 261-284 of Surveys in Number Theory (Urbana, May 21, 2000), ed. M. A. Bennett et al., Peters, 2003.
Links
- Lei Zhou, Table of n, a(n) for n = 1..10000 (first 501 terms from Franklin T. Adams-Watters)
- R. Blecksmith, M. McCallum and J. L. Selfridge, 3-smooth representations of integers, Amer. Math. Monthly, 105 (1998), 529-543.
- Thierry Bousch, La Tour de Stockmeyer, Séminaire Lotharingien de Combinatoire 77 (2017), Article B77d.
- Benoit Cloitre, a(n)/((1/sqrt(6))*exp(sqrt(2*log(2)*log(3)*n))) for 0
- Natalia da Silva, Serban Raianu, and Hector Salgado, Differences of Harmonic Numbers and the abc-Conjecture, arXiv:1708.00620 [math.NT], 2017.
- Emeric Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
- David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
- F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
- I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
- I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
- A. M. Hinz, S. Klavžar, U. Milutinović, and C. Petr, The Tower of Hanoi - Myths and Maths, Birkhäuser 2013. See page 252. Book's website
- H. W. Lenstra Jr., Harmonic Numbers
- H. W. Lenstra, Jr., Harmonic Numbers and the ABC-conjecture, Abstract of talk, May 30, 2001 [Annotated scanned copy]
- D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
- D. J. Mintz, 2,3 sequence as a binary mixture, Fib. Quarterly, Vol. 19, No 4, Oct 1981, pp. 351-360.
- I. Peterson, Medieval Harmony
- Raphael Schumacher, The Formulas for the Distribution of the 3-Smooth, 5-Smooth, 7-Smooth and all other Smooth Numbers, arXiv preprint arXiv:1608.06928 [math.NT], 2016.
- Eric Weisstein's World of Mathematics, Smooth Number
Crossrefs
Cf. A051037, A002473, A051038, A080197, A080681, A080682, A117221, A105420, A062051, A117222, A117220, A090184, A131096, A131097, A186711, A186712, A186771, A088468, A061987, A080683 (p-smooth numbers with other values of p), A025613 (a subsequence).
Cf. A191475 (successive values of i), A191476 (successive values of j), A022330 (indices of the pure terms 2^i), A022331 (indices of the pure terms 3^j). - N. J. A. Sloane, May 26 2024
Cf. A221363.
Programs
-
Haskell
import Data.Set (Set, singleton, insert, deleteFindMin) smooth :: Set Integer -> [Integer] smooth s = x : smooth (insert (3*x) $ insert (2*x) s') where (x, s') = deleteFindMin s a003586_list = smooth (singleton 1) a003586 n = a003586_list !! (n-1) -- Reinhard Zumkeller, Dec 16 2010
-
Magma
[n: n in [1..4000] | PrimeDivisors(n) subset [2,3]]; // Bruno Berselli, Sep 24 2012
-
Maple
A003586 := proc(n) option remember; if n = 1 then 1; else for a from procname(n-1)+1 do numtheory[factorset](a) minus {2,3} ; if % = {} then return a; end if; end do: end if; end proc: # R. J. Mathar, Feb 28 2011 with(numtheory): for i from 1 to 23328 do if(i/phi(i)=3)then print(i/6) fi od; # Gary Detlefs, Jun 28 2011
-
Mathematica
a[1] = 1; j = 1; k = 1; n = 100; For[k = 2, k <= n, k++, If[2*a[k - j] < 3^j, a[k] = 2*a[k - j], {a[k] = 3^j, j++}]]; Table[a[i], {i, 1, n}] (* Hai He (hai(AT)mathteach.net) and Gilbert Traub, Dec 28 2004 *) aa = {}; Do[If[EulerPhi[6 n] == 2 n, AppendTo[aa, n]], {n, 1, 1000}]; aa (* Artur Jasinski, Nov 05 2008 *) fQ[n_] := Union[ MemberQ[{1, 5}, # ] & /@ Union@ Mod[ Rest@ Divisors@ n, 6]] == {False}; fQ[1] = True; Select[ Range@ 4000, fQ] (* Robert G. Wilson v, Oct 26 2010 *) powerOfTwo = 12; Select[Nest[Union@Join[#, 2*#, 3*#] &, {1}, powerOfTwo-1], # < 2^powerOfTwo &] (* Robert G. Wilson v and T. D. Noe, Mar 03 2011 *) fQ[n_] := n == 3 EulerPhi@ n; Select[6 Range@ 4000, fQ]/6 (* Robert G. Wilson v, Jul 08 2011 *) mx = 4000; Sort@ Flatten@ Table[2^i*3^j, {i, 0, Log[2, mx]}, {j, 0, Log[3, mx/2^i]}] (* Robert G. Wilson v, Aug 17 2012 *) f[n_] := Block[{p2, p3 = 3^Range[0, Floor@ Log[3, n] + 1]}, p2 = 2^Floor[Log[2, n/p3] + 1]; Min[ Select[ p2*p3, IntegerQ]]]; NestList[f, 1, 54] (* Robert G. Wilson v, Aug 22 2012 *) Select[Range@4000, Last@Map[First, FactorInteger@#] <= 3 &] (* Vincenzo Librandi, Aug 25 2016 *) Select[Range[4000],Max[FactorInteger[#][[All,1]]]<4&] (* Harvey P. Dale, Jan 11 2017 *) -
PARI
test(n)=for(p=2,3, while(n%p==0, n/=p)); n==1; for(n=1,4000,if(test(n),print1(n",")))
-
PARI
list(lim)=my(v=List(),N);for(n=0,log(lim\1+.5)\log(3),N=3^n;while(N<=lim,listput(v,N);N<<=1));vecsort(Vec(v)) \\ Charles R Greathouse IV, Jun 28 2011
-
PARI
is_A003586(n)=n<5||vecmax(factor(n,5)[, 1])<5 \\ M. F. Hasler, Jan 16 2015
-
PARI
list(lim)=my(v=List(), N); for(n=0, logint(lim\=1,3), N=3^n; while(N<=lim, listput(v, N); N<<=1)); Set(v) \\ Charles R Greathouse IV, Jan 10 2018
-
Python
from itertools import count, takewhile def aupto(lim): pows2 = list(takewhile(lambda x: x -
Python
from sympy import integer_log def A003586(n): def bisection(f,kmin=0,kmax=1): while f(kmax) > kmax: kmax <<= 1 while kmax-kmin > 1: kmid = kmax+kmin>>1 if f(kmid) <= kmid: kmax = kmid else: kmin = kmid return kmax def f(x): return n+x-sum((x//3**i).bit_length() for i in range(integer_log(x,3)[0]+1)) return bisection(f,n,n) # Chai Wah Wu, Sep 15 2024
-
Python
# faster for initial segment of sequence import heapq from itertools import islice def A003586gen(): # generator of terms v, oldv, h, psmooth_primes, = 1, 0, [1], [2, 3] while True: v = heapq.heappop(h) if v != oldv: yield v oldv = v for p in psmooth_primes: heapq.heappush(h, v*p) print(list(islice(A003586gen(), 65))) # Michael S. Branicky, Sep 17 2024 (C++) // Returns A003586 <= threshold without approximations nor sorting #include
std::forward_list A003586(const int threshold) { std::forward_list sequence; auto start_it = sequence.before_begin(); for (int i = 1; i <= threshold; i *= 2) { for (int inc = 1; std::next(start_it) != sequence.end() && inc <= i; inc *= 3) ++start_it; auto it = start_it; for (int j = 1; i * j <= threshold; j *= 3) { sequence.emplace_after(it, i * j); for (int inc = 1; std::next(it) != sequence.end() && inc <= i; inc *= 2) ++it; } } return sequence; } // Eben Gino Lester, Apr 17 2025 -
Sage
def isA003586(n) : return not any(d != 2 and d != 3 for d in prime_divisors(n)) @CachedFunction def A003586(n) : if n == 1 : return 1 k = A003586(n-1) + 1 while not isA003586(k) : k += 1 return k [A003586(n) for n in (1..55)] # Peter Luschny, Jul 20 2012
Formula
An asymptotic formula for a(n) is roughly a(n) ~ 1/sqrt(6)*exp(sqrt(2*log(2)*log(3)*n)). - Benoit Cloitre, Nov 20 2001
A061987(n) = a(n + 1) - a(n), a(A084791(n)) = A084789(n), a(A084791(n) + 1) = A084790(n). - Reinhard Zumkeller, Jun 03 2003
Union of powers of 2 and 3 with n such that psi(n) = 2*n, where psi(n) = n*Product_(1 + 1/p) over all prime factors p of n = A001615(n). - Lekraj Beedassy, Sep 07 2004; corrected by Franklin T. Adams-Watters, Mar 19 2009
The characteristic function of this sequence is given by Sum_{n >= 1} x^a(n) = Sum_{n >= 1} moebius(6*n)*x^n/(1 - x^n). - Paul D. Hanna, Sep 18 2011
Comments