A023893 -id:A023893 - cp's OEIS frontend

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

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

A050361 Number of factorizations into distinct prime powers greater than 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 4, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1

Offset: 1

Christian G. Bower, Oct 15 1999

a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3*3 and 375 = 3*5^3 both have prime signature (3,1).

The number of unordered factorizations of n into 1 and exponentially odd prime powers, i.e., p^e where p is a prime and e is odd (A246551). - Amiram Eldar, Jun 12 2025

			From _Gus Wiseman_, Jul 30 2022: (Start)
The A000688(216) = 9 factorizations of 216 into prime powers are:
  (2*2*2*3*3*3)
  (2*2*2*3*9)
  (2*2*2*27)
  (2*3*3*3*4)
  (2*3*4*9)
  (2*4*27)
  (3*3*3*8)
  (3*8*9)
  (8*27)
Of these, the a(216) = 4 strict cases are:
  (2*3*4*9)
  (2*4*27)
  (3*8*9)
  (8*27)
(End)

Antti Karttunen, Table of n, a(n) for n = 1..100000 (first 10000 terms from Reinhard Zumkeller)
Index entries for sequences computed from exponents in factorization of n.

Cf. A000009, A050360, A050362, A050363, A050364, A101296, A246551.
Cf. A124010.
This is the strict case of A000688.
Positions of 1's are A004709, complement A046099.
The case of primes (instead of prime-powers) is A008966, non-strict A000012.
The non-strict additive version allowing 1's A023893, ranked by A302492.
The non-strict additive version is A023894, ranked by A355743.
The additive version (partitions) is A054685, ranked by A356065.
The additive version allowing 1's is A106244, ranked by A302496.
A001222 counts prime-power divisors.
A005117 lists all squarefree numbers.
A034699 gives maximal prime-power divisor.
A246655 lists all prime-powers (A000961 includes 1), towers A164336.
A296131 counts twice-factorizations of type PQR, non-strict A295935.
Cf. A001970, A002110, A025487, A055887, A063834, A076610, A085970, A279786, A302590, A302601, A354911, A355742.

a050361 = product . map a000009 . a124010_row
-- Reinhard Zumkeller, Aug 28 2014

A050361 := proc(n)
    local a,f;
    if n = 1 then
        1;
    else
        a := 1 ;
        for f in ifactors(n)[2] do
            a := a*A000009(op(2,f)) ;
        end do:
    end if;
end proc: # R. J. Mathar, May 25 2017

Table[Times @@ PartitionsQ[Last /@ FactorInteger[n]], {n, 99}] (* Arkadiusz Wesolowski, Feb 27 2017 *)

A000009(n,k=(n-!(n%2))) = if(!n,1,my(s=0); while(k >= 1, if(k<=n, s += A000009(n-k,k)); k -= 2); (s));
A050361(n) = factorback(apply(A000009,factor(n)[,2])); \\ Antti Karttunen, Nov 17 2019

Dirichlet g.f.: Product_{n is a prime power >1}(1 + 1/n^s).
Multiplicative with a(p^e) = A000009(e).
a(A002110(k))=1.
a(n) = A050362(A101296(n)). - R. J. Mathar, May 26 2017
Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = Product_{p prime} f(1/p) = 1.26020571070524171076..., where f(x) = (1-x) * Product_{k>=1} (1 + x^k). - Amiram Eldar, Oct 03 2023

A023894 Number of partitions of n into prime power parts (1 excluded).

Original entry on oeis.org

1, 0, 1, 1, 2, 2, 3, 4, 6, 7, 9, 12, 15, 19, 23, 29, 37, 44, 54, 66, 80, 96, 115, 138, 165, 196, 231, 275, 322, 380, 443, 520, 607, 705, 819, 950, 1099, 1268, 1461, 1681, 1932, 2214, 2533, 2898, 3305, 3768, 4285, 4872, 5530, 6267, 7094, 8022, 9060

Offset: 0

Olivier Gérard

nonn

			From _Gus Wiseman_, Jul 28 2022: (Start)
