A118462 -id:A118462 - cp's OEIS frontend

A118463 Inverse permutation to A118462.

0, 1, 2, 3, 4, 5, 7, 10, 6, 8, 11, 14, 15, 19, 25, 33, 9, 12, 16, 20, 21, 26, 34, 43, 27, 35, 44, 55, 56, 70, 88, 110, 13, 17, 22, 28, 29, 36, 45, 57, 37, 46, 58, 71, 72, 89, 111, 137, 47, 59, 73, 90, 91, 112, 138, 169, 113, 139, 170, 207, 208, 253, 307, 371, 18, 23, 30, 38, 39

Offset: 0

Franklin T. Adams-Watters, Apr 28 2006

Cf. A118462.

g:= proc(n, i) option remember; `if`(n=0, [0], `if`(i<1, [], [seq(
      map(p->p+2^(i-1)*j, g(n-i*j, i-1))[], j=0..min(1, n/i))]))
    end:
b:= proc() local l, i; l:=[]; i:=0;
      proc(n) while nops(l)<=n do
        l:=[l[], sort(g(i, i))[]]; i:=i+1 od; l[n+1]
      end
    end():
a:= proc() local t, a; t, a:= -1, proc() -1 end;
      proc(n) local h;
        while a(n) = -1 do
          t:= t+1; h:= b(t);
          if a(h) = -1 then a(h):= t fi
        od; a(n)
      end
    end():
seq(a(n), n=0..100);  # Alois P. Heinz, Sep 06 2014

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

A089633 Numbers having no more than one 0 in their binary representation.

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 7, 11, 13, 14, 15, 23, 27, 29, 30, 31, 47, 55, 59, 61, 62, 63, 95, 111, 119, 123, 125, 126, 127, 191, 223, 239, 247, 251, 253, 254, 255, 383, 447, 479, 495, 503, 507, 509, 510, 511, 767, 895, 959, 991, 1007, 1015, 1019, 1021, 1022, 1023

Offset: 0

Reinhard Zumkeller, Jan 01 2004

Complement of A158582. - Reinhard Zumkeller, Apr 16 2009
Also union of A168604 and A030130. - Douglas Latimer, Jul 19 2012
Numbers of the form 2^t - 2^k - 1, 0 <= k < t.
n is in the sequence if and only if 2*n+1 is in the sequence. - Robert Israel, Dec 14 2018
Also the least binary rank of a strict integer partition of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1). - Gus Wiseman, May 24 2024

			From _Tilman Piesk_, May 09 2012: (Start)
This may also be viewed as a triangle:             In binary:
                  0                                         0
               1     2                                 01       10
             3    5    6                          011      101      110
           7   11   13   14                  0111     1011     1101     1110
        15   23   27   29   30          01111    10111    11011    11101    11110
      31  47   55   59   61   62
   63   95  111  119  123  125  126
Left three diagonals are A000225,  A055010, A086224. Right diagonal is A000918. Central column is A129868. Numbers in row n (counted from 0) have n binary 1s. (End)
From _Gus Wiseman_, May 24 2024: (Start)
The terms together with their binary expansions and binary indices begin:
   0:      0 ~ {}
   1:      1 ~ {1}
   2:     10 ~ {2}
   3:     11 ~ {1,2}
   5:    101 ~ {1,3}
   6:    110 ~ {2,3}
   7:    111 ~ {1,2,3}
  11:   1011 ~ {1,2,4}
  13:   1101 ~ {1,3,4}
  14:   1110 ~ {2,3,4}
  15:   1111 ~ {1,2,3,4}
  23:  10111 ~ {1,2,3,5}
  27:  11011 ~ {1,2,4,5}
  29:  11101 ~ {1,3,4,5}
  30:  11110 ~ {2,3,4,5}
  31:  11111 ~ {1,2,3,4,5}
  47: 101111 ~ {1,2,3,4,6}
  55: 110111 ~ {1,2,3,5,6}
  59: 111011 ~ {1,2,4,5,6}
  61: 111101 ~ {1,3,4,5,6}
  62: 111110 ~ {2,3,4,5,6}
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, On the Basis Polynomials in the Theory of Permutations with Prescribed Up-Down Structure, arXiv:0801.0072 [math.CO], 2007-201. See Section 14.
Vladimir Shevelev, Binomial Coefficient Predictors, Journal of Integer Sequences, Vol. 14 (2011), Article 11.2.8.
Vladimir Shevelev, The number of permutations with prescribed up-down structure as a function of two variables, INTEGERS, 12 (2012), #A1.
Index entries for sequences related to binary expansion of n.

