A372688 -id:A372688 - cp's OEIS frontend

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

			From _Gus Wiseman_, May 22 2024: (Start)
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
   30: {1,2,3}
   40: {1,1,1,3}
   54: {1,2,2,2}
   72: {1,1,1,2,2}
   96: {1,1,1,1,1,2}
  128: {1,1,1,1,1,1,1}
(End)

Antti Karttunen, Table of n, a(n) for n = 1..1024
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]

Row 2 of A104244.
Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
The formula section details how the sequence maps the terms of A329050, A329332.
A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
Numbers k such that a(k) is prime are A277319, counts A372688.
Grouping by image gives A277905.
A014499 lists binary indices of prime numbers.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
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. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
Cf. A087207, A097248.

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
map(f, [$1..100]); # Robert Israel, Oct 10 2016

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)

a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ Michel Marcus, Oct 10 2016

\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020

from sympy import factorint, primepi
def a(n):
    if n==1: return 0
    f=factorint(n)
    return sum([f[i]*2**(primepi(i) - 1) for i in f])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 19 2017

a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
From Antti Karttunen, Jul 29 2015: (Start)
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
Other identities. For all n >= 0:
a(A019565(n)) = n.
a(A260443(n)) = n.
a(A206296(n)) = A000129(n).
a(A005940(n+1)) = A087808(n).
a(A007913(n)) = A248663(n).
a(A007947(n)) = A087207(n).
a(A283477(n)) = A005187(n).
a(A284003(n)) = A006068(n).
a(A285101(n)) = A028362(1+n).
a(A285102(n)) = A068052(n).
Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016
From Peter Munn, Jan 31 2020: (Start)
a(n^2) = a(A003961(n)) = 2 * a(n).
a(A297845(n,k)) = a(n) * a(k).
a(n) = a(A225546(n)).
a(A329332(n,k)) = n * k.
a(A329050(n,k)) = 2^(n+k).
(End)
From Antti Karttunen, Feb 02-25 2020, Feb 01 2021: (Start)
a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
a(n) = a(A097248(n)).
For n >= 2:
A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
For n >= 1, A331750(n) = a(A000203(n)).
For n >= 1, the following chains hold:
A293447(n) >= a(n) >= A331740(n) >= A331591(n).
a(n) >= A087207(n) >= A248663(n).
(End)
a(n) = A087207(A097248(n)). - Flávio V. Fernandes, Jul 16 2025

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

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

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]]]&]

A372885 Prime numbers whose binary indices (positions of ones in reversed binary expansion) sum to another prime number.

Original entry on oeis.org

2, 3, 11, 23, 29, 41, 43, 61, 71, 79, 89, 101, 103, 113, 131, 137, 149, 151, 163, 181, 191, 197, 211, 239, 269, 271, 281, 293, 307, 331, 349, 353, 373, 383, 401, 433, 457, 491, 503, 509, 523, 541, 547, 593, 641, 683, 701, 709, 743, 751, 761, 773, 827, 863, 887

Offset: 1

Gus Wiseman, May 19 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.

The indices of these primes are A372886.

			The binary indices of 89 are {1,4,5,7}, with sum 17, which is prime, so 89 is in the sequence.
The terms together with their binary expansions and binary indices begin:
    2:         10 ~ {2}
    3:         11 ~ {1,2}
   11:       1011 ~ {1,2,4}
   23:      10111 ~ {1,2,3,5}
   29:      11101 ~ {1,3,4,5}
   41:     101001 ~ {1,4,6}
   43:     101011 ~ {1,2,4,6}
   61:     111101 ~ {1,3,4,5,6}
   71:    1000111 ~ {1,2,3,7}
   79:    1001111 ~ {1,2,3,4,7}
   89:    1011001 ~ {1,4,5,7}
  101:    1100101 ~ {1,3,6,7}
  103:    1100111 ~ {1,2,3,6,7}
  113:    1110001 ~ {1,5,6,7}
  131:   10000011 ~ {1,2,8}
  137:   10001001 ~ {1,4,8}
  149:   10010101 ~ {1,3,5,8}
  151:   10010111 ~ {1,2,3,5,8}
  163:   10100011 ~ {1,2,6,8}
  181:   10110101 ~ {1,3,5,6,8}
  191:   10111111 ~ {1,2,3,4,5,6,8}
  197:   11000101 ~ {1,3,7,8}

Robert Israel, Table of n, a(n) for n = 1..10000

For prime instead of binary indices we have A006450, prime case of A316091.
Prime numbers p such that A029931(p) is also prime.
Prime case of A372689.
The indices of these primes are 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.
A372687 counts strict partitions of prime binary rank, counted by A372851.
A372688 counts partitions of prime binary rank, with Heinz numbers A277319.
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. A000009, A029837, A035100, A038499, A096111, A372429, A372441, A372471, A372850, A372887.

filter:= proc(p)
  local L,i,t;
  L:= convert(p,base,2);
  isprime(add(i*L[i],i=1..nops(L)))
end proc:
select(filter, [seq(ithprime(i),i=1..200)]); # Robert Israel, Jun 19 2025

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

A372886 Indices of prime numbers whose binary indices (positions of ones in reversed binary expansion) sum to another prime number.

Original entry on oeis.org

1, 2, 5, 9, 10, 13, 14, 18, 20, 22, 24, 26, 27, 30, 32, 33, 35, 36, 38, 42, 43, 45, 47, 52, 57, 58, 60, 62, 63, 67, 70, 71, 74, 76, 79, 84, 88, 94, 96, 97, 99, 100, 101, 108, 116, 124, 126, 127, 132, 133, 135, 137, 144, 150, 154, 156, 160, 161, 162, 164, 172

Offset: 1

Gus Wiseman, May 19 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.

The prime numbers themselves are A372885(n).

			The binary indices of 89 = prime(24) are {1,4,5,7}, with sum 17, which is prime, so 24 is in the sequence.

Robert Israel, Table of n, a(n) for n = 1..10000

Numbers k such that A029931(prime(k)) is prime.
Indices of primes that belong to A372689.
The indexed prime numbers themselves are A372885.
A000040 lists the prime numbers, A014499 their binary indices
A006450 lists primes of prime index, prime case of A316091.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
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
A058698 counts partitions of prime numbers, strict A064688.
A372687 counts strict partitions of prime binary rank, counted by A372851.
A372688 counts partitions of prime binary rank, with Heinz numbers A277319.
Cf. A029837, A158704, A158705, A035100, A372429, A372471, A372850.

filter:= proc(p)
  local L,i,t;
  L:= convert(p,base,2);
  isprime(add(i*L[i],i=1..nops(L)))
end proc:
select(t -> filter(ithprime(t)), [$1..1000]); # Robert Israel, Jun 19 2025

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

A372687 Number of prime numbers whose binary indices sum to n. Number of strict integer partitions y of n such that Sum_i 2^(y_i-1) is prime.

Original entry on oeis.org

0, 0, 1, 1, 1, 0, 2, 1, 2, 0, 3, 3, 1, 4, 1, 6, 5, 8, 4, 12, 8, 12, 7, 20, 8, 16, 17, 27, 19, 38, 19, 46, 33, 38, 49, 65, 47, 67, 83, 92, 94, 113, 103, 130, 146, 127, 215, 224, 176, 234, 306, 270, 357, 383, 339, 393, 537, 540, 597, 683, 576, 798, 1026, 830, 1157

Offset: 0

Gus Wiseman, May 15 2024

nonn

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 inverse of A048793 (binary indices) takes a set s to Sum_i 2^(s_i-1).

			The a(2) = 1 through a(17) = 8 prime numbers:
  2  3  5  .  17  11  19  .  257  131  73  137  97  521  4099  1031
              7       13     67   41       71       263  2053  523
                             37   23       43       139  1033  269
                                           29       83   193   163
                                                    53   47    149
                                                    31         101
                                                               89
                                                               79
The a(2) = 1 through a(11) = 3 strict partitions:
  (2)  (2,1)  (3,1)  .  (5,1)    (4,2,1)  (4,3,1)  .  (9,1)    (6,4,1)
                        (3,2,1)           (5,2,1)     (6,3,1)  (8,2,1)
                                                      (7,2,1)  (5,3,2,1)

For all positive integers (not just prime) we get A000009.
Number of prime numbers p with A029931(p) = n.
For odd instead of prime we have A096765, even A025147, non-strict A087787
Number of times n appears in A372429.
Number of rows of A372471 with sum n.
The non-strict version is A372688 (or A372887), ranks A277319 (or A372850).
These (strict) partitions have Heinz numbers A372851.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
A048793 lists binary indices:
- length A000120
- min A001511
- sum A029931
- max A070939
- reverse A272020
A058698 counts partitions of prime numbers, strict A064688.
A096111 gives product of binary indices.
A372689 lists numbers whose binary indices sum to a prime.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Cf. A000040, A005940, A023506, A029837, A035100, A071814, A230877, A231204, A359359, A372436, A372441.

Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&PrimeQ[Total[2^#]/2]&]],{n,0,30}]

A372850 Numbers whose distinct prime indices are the binary indices of some prime number.

Original entry on oeis.org

3, 6, 9, 10, 12, 18, 20, 22, 24, 27, 30, 36, 40, 42, 44, 46, 48, 50, 54, 60, 66, 70, 72, 80, 81, 84, 88, 90, 92, 96, 100, 102, 108, 114, 118, 120, 126, 130, 132, 140, 144, 150, 160, 162, 168, 176, 180, 182, 184, 192, 198, 200, 204, 216, 228, 236, 238, 240, 242

Offset: 1

Gus Wiseman, May 16 2024

nonn

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.
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.
Note the function taking a set s to its rank Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices).

			The distinct prime indices of 45 are {2,3}, which are the binary indices of 6, which is not prime, so 45 is not in the sequence.
The distinct prime indices of 60 are {1,2,3}, which are the binary indices of 7, which is prime, so 60 is in the sequence.
The terms together with their prime indices begin:
    3: {2}
    6: {1,2}
    9: {2,2}
   10: {1,3}
   12: {1,1,2}
   18: {1,2,2}
   20: {1,1,3}
   22: {1,5}
   24: {1,1,1,2}
   27: {2,2,2}
   30: {1,2,3}
   36: {1,1,2,2}
   40: {1,1,1,3}
   42: {1,2,4}
   44: {1,1,5}
   46: {1,9}
   48: {1,1,1,1,2}
   50: {1,3,3}
   54: {1,2,2,2}
   60: {1,1,2,3}
   66: {1,2,5}
   70: {1,3,4}

For even instead of prime we have A005408, with multiplicity A003159.
For odd instead of prime we have  A005843, with multiplicity A036554.
For prime indices with multiplicity we have A277319, counted by A372688.
The squarefree case is A372851, counted by A372687.
Partitions of this type are counted by A372887.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
A048793 and A272020 (reverse) list binary indices:
- length A000120
- min A001511
- sum A029931
- max A070939
A058698 counts partitions of prime numbers, strict A064688.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Cf. A000040, A005940, A023506, A029837, A035100, A071814, A096111, A372429, A372436, A372441, A372471, A372689.

prix[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],PrimeQ[Total[2^(Union[prix[#]]-1)]]&]

Numbers k such that Sum_{i:prime(i)|k} 2^(i-1) is prime, where the sum is over the distinct prime indices of k.

A372851 Squarefree numbers whose prime indices are the binary indices of some prime number.

Original entry on oeis.org

3, 6, 10, 22, 30, 42, 46, 66, 70, 102, 114, 118, 130, 182, 238, 246, 266, 318, 330, 354, 370, 402, 406, 434, 442, 510, 546, 646, 654, 690, 762, 770, 798, 930, 938, 946, 962, 986, 1066, 1102, 1122, 1178, 1218, 1222, 1246, 1258, 1334, 1378, 1430, 1482, 1578

Offset: 1

Gus Wiseman, May 16 2024

nonn

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.
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.
Note the function taking a set s to its rank Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices).

			The prime indices of 70 are {1,3,4}, which are the binary indices of 13, which is prime, so 70 is in the sequence.
The prime indices of 15 are {2,3}, which are the binary indices of 6, which is not prime, so 15 is not in the sequence.
The terms together with their prime indices begin:
    3: {2}
    6: {1,2}
   10: {1,3}
   22: {1,5}
   30: {1,2,3}
   42: {1,2,4}
   46: {1,9}
   66: {1,2,5}
   70: {1,3,4}
  102: {1,2,7}
  114: {1,2,8}
  118: {1,17}
  130: {1,3,6}
  182: {1,4,6}
  238: {1,4,7}
  246: {1,2,13}
  266: {1,4,8}
  318: {1,2,16}
  330: {1,2,3,5}
  354: {1,2,17}
  370: {1,3,12}
  402: {1,2,19}

[Warning: do not confuse A372887 with the strict case A372687.]
For odd instead of prime we have A039956.
For even instead of prime we have A056911.
Strict partitions of this type are counted by A372687.
Non-strict partitions of this type are counted by A372688, ranks A277319.
The nonsquarefree version is A372850, counted by A372887.
A014499 lists binary indices of prime numbers.
A019565 gives Heinz number of binary indices, adjoint A048675.
A038499 counts partitions of prime length, strict A085756.
A048793 and A272020 (reverse) list binary indices:
- length A000120
- min A001511
- sum A029931
- max A070939
A058698 counts partitions of prime numbers, strict A064688.
A372885 lists primes whose binary indices sum to a prime, indices A372886.
Cf. A000040, A005940, A025147, A035100, A071814, A096111, A096765, A231204, A372429, A372471, A372689.

Select[Range[100],SquareFreeQ[#] && PrimeQ[Total[2^(PrimePi/@First/@FactorInteger[#]-1)]]&]

Squarefree numbers k such that Sum_{i:prime(i)|k} 2^(i-1) is prime, where the sum is over the (distinct) prime indices of k.

cp's OEIS Frontend

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

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

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

A372885 Prime numbers whose binary indices (positions of ones in reversed binary expansion) sum to another prime number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A372886 Indices of prime numbers whose binary indices (positions of ones in reversed binary expansion) sum to another prime number.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A372687 Number of prime numbers whose binary indices sum to n. Number of strict integer partitions y of n such that Sum_i 2^(y_i-1) is prime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A372850 Numbers whose distinct prime indices are the binary indices of some prime number.

Views

Author

Keywords

Comments