The a(0) = 1 through a(9) = 7 partitions:
  ()  .  (2)  (3)  (4)   (5)   (33)   (7)    (8)     (9)
                   (22)  (32)  (42)   (43)   (44)    (54)
                               (222)  (52)   (53)    (72)
                                      (322)  (332)   (333)
                                             (422)   (432)
                                             (2222)  (522)
                                                     (3222)
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000
E. Grosswald, Partitions into prime powers

The multiplicative version (factorizations) is A000688, coprime A354911.
Allowing 1's gives A023893, strict A106244, ranked by A302492.
The strict version is A054685.
The version for just primes is ranked by A076610, squarefree A356065.
Twice-partitions of this type are counted by A279784, factorizations A295935.
These partitions are ranked by A355743.
A000041 counts partitions, strict A000009.
A001222 counts prime-power divisors.
A072233 counts partitions by sum and length.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
Cf. A001970, A055887, A063834, A085970.

Table[Length[Select[IntegerPartitions[n],And@@PrimePowerQ/@#&]],{n,0,30}] (* Gus Wiseman, Jul 28 2022 *)

is_primepower(n)= {ispower(n, , &n); isprime(n)}
lista(m) = {x = t + t*O(t^m); gf = prod(k=1, m, if (is_primepower(k), 1/(1-x^k), 1)); for (n=0, m, print1(polcoeff(gf, n, t), ", "));}
\\ Michel Marcus, Mar 09 2013

from functools import lru_cache
from sympy import factorint
@lru_cache(maxsize=None)
def A023894(n):
    @lru_cache(maxsize=None)
    def c(n): return sum((p**(e+1)-p)//(p-1) for p,e in factorint(n).items())
    return (c(n)+sum(c(k)*A023894(n-k) for k in range(1,n)))//n if n else 1 # Chai Wah Wu, Jul 15 2024

G.f.: Prod(p prime, Prod(k >= 1, 1/(1-x^(p^k))))

A377051 Array read by antidiagonals downward where A(n,k) is the n-th term of the k-th differences of the powers of primes.

Original entry on oeis.org

1, 2, 1, 3, 1, 0, 4, 1, 0, 0, 5, 1, 0, 0, 0, 7, 2, 1, 1, 1, 1, 8, 1, -1, -2, -3, -4, -5, 9, 1, 0, 1, 3, 6, 10, 15, 11, 2, 1, 1, 0, -3, -9, -19, -34, 13, 2, 0, -1, -2, -2, 1, 10, 29, 63, 16, 3, 1, 1, 2, 4, 6, 5, -5, -34, -97, 17, 1, -2, -3, -4, -6, -10, -16, -21, -16, 18, 115

Offset: 0

Gus Wiseman, Oct 20 2024

Row k of the array is the k-th differences of A000961.

			Array form:
        n=1:  n=2:  n=3:  n=4:  n=5:  n=6:  n=7:  n=8:  n=9:
  ----------------------------------------------------------
  k=0:   1     2     3     4     5     7     8     9    11
  k=1:   1     1     1     1     2     1     1     2     2
  k=2:   0     0     0     1    -1     0     1     0     1
  k=3:   0     0     1    -2     1     1    -1     1    -3
  k=4:   0     1    -3     3     0    -2     2    -4     6
  k=5:   1    -4     6    -3    -2     4    -6    10    -8
  k=6:  -5    10    -9     1     6   -10    16   -18     5
  k=7:  15   -19    10     5   -16    26   -34    23     9
  k=8: -34    29    -5   -21    42   -60    57   -14   -42
  k=9:  63   -34   -16    63  -102   117   -71   -28   104
Triangle form:
    1
    2    1
    3    1    0
    4    1    0    0
    5    1    0    0    0
    7    2    1    1    1    1
    8    1   -1   -2   -3   -4   -5
    9    1    0    1    3    6   10   15
   11    2    1    1    0   -3   -9  -19  -34
   13    2    0   -1   -2   -2    1   10   29   63
   16    3    1    1    2    4    6    5   -5  -34  -97

Row k=0 is A000961, exclusive A246655.
Row k=1 is A057820.
Row k=2 is A376596.
The version for primes is A095195, noncomposites A376682, composites A377033.
A version for partitions is A175804, cf. A053445, A281425, A320590.
For squarefree numbers we have A377038, nonsquarefree A377046.
Triangle row-sums are A377052, absolute version A377053.
Column n = 1 is A377054, for primes A007442 or A030016.
First position of 0 in each row is A377055.
A000040 lists the primes, differences A001223, seconds A036263.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
Cf. A025475, A053707, A093555, A174965, A361102, A376340, A376598, A376653.

nn=12;
t=Table[Take[Differences[NestList[NestWhile[#+1&, #+1,!PrimePowerQ[#]&]&,1,2*nn],k],nn],{k,0,nn}]
Table[t[[j,i-j+1]],{i,nn},{j,i}]

A(i,j) = Sum_{k=0..j} (-1)^(j-k)*binomial(j,k)*A000961(i+k).

A376596 Second differences of consecutive prime-powers inclusive (A000961). First differences of A057820.

Original entry on oeis.org

0, 0, 0, 1, -1, 0, 1, 0, 1, -2, 1, 2, -2, 0, 0, 0, -1, 4, -1, -2, 2, -2, 2, 2, -4, 1, 0, 1, -2, 4, -4, 0, 4, 2, -4, -2, 2, -2, 2, 4, -4, -2, -1, 2, 3, -4, 8, -8, 4, 0, -2, -2, 2, 2, -4, 8, -8, 2, -2, 10, 0, -8, -2, 2, 2, -4, 0, 6, -3, -4, 5, 0, -4, 4, -2, -2

Offset: 1

Gus Wiseman, Oct 02 2024

sign

For the exclusive version, shift left once.

			The prime-powers inclusive (A000961) are:
  1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, ...
with first differences (A057820):
  1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 2, 4, 2, 2, 2, 2, 1, 5, 4, 2, 4, 2, 4, 6, 2, 3, ...
with first differences (A376596):
  0, 0, 0, 1, -1, 0, 1, 0, 1, -2, 1, 2, -2, 0, 0, 0, -1, 4, -1, -2, 2, -2, 2, 2, ...

The version for A000002 is A376604, first differences of A054354.
For first differences we had A057820, sorted firsts A376340(n)+1 (except first term).
Positions of zeros are A376597, complement A376598.
Sorted positions of first appearances are A376653, exclusive A376654.
A000961 lists prime-powers inclusive, exclusive A246655.
A001597 lists perfect-powers, complement A007916.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
A064113 lists positions of adjacent equal prime gaps.
For prime-powers inclusive: A057820 (first differences), A376597 (inflections and undulations), A376598 (nonzero curvature).
For second differences: A036263 (prime), A073445 (composite), A376559 (perfect-power), A376562 (non-perfect-power), A376590 (squarefree), A376593 (nonsquarefree), A376599 (non-prime-power).
Cf. A025475, A045542, A053707, A069623, A093555, A174965, A251092, A333254, A336416, A361102.

Differences[Select[Range[1000],#==1||PrimePowerQ[#]&],2]

from sympy import primepi, integer_nthroot
def A376596(n):
    def iterfun(f,n=0):
        m, k = n, f(n)
        while m != k: m, k = k, f(k)
        return m
    def f(x): return int(n+x-1-sum(primepi(integer_nthroot(x,k)[0]) for k in range(1,x.bit_length())))
    return (a:=iterfun(f,n))-((b:=iterfun(lambda x:f(x)+1,a))<<1)+iterfun(lambda x:f(x)+2,b) # Chai Wah Wu, Oct 02 2024

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

A355743 Numbers whose prime indices are all prime-powers.

Original entry on oeis.org

1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25, 27, 31, 33, 35, 41, 45, 49, 51, 53, 55, 57, 59, 63, 67, 69, 75, 77, 81, 83, 85, 93, 95, 97, 99, 103, 105, 109, 115, 119, 121, 123, 125, 127, 131, 133, 135, 147, 153, 155, 157, 159, 161, 165, 171, 175, 177, 179, 187

Offset: 1

Gus Wiseman, Jul 24 2022

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Also MM-numbers of multiset partitions into constant multisets, where the multiset of multisets with MM-number n is formed by taking the multiset of prime indices of each part of the multiset of prime indices of n. For example, the prime indices of 78 are {1,2,6}, so the multiset of multisets with MM-number 78 is {{},{1},{1,2}}.

			The terms together with their prime indices begin:
   1: {}
   3: {2}
   5: {3}
   7: {4}
   9: {2,2}
  11: {5}
  15: {2,3}
  17: {7}
  19: {8}
  21: {2,4}
  23: {9}
  25: {3,3}
  27: {2,2,2}
  31: {11}
  33: {2,5}
  35: {3,4}
  41: {13}
  45: {2,2,3}

Robert Price, Table of n, a(n) for n = 1..1410

The multiplicative version is A000688, strict A050361, coprime A354911.
The case of only primes (not all prime-powers) is A076610, strict A302590.
Allowing prime index 1 gives A302492.
These are the products of elements of A302493.
Requiring n to be a prime-power gives A302601.
These are the positions of 1's in A355741.
The squarefree case is A356065.
The complement is A356066.
A001222 counts prime-power divisors.
A023894 counts ptns into prime-powers, strict A054685, with 1's A023893.
A034699 gives maximal prime-power divisor.
A246655 lists the prime-powers (A000961 includes 1), towers A164336.
A355742 chooses a prime-power divisor of each prime index.
Cf. A085970, A106244, A279784, A295935, A355731, A356064.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And@@PrimePowerQ/@primeMS[#]&]

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

A376597 Inflection and undulation points in the sequence of prime-powers inclusive (A000961).

Original entry on oeis.org

1, 2, 3, 6, 8, 14, 15, 16, 27, 32, 50, 61, 67, 72, 85, 92, 93, 124, 129, 132, 136, 141, 185, 190, 211, 214, 221, 226, 268, 292, 301, 302, 322, 374, 394, 423, 456, 463, 502, 503, 547, 559, 560, 593, 604, 640, 646, 663, 671, 675, 710, 726, 727, 746, 754, 755

Offset: 1

Gus Wiseman, Oct 05 2024

nonn

These are points at which the second differences (A376596) are zero.

Inclusive means 1 is a prime-power. For the exclusive version, subtract 1 and shift left.

			The prime-powers inclusive (A000961) are:
  1, 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, ...
with first differences (A057820):
  1, 1, 1, 1, 2, 1, 1, 2, 2, 3, 1, 2, 4, 2, 2, 2, 2, 1, 5, 4, 2, 4, 2, 4, 6, 2, ...
with first differences (A376596):
  0, 0, 0, 1, -1, 0, 1, 0, 1, -2, 1, 2, -2, 0, 0, 0, -1, 4, -1, -2, 2, -2, 2, 2, ...
with zeros (A376597) at:
  1, 2, 3, 6, 8, 14, 15, 16, 27, 32, 50, 61, 67, 72, 85, 92, 93, 124, 129, 132, ...

Gus Wiseman, Inflection and undulation points in the prime-powers inclusive.

The first differences were A057820, see also A053707, A376340.
These are the zeros of A376596 (sorted firsts A376653, exclusive A376654).
The complement is A376598.
A000961 lists prime-powers inclusive, exclusive A246655.
A001597 lists perfect-powers, complement A007916.
A023893 and A023894 count integer partitions into prime-powers, factorizations A000688.
A064113 lists positions of adjacent equal prime gaps.
For prime-powers inclusive: A057820 (first differences), A376596 (second differences), A376598 (nonzero curvature).
For second differences: A036263 (prime), A073445 (composite), A376559 (perfect-power), A376562 (non-perfect-power), A376590 (squarefree), A376593 (nonsquarefree), A376599 (non-prime-power).
Cf. A025475, A053707, A069623, A093555, A174965, A361102, A376653, A376654.

Join@@Position[Differences[Select[Range[1000],#==1||PrimePowerQ[#]&],2],0]

A090677 Number of ways to partition n into sums of squares of primes.

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 2, 3, 2, 2, 2, 4, 3, 2, 3, 4, 4, 2, 3, 4, 5, 3, 3, 5, 5, 4, 3, 5, 5, 5, 4, 5, 6, 5, 5, 5, 7, 6, 6, 6, 7, 7, 6, 7, 7, 8, 7, 8, 8, 8, 8, 8, 9, 8, 9, 9, 10, 9, 9, 10, 11, 11, 10, 11

Offset: 0

N. J. A. Sloane, Dec 19 2003

nonn

From Hieronymus Fischer, Nov 11 2007: (Start)
First statement of monotony: a(n+p^2)>=a(n) for all primes p. Proof: we restrict ourselves on a(n)>0 (the case a(n)=0 is trivial). Let T(i), 1<=i<=a(n), be the a(n) different sums of squares of primes representing n. Then, adding p^2 to those expressions, we get a(n) sums of squares of primes T(i)+p^2, obviously representing n+p^2, thus a(n+p^2) cannot be less than a(n).
Second statement of monotony: a(n+m)>=max(a(n),a(m)) for all m with a(m)>1. Proof: let T(i), 1<=i<=a(n), be the a(n) different sums of squares of primes representing n; let S(i), 1<=i<=a(m), be the a(m) different sums of squares of primes representing m. Then, adding these expressions, we get a(n) sums of squares of primes T(i)+S(1), representing n+m, further we get a(m) sums T(1)+S(i), also representing n+m. Thus a(n+m) cannot be less than the maximum of a(n) and a(m).
The minimum b(k):=min( n | a(j)>k for all j>n) exists for all k>=0. See A134755 for that sequence representing b(k). (End)

			a(25)=2 because 25 = 5^2 = 4*(2^2)+3^2.
a(83)=8 because 83 = 3^2+5^2+7^2 = 4*(2^2)+2*(3^2)+7^2
                   = 2*(2^2)+3*(5^2) = 6*(2^2)+3^2+2*(5^2)
                   = 2^2+6*(3^2)+5^2 = 10*(2^2)+2*(3^2)+5^2
                   = 5*(2^2)+7*(3^2) = 14*(2^2)+3*(3^2).

R. F. Churchouse, Representation of integers as sums of squares of primes. Caribbean J. Math. 5 (1986), no. 2, 59-65.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Christian N. K. Anderson, Table of coefficients b_i solving n=sum(b_i * prime(i)^2), for n=0..500
Roger Woodford, Bounds for the Eventual Positivity of Difference Functions of Partitions, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.3.

Cf. A111900, A001248, A001156, A023893, A111901.

Cf. A078134, A078135, A078136, A078139, A134600, A078137, A134754, A134755.

CoefficientList[ Series[ Product[1/(1 - x^Prime[i]^2), {i, 111}], {x, 0, 101}], x] (* Robert G. Wilson v, Sep 20 2004 *)

G.f.: 1/((1-x^4)*(1-x^9)*(1-x^25)*(1-x^49)*(1-x^121)*(1-x^169)*(1-x^289)...).

G.f.: 1 + Sum_{i>=1} x^(prime(i)^2) / Product_{j=1..i} (1 - x^(prime(j)^2)). - Ilya Gutkovskiy, May 07 2017

cp's OEIS Frontend

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

A050361 Number of factorizations into distinct prime powers greater than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

A023894 Number of partitions of n into prime power parts (1 excluded).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A377051 Array read by antidiagonals downward where A(n,k) is the n-th term of the k-th differences of the powers of primes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A376596 Second differences of consecutive prime-powers inclusive (A000961). First differences of A057820.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Python

A106244 Number of partitions into distinct prime powers.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions