A105420 -id:A105420 - cp's OEIS frontend

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

Paul Zimmermann, Dec 11 1996

This sequence is easily confused with A033845, which gives numbers of the form 2^i*3^j with i, j >= 1. Don't simply say "numbers of the form 2^i*3^j", but specify which sequence you mean. - N. J. A. Sloane, May 26 2024
These numbers were once called "harmonic numbers", see Lenstra links. - N. J. A. Sloane, Jul 03 2015
Successive numbers k such that phi(6k) = 2k. - Artur Jasinski, Nov 05 2008
Where record values greater than 1 occur in A088468: A160519(n) = A088468(a(n)). - Reinhard Zumkeller, May 16 2009
Also numbers that are divisible by neither 6k - 1 nor 6k + 1, for all k > 0. - Robert G. Wilson v, Oct 26 2010
Also numbers m such that the rooted tree with Matula-Goebel number m has m antichains. The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T. The vertices of a rooted tree can be regarded as a partially ordered set, where u<=v holds for two vertices u and v if and only if u lies on the unique path between v and the root. An antichain is a nonempty set of mutually incomparable vertices. Example: m=4 is in the sequence because the corresponding rooted tree is \/=ARB (R is the root) having 4 antichains (A, R, B, AB). - Emeric Deutsch, Jan 30 2012
A204455(3*a(n)) = 3, and only for these numbers. - Wolfdieter Lang, Feb 04 2012
The number of terms less than or equal to n is Sum_{i=0..floor(log_2(n))} floor(log_3(n/2^i) + 1), or Sum_{i=0..floor(log_3(n))} floor(log_2(n/3^i) + 1), which requires fewer terms to compute. - Robert G. Wilson v, Aug 17 2012
Named 3-friables in French. - Michel Marcus, Jul 17 2013
In the 14th century Levi Ben Gerson proved that the only pairs of terms which differ by 1 are (1,2), (2,3), (3,4), and (8,9); see A235365, A235366, A236210. - Jonathan Sondow, Jan 20 2014
Range of values of A000005(n) (and also A181819(n)) for cubefree numbers n. - Matthew Vandermast, May 14 2014
A036561 is a permutation of this sequence. - L. Edson Jeffery, Sep 22 2014
Also the sorted union of A000244 and A007694. - Lei Zhou, Apr 19 2017
The sum of the reciprocals of the 3-smooth numbers is equal to 3. Brief proof: 1 + 1/2 + 1/3 + 1/4 + 1/6 + 1/8 + 1/9 + ... = (Sum_{k>=0} 1/2^k) * (Sum_{m>=0} 1/3^m) = (1/(1-1/2)) * (1/(1-1/3)) = (2/(2-1)) * (3/(3-1)) = 3. - Bernard Schott, Feb 19 2019
Also those integers k for which, for every prime p > 3, p^(2k) - 1 == 0 (mod 24k). - Federico Provvedi, May 23 2022
For n>1, the exponents’ parity {parity(i), parity(j)} of one out of four consecutive terms is {odd, odd}. Therefore, for n>1, at least one out of every four consecutive terms is a Zumkeller number (A083207). If for the term whose parity is {even, odd}, even also means nonzero, then this term is also a Zumkeller number (as is the case with the last of the four consecutive terms 1296, 1458, 1536, 1728). - Ivan N. Ianakiev, Jul 10 2022
Except the initial terms 2, 3, 4, 8, 9 and 16, these are numbers k such that k^6 divides 6^k. Except the initial terms 2, 3, 4, 6, 8, 9, 16, 18 and 27, these are numbers k such that k^12 divides 12^k. - Mohammed Yaseen, Jul 21 2022
In music theory, a comma is a ratio, close to 1 (typically less than 1.04), between two natural numbers divisible by only small primes (typically single digit). In this sequence, a(131) / a(130) = 531441 / 524288 ~ 1.013643 is the Pythagorean comma (A221363), the difference between 12 perfect fifths and 7 octaves. - Hal M. Switkay, Mar 23 2025

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.

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

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. also A235365, A235366, A236210, A036561.
Cf. also A000244, A007694. - Lei Zhou, Apr 19 2017
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.

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