Cf. A000120, A007088, A011371, A014132, A023416, A023532, A029931.
Cf. A181741 (primes), union of A081118 and A000918, apart from initial -1.
Cf. A065442, A160502, A265705.
For least binary index (instead of rank) we have A001511.
Applying A019565 (Heinz number of binary indices) gives A077011.
For greatest binary index we have A029837 or A070939, opposite A070940.
Row minima of A118462 (binary ranks of strict partitions).
For sum instead of minimum we have A372888, non-strict A372890.
A000009 counts strict partitions, ranks A005117.
A048675 gives binary rank of prime indices, distinct A087207.
A048793 lists binary indices, product A096111, reverse A272020.
A277905 groups all positive integers by binary rank of prime indices.
Cf. A000041, A005940, A018819, A147655, A225620, A246868.

a089633 n = a089633_list !! (n-1)
a089633_list = [2 ^ t - 2 ^ k - 1 | t <- [1..], k <- [t-1,t-2..0]]
-- Reinhard Zumkeller, Feb 23 2012

seq(seq(2^a-1-2^b,b=a-1..0,-1),a=1..11); # Robert Israel, Dec 14 2018

fQ[n_] := DigitCount[n, 2, 0] < 2; Select[ Range[0, 2^10], fQ] (* Robert G. Wilson v, Aug 02 2012 *)

{insq(n) = local(dd, hf, v); v=binary(n);hf=length(v);dd=sum(i=1,hf,v[i]);if(dd<=hf-2,-1,1)}
{for(w=0,1536,if(insq(w)>=0,print1(w,", ")))}
\\ Douglas Latimer, May 07 2013

isoka(n) = #select(x->(x==0), binary(n)) <= 1; \\ Michel Marcus, Dec 14 2018

from itertools import count, islice
def A089633_gen(): # generator of terms
    return ((1<A089633_list = list(islice(A089633_gen(),30)) # Chai Wah Wu, Feb 10 2023

from math import isqrt, comb
def A089633(n): return (1<<(a:=(isqrt((n<<3)+1)-1>>1)+1))-(1<Chai Wah Wu, Dec 19 2024

A023416(a(n)) <= 1; A023416(a(n)) = A023532(n-2) for n>1;
A000120(a(u)) <= A000120(a(v)) for uA000120(a(n)) = A003056(n).
a(0)=0, n>0: a(n+1) = Min{m>n: BinOnes(a(n))<=BinOnes(m)} with BinOnes=A000120.
If m = floor((sqrt(8*n+1) - 1) / 2), then a(n) = 2^(m+1) - 2^(m*(m+3)/2 - n) - 1. - Carl R. White, Feb 10 2009
A029931(a(n)) = n and A029931(m) != n for m < a(n). - Reinhard Zumkeller, Feb 28 2014
A265705(a(n),k) = A265705(a(n),a(n)-k), k = 0 .. a(n). - Reinhard Zumkeller, Dec 15 2015
a(A014132(n)-1) = 2*a(n-1)+1 for n >= 1. - Robert Israel, Dec 14 2018
Sum_{n>=1} 1/a(n) = A065442 + A160502 = 3.069285887459... . - Amiram Eldar, Jan 09 2024
A019565(a(n)) = A077011(n). - Gus Wiseman, May 24 2024

A246867 Triangle T(n,k) in which n-th row lists in increasing order all partitions lambda of n into distinct parts encoded as Product_{i:lambda} prime(i); n>=0, 1<=k<=A000009(n).

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 14, 15, 13, 21, 22, 30, 17, 26, 33, 35, 42, 19, 34, 39, 55, 66, 70, 23, 38, 51, 65, 77, 78, 105, 110, 29, 46, 57, 85, 91, 102, 130, 154, 165, 210, 31, 58, 69, 95, 114, 119, 143, 170, 182, 195, 231, 330, 37, 62, 87, 115, 133, 138, 187

Offset: 0

Alois P. Heinz, Sep 05 2014

The concatenation of all rows (with offset 1) gives a permutation of the squarefree numbers A005117. The missing positive numbers are in A013929.

			The partitions of n=5 into distinct parts are {[5], [4,1], [3,2]}, encodings give {prime(5), prime(4)*prime(1), prime(3)*prime(2)} = {11, 7*2, 5*3} => row 5 = [11, 14, 15].
For n=0 the empty partition [] gives the empty product 1.
Triangle T(n,k) begins:
   1;
   2;
   3;
   5,  6;
   7, 10;
  11, 14, 15;
  13, 21, 22, 30;
  17, 26, 33, 35, 42;
  19, 34, 39, 55, 66,  70;
  23, 38, 51, 65, 77,  78, 105, 110;
  29, 46, 57, 85, 91, 102, 130, 154, 165, 210;
  ...
Corresponding triangle of strict integer partitions begins:
                  0
                 (1)
                 (2)
               (3) (21)
               (4) (31)
             (5) (41) (32)
          (6) (42) (51) (321)
        (7) (61) (52) (43) (421)
     (8) (71) (62) (53) (521) (431)
(9) (81) (72) (63) (54) (621) (432) (531). - _Gus Wiseman_, Feb 23 2018

Alois P. Heinz, Rows n = 0..42, flattened

Column k=1 gives: A008578(n+1).
Last elements of rows give: A246868.
Row sums give A147655.
Row lengths are: A000009.
Cf. A005117, A118462, A215366 (the same for all partitions), A258323, A299755, A299757, A299759.

b:= proc(n, i) option remember; `if`(n=0, [1], `if`(i<1, [], [seq(
      map(p->p*ithprime(i)^j, b(n-i*j, i-1))[], j=0..min(1, n/i))]))
    end:
T:= n-> sort(b(n$2))[]:
seq(T(n), n=0..14);

b[n_, i_] := b[n, i] = If[n==0, {1}, If[i<1, {}, Flatten[Table[Map[ #*Prime[i]^j&, b[n-i*j, i-1]], {j, 0, Min[1, n/i]}]]]]; T[n_] := Sort[b[n, n]]; Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Dec 18 2016, after Alois P. Heinz *)

A277905 Irregular table: Each row n (n >= 0) lists in ascending order all A018819(n) numbers k for which A048675(k) = n.

Original entry on oeis.org

1, 2, 3, 4, 6, 8, 5, 9, 12, 16, 10, 18, 24, 32, 15, 20, 27, 36, 48, 64, 30, 40, 54, 72, 96, 128, 7, 25, 45, 60, 80, 81, 108, 144, 192, 256, 14, 50, 90, 120, 160, 162, 216, 288, 384, 512, 21, 28, 75, 100, 135, 180, 240, 243, 320, 324, 432, 576, 768, 1024, 42, 56, 150, 200, 270, 360, 480, 486, 640, 648, 864, 1152, 1536, 2048, 35, 63, 84, 112, 125, 225, 300, 400

Offset: 1

Antti Karttunen, Nov 14 2016

Each row beginning with an odd number (rows with even index) is followed by a row of the same length, with the same terms, but multiplied by 2. See also comments in the Formula section of A018819.
Note that although the indexing of rows start from zero, the indexing of this sequence starts from 1, with a(1) = 1.
Also Heinz numbers of integer partitions whose binary rank is n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1). For example, row n = 6 is 15, 20, 27, 36, 48, 64, corresponding to the partitions (3,2), (3,1,1), (2,2,2), (2,2,1,1), (2,1,1,1,1), (1,1,1,1,1,1). - Gus Wiseman, May 25 2024
Also, row n lists in ascending order all A018819(n) numbers k for which A097248(k) = A019565(n). - Flávio V. Fernandes, Jul 19 2025

			The irregular table begins as:
  row terms
   0   1;
   1   2;
   2   3,  4;
   3   6,  8;
   4   5,  9,  12,  16;
   5  10, 18,  24,  32;
   6  15, 20,  27,  36,  48,  64;
   7  30, 40,  54,  72,  96, 128;
   8   7, 25,  45,  60,  80,  81, 108, 144, 192, 256;
   9  14, 50,  90, 120, 160, 162, 216, 288, 384, 512;
  10  21, 28,  75, 100, 135, 180, 240, 243, 320, 324, 432,  576,  768, 1024;
  11  42, 56, 150, 200, 270, 360, 480, 486, 640, 648, 864, 1152, 1536, 2048;
...

Antti Karttunen, Table of n, a(n) for n = 1..166
Index entries for sequences that are permutations of the natural numbers

Cf. A019565 (the left edge, the only terms that are squarefree).
Cf. A000079 (the trailing edge).
Cf. A048675, A260443, A277886, A277896, A277903, A277904.
Row lengths are A018819 (number of partitions of binary rank n).
A000009 counts strict partitions, ranks A005117.
A029837 stc_sum or A070939 bin_len, opposite A070940 binexp_lastpos_1.
A048675 gives binary rank of prime indices, distinct A087207.
A048793 lists binary indices, product A096111, reverse A272020.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, cf. A001222, A003963, A056239, A296150.
A372890 adds up binary ranks of partitions, strict A372888.
Cf. A000040, A000041, A001511, A005940, A118462, A215366, A225620, A246868.
Cf. A097248, A048675.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n], {p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Select[Range[0,2^k],Total[2^(prix[#]-1)]==k&],{k,0,10}] (* Gus Wiseman, May 25 2024 *)

(definec (A277905 n) (A277905bi (A277903 n) (A277904 n)))
(define (A277905bi row col) (let outloop ((k (A019565 row)) (col col)) (if (zero? col) k (let inloop ((j (+ 1 k))) (if (= (A048675 j) row) (outloop j (- col 1)) (inloop (+ 1 j))))))) ;; Very slow implementation.
;; Implementation based on a naive recurrence:
(definec (A277905 n) (if (= 1 n) n (let ((maybe_next (A277896 (A277905 (- n 1))))) (if (not (zero? maybe_next)) maybe_next (A019565 (A277903 n))))))

a(1) = 1; for n > 1, if A277896(a(n-1)) > 0, then a(n) = A277896(a(n-1)), otherwise a(n) = A019565(A277903(n)). [A naive recurrence for a one-dimensional version.]
Other identities. For all n >= 1:
A048675(a(n)) = A277903(n).

A372689 Positive integers whose binary indices (positions of ones in reversed binary expansion) sum to a prime number.

Original entry on oeis.org

2, 3, 4, 6, 9, 11, 12, 16, 18, 23, 26, 29, 33, 38, 41, 43, 44, 48, 50, 55, 58, 61, 64, 69, 71, 72, 74, 79, 81, 86, 89, 91, 92, 96, 101, 103, 104, 106, 111, 113, 118, 121, 131, 132, 134, 137, 142, 144, 149, 151, 152, 154, 159, 163, 164, 166, 169, 174, 176, 181

Offset: 1

Gus Wiseman, May 18 2024

A binary index of n is any position of a 1 in its reversed binary expansion. The binary indices of n are row n of A048793.

Note the function taking a set s to its binary rank Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices).

			The terms together with their binary expansions and binary indices begin:
   2:      10 ~ {2}
   3:      11 ~ {1,2}
   4:     100 ~ {3}
   6:     110 ~ {2,3}
   9:    1001 ~ {1,4}
  11:    1011 ~ {1,2,4}
  12:    1100 ~ {3,4}
  16:   10000 ~ {5}
  18:   10010 ~ {2,5}
  23:   10111 ~ {1,2,3,5}
  26:   11010 ~ {2,4,5}
  29:   11101 ~ {1,3,4,5}
  33:  100001 ~ {1,6}
  38:  100110 ~ {2,3,6}
  41:  101001 ~ {1,4,6}
  43:  101011 ~ {1,2,4,6}
  44:  101100 ~ {3,4,6}
  48:  110000 ~ {5,6}
  50:  110010 ~ {2,5,6}
  55:  110111 ~ {1,2,3,5,6}
  58:  111010 ~ {2,4,5,6}
  61:  111101 ~ {1,3,4,5,6}

Numbers k such that A029931(k) is prime.
Union of prime-indexed rows of A118462.
For even instead of prime we have A158704, odd A158705.
For prime indices instead of binary indices we have A316091.
The prime case is A372885, indices A372886.
A000040 lists the prime numbers, A014499 their binary indices.
A019565 gives Heinz number of binary indices, adjoint A048675.
A058698 counts partitions of prime numbers, strict A064688.
A372471 lists binary indices of primes, row-sums A372429.
A372687 counts strict partitions of prime binary rank, counted by A372851.
A372689 lists numbers whose binary indices sum to a prime.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Binary indices:
- listed A048793, sum A029931
- reversed A272020
- opposite A371572, sum A230877
- length A000120, complement A023416
- min A001511, opposite A000012
- max A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
Cf. A035100, A071814, A096111, A023506, A277319, A372688, A372850, A372887.

Select[Range[100],PrimeQ[Total[First /@ Position[Reverse[IntegerDigits[#,2]],1]]]&]

A372890 Sum of binary ranks of all integer partitions of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1).

Original entry on oeis.org

0, 1, 4, 10, 25, 52, 115, 228, 471, 931, 1871, 3687, 7373, 14572, 29049, 57694, 115058, 229101, 457392, 912469, 1822945, 3640998, 7277426, 14544436, 29079423, 58137188, 116254386, 232465342, 464889800, 929691662, 1859302291, 3718428513, 7436694889, 14873042016

Offset: 0

Gus Wiseman, May 23 2024

nonn

			The partitions of 4 are (4), (3,1), (2,2), (2,1,1), (1,1,1,1), with respective binary ranks 8, 5, 4, 4, 4 with sum 25, so a(4) = 25.

Alois P. Heinz, Table of n, a(n) for n = 0..3321

For Heinz number (not binary rank) we have A145519, row sums of A215366.
For Heinz number the strict version is A147655, row sums of A246867.
The strict version is A372888, row sums of A118462.
A005117 gives Heinz numbers of strict integer partitions.
A048675 gives binary rank of prime indices, distinct A087207.
A061395 gives greatest prime index, least A055396.
A118457 lists strict partitions in Mathematica order.
A277905 groups all positive integers by binary rank of prime indices.
Binary indices (A048793):
- length A000120, complement A023416
- min A001511, opposite A000012
- max A029837 or A070939, opposite A070940
- sum A029931, product A096111
- reverse A272020
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
- opposite A371572, sum A230877
Cf. A000041, A005940, A018819, A019565, A066633, A225620, A344086, A365410.

b:= proc(n, i) option remember; `if`(n=0 or i=1, [1, n],
      b(n, i-1)+(p->[0, p[1]*2^(i-1)]+p)(b(n-i, min(n-i, i))))
    end:
a:= n-> b(n$2)[2]:
seq(a(n), n=0..33);  # Alois P. Heinz, May 23 2024

Table[Total[Total[2^(#-1)]&/@IntegerPartitions[n]],{n,0,10}]

From Alois P. Heinz, May 23 2024: (Start)
a(n) = Sum_{k=1..n} 2^(k-1) * A066633(n,k).
a(n) mod 2 = A365410(n-1) for n>=1. (End)

A372888 Sum of binary ranks of all strict integer partitions of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1).

Original entry on oeis.org

0, 1, 2, 7, 13, 31, 66, 138, 279, 581, 1173, 2375, 4783, 9630, 19316, 38802, 77689, 155673, 311639, 623845, 1248179, 2497719, 4996387, 9995304, 19992908, 39990902, 79986136, 159983241, 319975073, 639971495, 1279962115, 2559966847, 5119970499, 10240030209

Offset: 0

Gus Wiseman, May 23 2024

nonn

			The strict partitions of 6 are (6), (5,1), (4,2), (3,2,1), with respective binary ranks 32, 17, 10, 7 with sum 66, so a(6) = 66.

Alois P. Heinz, Table of n, a(n) for n = 0..3321

Row sums of A118462 (binary ranks of strict partitions).
For Heinz number the non-strict version is A145519, row sums of A215366.
For Heinz number (not binary rank) we have A147655, row sums of A246867.
The non-strict version is A372890.
A000009 counts strict partitions, ranks A005117.
A048675 gives binary rank of prime indices, distinct A087207.
A277905 groups all positive integers by binary rank of prime indices.
Binary indices (A048793):
- length A000120, complement A023416
- min A001511, opposite A000012
- max A029837 or A070939, opposite A070940
- sum A029931, product A096111
- reverse A272020
- complement A368494, sum A359400
- opposite A371572, sum A230877
- opposite complement A371571, sum A359359
Cf. A000041, A005940, A015716, A018819, A019565, A118457, A225620, A344086.

b:= proc(n, i) option remember; `if`(i*(i+1)/2 [0, p[1]*2^(i-1)]
          +p)(b(n-i, min(n-i, i-1)))))
    end:
a:= n-> b(n$2)[2]:
seq(a(n), n=0..33);  # Alois P. Heinz, May 23 2024

Table[Total[Total[2^(#-1)]& /@ Select[IntegerPartitions[n],UnsameQ@@#&]],{n,0,10}]

a(n) = Sum_{k=1..n} 2^(k-1) * A015716(n,k). - Alois P. Heinz, May 24 2024

A373120 Number of distinct possible binary ranks of integer partitions of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1).

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 8, 11, 15, 20, 26, 33, 43, 55, 70, 89, 109, 136, 167, 206, 251, 306, 371, 445, 535, 639, 759, 904, 1069, 1262, 1489, 1747, 2047, 2390, 2784, 3237, 3754, 4350, 5027, 5798, 6680, 7671, 8808, 10091, 11543, 13190, 15040, 17128, 19477, 22118

Offset: 0

Gus Wiseman, May 26 2024

nonn

			The partitions of 4 are (4), (3,1), (2,2), (2,1,1), (1,1,1,1), with respective binary ranks 8, 5, 4, 4, 4, so a(4) = 3.

The strict case is A000009.
A048675 gives binary rank of prime indices, distinct A087207.
A118462 lists binary ranks of strict integer partitions, row sums A372888.
A277905 groups all positive integers by binary rank of prime indices.
A372890 adds up binary ranks of integer partitions.
Binary indices (A048793):
- length A000120, complement A023416
- min A001511, opposite A000012
- max A029837 or A070939, opposite A070940
- sum A029931, product A096111
- reverse A272020
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
- opposite A371572, sum A230877
Cf. A000041, A018819, A158704, A158705, A225620, A231204, A372688.

Table[Length[Union[Total[2^(#-1)]&/@IntegerPartitions[n]]],{n,0,15}]

cp's OEIS Frontend

A118463 Inverse permutation to A118462.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

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

A089633 Numbers having no more than one 0 in their binary representation.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Python

Formula

A246867 Triangle T(n,k) in which n-th row lists in increasing order all partitions lambda of n into distinct parts encoded as Product_{i:lambda} prime(i); n>=0, 1<=k<=A000009(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A277905 Irregular table: Each row n (n >= 0) lists in ascending order all A018819(n) numbers k for which A048675(k) = n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Scheme

Formula

A372689 Positive integers whose binary indices (positions of ones in reversed binary expansion) sum to a prime number.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A372890 Sum of binary ranks of all integer partitions of n, where the binary rank of a partition y is given by Sum_i 2^(y_i-1).

Views

Author

Keywords