[n: n in [1..4000] | PrimeDivisors(n) subset [2,3]]; // Bruno Berselli, Sep 24 2012

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

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 *)

test(n)=for(p=2,3, while(n%p==0, n/=p)); n==1;
for(n=1,4000,if(test(n),print1(n",")))

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

is_A003586(n)=n<5||vecmax(factor(n,5)[, 1])<5 \\ M. F. Hasler, Jan 16 2015

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

from itertools import count, takewhile
def aupto(lim):
    pows2 = list(takewhile(lambda x: xMichael S. Branicky, Jul 08 2022

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

# 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

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

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
a(n) = 2^A022328(n)*3^A022329(n). - N. J. A. Sloane, 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
a(n) = A007694(n+1)/2. - Lei Zhou, Apr 19 2017

Deleted claim that this sequence is union of 2^n (A000079) and 3^n (A000244) sequences -- this does not include the terms which are not pure powers. - Walter Roscello (wroscello(AT)comcast.net), Nov 16 2008

A018819 Binary partition function: number of partitions of n into powers of 2.

Original entry on oeis.org

1, 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20, 20, 26, 26, 36, 36, 46, 46, 60, 60, 74, 74, 94, 94, 114, 114, 140, 140, 166, 166, 202, 202, 238, 238, 284, 284, 330, 330, 390, 390, 450, 450, 524, 524, 598, 598, 692, 692, 786, 786, 900, 900, 1014, 1014, 1154, 1154, 1294, 1294

Offset: 0

David W. Wilson, N. J. A. Sloane and J. H. Conway

First differences of A000123; also A000123 with terms repeated. See the relevant proof that follows the first formula below.
Among these partitions there is exactly one partition with all distinct terms, as every number can be expressed as the sum of the distinct powers of 2.
Euler transform of A036987 with offset 1.
a(n) is the number of "non-squashing" partitions of n, that is, partitions n = p_1 + p_2 + ... + p_k with 1 <= p_1 <= p_2 <= ... <= p_k and p_1 + p_2 + ... + p_i <= p_{i+1} for all 1 <= i < k. - N. J. A. Sloane, Nov 30 2003
Normally the OEIS does not include sequences like this where every term is repeated, but an exception was made for this one because of its importance. The unrepeated sequence A000123 is the main entry.
Number of different partial sums from 1 + [1, *2] + [1, *2] + ..., where [1, *2] means we can either add 1 or multiply by 2. E.g., a(6) = 6 because we have 6 = 1 + 1 + 1 + 1 + 1 + 1 = (1+1) * 2 + 1 + 1 = 1 * 2 * 2 + 1 + 1 = (1+1+1) * 2 = 1 * 2 + 1 + 1 + 1 + 1 = (1*2+1) * 2 where the connection is defined via expanding each bracket; e.g., this is 6 = 1 + 1 + 1 + 1 + 1 + 1 = 2 + 2 + 1 + 1 = 4 + 1 + 1 = 2 + 2 + 2 = 2 + 1 + 1 + 1 + 1 = 4 + 2. - Jon Perry, Jan 01 2004
Number of partitions p of n such that the number of compositions generated by p is odd. For proof see the Alekseyev and Adams-Watters link. - Vladeta Jovovic, Aug 06 2007
Differs from A008645 first at a(64). - R. J. Mathar, May 28 2008
Appears to be row sums of A155077. - Mats Granvik, Jan 19 2009
Number of partitions (p_1, p_2, ..., p_k) of n, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i >= p_{i+1} + ... + p_k. - John MCKAY (mckay(AT)encs.concordia.ca), Mar 06 2009 (these are the "non-squashing" partitions as nonincreasing lists).
Equals rightmost diagonal of triangle of A168261. Starting with offset 1 = eigensequence of triangle A115361 and row sums of triangle A168261. - Gary W. Adamson, Nov 21 2009
Equals convolution square root of A171238: (1, 2, 5, 8, 16, 24, 40, 56, 88, ...). - Gary W. Adamson, Dec 05 2009
Let B = the n-th convolution power of the sequence and C = the aerated variant of B. It appears that B/C = the binomial sequence beginning (1, n, ...). Example: Third convolution power of the sequence is (1, 3, 9, 19, 42, 78, 146, ...), with C = (1, 0, 3, 0, 9, 0, 19, ...). Then B/C = (1, 3, 6, 10, 15, 21, ...). - Gary W. Adamson, Aug 15 2016
From Gary W. Adamson, Sep 08 2016: (Start)
The limit of the matrix power M^k as n-->inf results in a single column vector equal to the sequence, where M is the following production matrix:
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 0, ...
  1, 1, 1, 1, 1, ...
  ... (End)
a(n) is the number of "non-borrowing" partitions of n, meaning binary subtraction of a smaller part from a larger part will never require place-value borrowing. - David V. Feldman, Jan 29 2020
From Gus Wiseman, May 25 2024: (Start)
Also the number of multisets of positive integers whose binary rank is n, where the binary rank of a multiset m is given by Sum_i 2^(m_i-1). For example, the a(1) = 1 through a(8) = 10 multisets are:
  {1}  {2}   {12}   {3}     {13}     {23}      {123}      {4}
       {11}  {111}  {22}    {122}    {113}     {1113}     {33}
                    {112}   {1112}   {222}     {1222}     {223}
                    {1111}  {11111}  {1122}    {11122}    {1123}
                                     {11112}   {111112}   {2222}
                                     {111111}  {1111111}  {11113}
                                                          {11222}
                                                          {111122}
                                                          {1111112}
                                                          {11111111}
(End)

			G.f. = 1 + x + 2*x^2 + 2*x^3 + 4*x^4 + 4*x^5 + 6*x^6 + 6*x^7 + 10*x^8 + ...
a(4) = 4: the partitions are 4, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.
a(7) = 6: the partitions are 4 + 2 + 1, 4 + 1 + 1 + 1, 2 + 2 + 2 + 1, 2 + 2 + 1 + 1 + 1, 2 + 1 + 1 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1 + 1.
From _Joerg Arndt_, Dec 17 2012: (Start)
The a(10) = 14 binary partitions of 10 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 ]
[ 6]  [ 2 2 2 2 2 ]
[ 7]  [ 4 1 1 1 1 1 1 ]
[ 8]  [ 4 2 1 1 1 1 ]
[ 9]  [ 4 2 2 1 1 ]
[10]  [ 4 2 2 2 ]
[11]  [ 4 4 1 1 ]
[12]  [ 4 4 2 ]
[13]  [ 8 1 1 ]
[14]  [ 8 2 ]
The a(11) = 14 binary partitions of 11 are obtained by appending 1 to each partition in the list.
The a(10) = 14 non-squashing partitions of 10 are (in lexicographic order)
[ 1]  [ 6 3 1 1 ]
[ 2]  [ 6 3 2 ]
[ 3]  [ 6 4 1 ]
[ 4]  [ 6 5 ]
[ 5]  [ 7 2 1 1 ]
[ 6]  [ 7 2 2 ]
[ 7]  [ 7 3 1 ]
[ 8]  [ 7 4 ]
[ 9]  [ 8 2 1 ]
[10]  [ 8 3 ]
[11]  [ 9 1 1 ]
[12]  [ 9 2 ]
[13]  [ 10 1 ]
[14]  [ 11 ]
The a(11) = 14 non-squashing partitions of 11 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _David V. Feldman_, Jan 29 2020: (Start)
The a(10) = 14 non-borrowing partitions of 10 are (in lexicographic order)
[ 1] [1 1 1 1 1 1 1 1 1 1]
[ 2] [2 2 2 2 2]
[ 3] [3 1 1 1 1 1 1 1]
[ 4] [3 3 1 1 1 1]
[ 5] [3 3 2 2]
[ 6] [3 3 3 1]
[ 7] [5 1 1 1 1 1]
[ 8] [5 5]
[ 9] [6 2 2]
[10] [6 4]
[11] [7 1 1 1]
[12] [7 3]
[13] [9 1]
[14] [10]
The a(11) = 14 non-borrowing partitions of 11 are obtained either by adding 1 to the first even part in each partition (if any) or else appending a 1 after the last part.
(End)
For example, the five partitions of 4, written in nonincreasing order, are [1, 1, 1, 1], [2, 1, 1], [2, 2], [3, 1], [4]. The last four satisfy the condition, and a(4) = 4. The Maple program below verifies this for small values of n.

T. D. Noe, Table of n, a(n) for n = 0..1000
Max Alekseyev and Franklin T. Adams-Watters, Two proofs of an observation of Vladeta Jovovic
Giedrius Alkauskas, Generalization of the Rodseth-Gupta theorem on binary partitions, Lithuanian Math. J., 43 (2) (2003), 103-110.
Giedrius Alkauskas, Congruence Properties of the Function that Counts Compositions into Powers of 2 , J. Int. Seq. 13 (2010), 10.5.3.
Joerg Arndt, Matters Computational (The Fxtbook), section 38.1, p.729.
Scott M. Bailey and Donald M. Larson, The A(1)-module structure of the homology of Brown-Gitler spectra, arXiv:2107.01316 [math.AT], 2021.
Valentin P. Bakoev, Algorithmic approach to counting of certain types m-ary partitions, Discrete Mathematics, 275 (2004) pp. 17-41.
Philippe Biane, Laver tables and combinatorics, arXiv:1810.00548 [math.CO], 2018. Mentions this sequence.
Peter J. Cameron, Firdous Ee Jannat, Rajat Kanti Nath, and Reza Sharafdini, A survey on conjugacy class graphs of groups, arXiv:2403.09423 [math.GR], 2024.
Karl Dilcher and Larry Ericksen, Polynomial Analogues of Restricted b-ary Partition Functions, J. Int. Seq., Vol. 22 (2019), Article 19.3.2.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 48, 581.
Maciej Gawron, Piotr Miska and Maciej Ulas, Arithmetic properties of coefficients of power series expansion of Prod_{n>=0} (1-x^(2^n))^t, arXiv:1703.01955 [math.NT], 2017.
Michael D. Hirschhorn and James A. Sellers, A different view of m-ary partitions, Australasian J. Combin., vol.30 (2004), 193-196.
Jonathan Jordan and Richard Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. doi: 10.4236/am.2010.15045. - From _N. J. A. Sloane_, Feb 03 2013
Yasuyuki Kachi and Pavlos Tzermias, On the m-ary partition numbers, Algebra and Discrete Mathematics, Volume 19 (2015). Number 1, pp. 67-76.
Matjaž Konvalinka and Igor Pak, Cayley compositions, partitions, polytopes, and geometric bijections, Journal of Combinatorial Theory, Series A, Volume 123, Issue 1, April 2014, Pages 86-91; see also DOI link. - From _N. J. A. Sloane_, Dec 22 2012
Apisit Pakapongpun and Thomas Ward, Functorial Orbit counting, J. Int. Seq., 12 (2009) 09.2.4, example 25.
Øystein J. Rodseth and James A. Sellers, On a Restricted m-Non-Squashing Partition Function, Journal of Integer Sequences, Vol. 8 (2005), Article 05.5.4.
David Ruelle, Dynamical zeta functions and transfer operators, Notices Amer. Math. Soc., 49 (No. 8, 2002), 887-895; see p. 888.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, arXiv:math/0312418 [math.CO], 2003.
N. J. A. Sloane and James A. Sellers, On non-squashing partitions, Discrete Math., 294 (2005), 259-274.

A000123 is the main entry for the binary partition function and gives many more properties and references.
Cf. A115625 (labeled binary partitions), A115626 (labeled non-squashing partitions).
Convolution inverse of A106400.
Cf. A023893, A062051, A105420, A131995, A040039, A018819, A088567, A089054, A115361, A168261, A171238, A179051, A008619.
Multiplicity of n in A048675, for distinct prime indices A087207.
Row lengths of A277905.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A372890 adds up binary ranks of integer partitions.
Binary indices: A000120, A001511, A029931, A048793, A070939, A272020.
Cf. A005940, A019565, A056239, A158704, A158705, A231204, A277319, A372688.

a018819 n = a018819_list !! n
a018819_list = 1 : f (tail a008619_list) where
   f (x:xs) = (sum $ take x a018819_list) : f xs
-- Reinhard Zumkeller, Jan 28 2012

import Data.List (intersperse)
a018819 = (a018819_list !!)
a018819_list = 1 : 1 : (<*>) (zipWith (+)) (intersperse 0) (tail a018819_list)
-- Johan Wiltink, Nov 08 2018

with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
# while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od; # John McKay

max = 59; a[0] = a[1] = 1; a[n_?OddQ] := a[n] = a[n-1]; a[n_?EvenQ] := a[n] = a[n-1] + a[n/2]; Table[a[n], {n, 0, max}]
(* or *) CoefficientList[Series[1/Product[(1-x^(2^j)), {j, 0, Log[2, max] // Ceiling}], {x, 0, max}], x] (* Jean-François Alcover, May 17 2011, updated Feb 17 2014 *)
a[ n_] := If[n<1, Boole[n==0], a[n] = a[n-1] + If[EvenQ@n, a[Quotient[n,2]], 0]]; (* Michael Somos, May 04 2022 *)
Table[Count[IntegerPartitions[n],?(AllTrue[Log2[#],IntegerQ]&)],{n,0,60}] (* _Harvey P. Dale, Jun 20 2024 *)

{ n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*2)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } /* Jon Perry */

{a(n) = my(A, m); if( n<1, n==0, m=1; A = 1 + O(x); while(m<=n, m*=2; A = subst(A, x, x^2) / (1 - x)); polcoeff(A, n))}; /* Michael Somos, Aug 25 2003 */

{a(n) = if( n<1, n==0, if( n%2, a(n-1), a(n/2)+a(n-1)))}; /* Michael Somos, Aug 25 2003 */

from functools import lru_cache
@lru_cache(maxsize=None)
def A018819(n): return 1 if n == 0 else A018819(n-1) + (0 if n % 2 else A018819(n//2)) # Chai Wah Wu, Jan 18 2022

a(2m+1) = a(2m), a(2m) = a(2m-1) + a(m). Proof: If n is odd there is a part of size 1; removing it gives a partition of n - 1. If n is even either there is a part of size 1, whose removal gives a partition of n - 1, or else all parts have even sizes and dividing each part by 2 gives a partition of n/2.
G.f.: 1 / Product_{j>=0} (1-x^(2^j)).
a(n) = (1/n)*Sum_{k = 1..n} A038712(k)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002
a(2*n) = a(2*n + 1) = A000123(n). - Michael Somos, Aug 25 2003
a(n) = 1 if n = 0, Sum_{j = 0..floor(n/2)} a(j) if n > 0. - David W. Wilson, Aug 16 2007
G.f. A(x) satisfies A(x^2) = (1-x) * A(x). - Michael Somos, Aug 25 2003
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = u^2*w - 2*u*v^2 + v^3. - Michael Somos, Apr 10 2005
G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6 * u1^3 - 3*u3*u2*u1^2 + 3*u3*u2^2*u1 - u3*u2^3. - Michael Somos, Oct 15 2006
G.f.: 1/( Sum_{n >= 0} x^evil(n) - x^odious(n) ), where evil(n) = A001969(n) and odious(n) = A000069(n). - Paul D. Hanna, Jan 23 2012
Let A(x) by the g.f. and B(x) = A(x^k), then 0 = B*((1-A)^k - (-A)^k) + (-A)^k, see fxtbook link. - Joerg Arndt, Dec 17 2012
G.f.: Product_{n>=0} (1+x^(2^n))^(n+1), see the fxtbook link. - Joerg Arndt, Feb 28 2014
G.f.: 1 + Sum_{i>=0} x^(2^i) / Product_{j=0..i} (1 - x^(2^j)). - Ilya Gutkovskiy, May 07 2017

A106244 Number of partitions into distinct prime powers.

Original entry on oeis.org

1, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 8, 10, 11, 13, 14, 17, 19, 21, 24, 27, 30, 33, 37, 41, 46, 50, 56, 62, 68, 75, 82, 91, 99, 108, 118, 129, 141, 152, 166, 180, 196, 211, 229, 248, 267, 288, 310, 335, 360, 387, 415, 447, 479, 513, 549, 589, 630, 672, 719, 768, 820, 873, 930

Offset: 0

Reinhard Zumkeller, Apr 26 2005

nonn

A054685(n) < a(n) < A023893(n) for n>2.

			a(10) = #{3^2+1,2^3+2,7+3,7+2+1,5+2^2+1,5+3+2,2^2+3+2+1} = 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000 (first 1000 terms from T. D. Noe)

Cf. A000586, A000607, A000961.
Cf. A062051, A105420, A131996.
Cf. A023893, A051613, A054685.

import Data.MemoCombinators (memo2, integral)
a106244 n = a106244_list !! n
a106244_list = map (p' 1) [0..] where
   p' = memo2 integral integral p
   p _ 0 = 1
   p k m = if m < pp then 0 else p' (k + 1) (m - pp) + p' (k + 1) m
           where pp = a000961 k
-- Reinhard Zumkeller, Nov 24 2015

g:=(1+x)*(product(product(1+x^(ithprime(k)^j),j=1..5),k=1..20)): gser:=series(g,x=0,68): seq(coeff(gser,x,n),n=1..63); # Emeric Deutsch, Aug 27 2007

m = 64; gf = (1+x)*Product[1+x^(Prime[k]^j), {j, 1, 5}, {k, 1, 18}] + O[x]^m; CoefficientList[gf, x] (* Jean-François Alcover, Mar 02 2019, from Maple *)

lista(m) = {x = t + t*O(t^m); gf = (1+x)*prod(k=1, m, if (isprimepower(k),(1+x^k), 1)); for (n=0, m, print1(polcoeff(gf, n, t), ", "));} \\ Michel Marcus, Mar 02 2019

a(n) = A054685(n-1)+A054685(n). - Vladeta Jovovic, Apr 28 2005

G.f.: (1+x)*Product(Product(1+x^(p(k)^j), j=1..infinity),k=1..infinity), where p(k) is the k-th prime (offset 0). - Emeric Deutsch, Aug 27 2007

Offset corrected and a(0)=1 added by Reinhard Zumkeller, Nov 24 2015

A062051 Number of partitions of n into powers of 3.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 3, 3, 5, 5, 5, 7, 7, 7, 9, 9, 9, 12, 12, 12, 15, 15, 15, 18, 18, 18, 23, 23, 23, 28, 28, 28, 33, 33, 33, 40, 40, 40, 47, 47, 47, 54, 54, 54, 63, 63, 63, 72, 72, 72, 81, 81, 81, 93, 93, 93, 105, 105, 105, 117, 117, 117, 132, 132, 132, 147, 147, 147, 162

Offset: 0

Amarnath Murthy, Jun 06 2001

nonn

Number of different partial sums of 1+[1,*3]+[1,*3]+..., where [1,*3] means we can either add 1 or multiply by 3. E.g., a(6)=3 because we have 6=1+1+1+1+1+1=(1+1)*3=1*3+1+1+1. - Jon Perry, Jan 01 2004
Also number of partitions of n into distinct 3-smooth parts. E.g., a(10) = #{9+1, 8+2, 6+4, 6+3+1, 4+3+2+1} = #{9+1, 3+3+3+1, 3+3+1+1+1+1, 3+1+1+1+1+1+1+1, 1+1+1+1+1+1+1+1+1+1} = 5. - Reinhard Zumkeller, Apr 07 2005
Starts to differ from A008650 at a(81). - R. J. Mathar, Jul 31 2010
If m=ceiling(log_3(2k)) and n=(3^m+1)/2-k for k in the range (3^(m-1)+1)/2+(3^(m-2))<=k<=(3^m-1)/2, this sequence gives the number of "feasible" partitions described in the sequence A254296. For instance, the terms starting at 121st term of A254296 backwards to 68th term of A254296 provide the first 54 terms of this sequence. - Md. Towhidul Islam, Mar 01 2015
From Gary W. Adamson, Sep 03 2016: (Start)
Let M =
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 0, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 0, 0, 0, ...
  1, 1, 1, 0, 0, ...
  1, 1, 1, 0, 0, ...
  ..., where the leftmost column is all 1's, and all other columns are 1's shifted down thrice. Lim_{k=1..inf} M^k has a single nonzero column, which gives the sequence. (End)

			a(4) = 2 and the partitions are 3+1, 1+1+1+1;
a(9) = 5 and the partitions are 9; 3+3+3; 3+3+1+1+1; 3+1+1+1+1+1+1; 1+1+1+1+1+1+1+1+1.

Seiichi Manyama, Table of n, a(n) for n = 0..1000
Vassil Dimitrov, Laurent Imbert, and Andrew Zakaluzny, Multiplication by a Constant is Sublinear, 18th IEEE Symposium on Computer Arithmetic (2007). See Theorem 1.
Md Towhidul Islam and Md Shahidul Islam, Number of Partitions of an n-kilogram Stone into Minimum Number of Weights to Weigh All Integral Weights from 1 to n kg(s) on a Two-pan Balance, arXiv:1502.07730 [math.CO], 2015.
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228.
M. Latapy, Partitions of an integer into powers, DMTCS Proceedings AA (DM-CCG), 2001, 215-228. [Cached copy, with permission]

A005704 with terms repeated 3 times.

Cf. A000123, A018819, A000009, A003586, A105420, A039966, A023893, A105420, A106244, A131995, A179051, A254296.

nn=70;a=Product[1/(1-x^(3^i)),{i,0,4}];CoefficientList[Series[a,{x,0,nn}],x] (* Geoffrey Critzer, Oct 30 2012 *)

{ n=15; v=vector(n); for (i=1,n,v[i]=vector(2^(i-1))); v[1][1]=1; for (i=2,n, k=length(v[i-1]); for (j=1,k, v[i][j]=v[i-1][j]+1; v[i][j+k]=v[i-1][j]*3)); c=vector(n); for (i=1,n, for (j=1,2^(i-1), if (v[i][j]<=n, c[v[i][j]]++))); c } \\ Jon Perry

from functools import lru_cache
@lru_cache(maxsize=None)
def A062051(n): return A062051(n-1)+(0 if n%3 else A062051(n//3)) if n>2 else 1 # Chai Wah Wu, Sep 21 2022

a(n) = A005704([n/3]).
G.f.: Product_{k>=0} 1/(1-x^(3^k)). - R. J. Mathar, Jul 31 2010
If m = ceiling(log_3(2k)), define n = (3^m + 1)/2 - k for k in the range (3^(m-1)+1)/2 + (3^(m-2)) <= k <= (3^m-1)/2. Then, a(n) = Sum_{s=ceiling((k-1)/3)..(3^(m-1)-1)/2} a(s). This gives the first 2(3^(m-1))/3 terms. - Md. Towhidul Islam, Mar 01 2015
G.f.: 1 + Sum_{i>=0} x^(3^i) / Product_{j=0..i} (1 - x^(3^j)). - Ilya Gutkovskiy, May 07 2017

More terms from Larry Reeves (larryr(AT)acm.org), Jun 11 2001

cp's OEIS Frontend

A003586 3-smooth numbers: numbers of the form 2^i*3^j with i, j >= 0.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Python

Sage

Formula

Extensions

A018819 Binary partition function: number of partitions of n into powers of 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

A106244 Number of partitions into distinct prime powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A062051 Number of partitions of n into powers of 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

Extensions

A117222 Number of partitions of 3-smooth numbers into 3-smooth numbers.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI