A087135 -id:A087135 - cp's OEIS frontend

A073642 Replace 2^k in the binary representation of n with k (i.e., if n = 2^b + 2^c + 2^d + ... then a(n) = b + c + d + ...).

0, 0, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 4, 4, 5, 5, 6, 6, 7, 7, 7, 7, 8, 8, 9, 9, 10, 10, 5, 5, 6, 6, 7, 7, 8, 8, 8, 8, 9, 9, 10, 10, 11, 11, 9, 9, 10, 10, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 15, 15, 6, 6, 7, 7, 8, 8, 9, 9, 9, 9, 10, 10, 11, 11, 12, 12, 10, 10, 11, 11, 12, 12, 13, 13

Offset: 0

Benoit Cloitre, Aug 29 2002

For n >= 1, a(n) is the n-th row sum of the irregular triangle A133457. - Vladimir Shevelev, Dec 14 2015

For n >= 0, 2^a(n) is the number of partitions of n whose dimension (given by the hook-length formula) is an odd integer. See the MacDonald reference. - Arvind Ayyer, May 12 2016

			9 = 2^3 + 2^0, hence a(9) = 3 + 0 = 3;
25 = 2^4 + 2^3 + 2^0, hence a(25) = 4 + 3 + 0 = 7.

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Arvind Ayyer, Amritanshu Prasad and Steven Spallone, Odd partitions in Young's lattice, arXiv:1601.01776 [math.CO], 2016.
Ian G. MacDonald, On the degrees of the irreducible representations of symmetric groups, Bulletin of the London Mathematical Society, 3(2):189-192, 1971.

Cf. A059867, A029931, A087135, A000009, A087136, A272090.

a073642 = sum . zipWith (*) [0..] . a030308_row
-- Reinhard Zumkeller, Jun 01 2013

A073642 := proc(n)
        local bdgs ;
        bdgs := convert(n,base,2) ;
        add( op(i,bdgs)*(i-1), i=1..nops(bdgs)) ;
end proc: # R. J. Mathar, Nov 17 2011

Total[Flatten[Position[Rest[Reverse[IntegerDigits[#, 2]]], 1]]] & /@ Range[0, 87] (* Jayanta Basu, Jul 03 2013 *)

a(n)=sum(i=1,length(binary(n)), component(binary(n),i)*(length(binary(n))-i))

a(n) = my(b=binary(n)); b*-[-#b+1..0]~; \\ Ruud H.G. van Tol, Oct 17 2023

def A073642(n):
    a, i = 0, 0
    while n > 0:
        a, n, i = a+(n%2)*i, n//2, i+1
    return a
print([A073642(n) for n in range(30)]) # A.H.M. Smeets, Aug 17 2019

a(n) = log_2(A059867(n)).
It seems that for n > 10 a(n) < n/(2*log(n)) and that Sum_{k=1..n} a(k) is asymptotic to C*n*log(n)^2 with 1/2 > C > 0.47.
a(1)=0, a(2n) = a(n) + e1(n), a(2n+1) = a(2n), where e1(n) = A000120(n). - Ralf Stephan, Jun 19 2003
If n = 2^log_2(n) then a(n) = log_2(n); otherwise, a(n) = log_2(n) + a(n-2^log_2(n)), where log_2=A000523. a(2*n+1) = a(2*n), as the least significant bit of n does not contribute to a(n). - Reinhard Zumkeller, Aug 17 2003, edited by A.H.M. Smeets, Aug 17 2019
a(n) = A029931(floor(n/2)). - Franklin T. Adams-Watters, Oct 22 2011
a(n) = Sum_{k=0..A070939(n)-1} k*A030308(n,k). - Reinhard Zumkeller, Jun 01 2013
Conjecture: a(n) = (3*A011371(n) - Sum_{k=1..n} A007814(k)^2)/2 for n > 0. - Velin Yanev, Sep 09 2017
G.f.: (1/(1 - x)) * Sum_{k>=1} k*x^(2^k)/(1 + x^(2^k)). - Ilya Gutkovskiy, Aug 17 2019
From A.H.M. Smeets, Aug 17 2019: (Start)
floor(log_2(n)) <= a(n) <= floor(log_2(n+2)*(log_2(n+2)-1)/2), n > 0.
Lower bound: floor(log_2(n)) = a(n) for n = 2^m or n = 2^m+1, m >= 0.
Upper bound: a(n) = floor(log_2(n+2)*(log_2(n+2)-1)/2) for n = 2^m-2 or n = 2^m-1, m >= 0. (End)
From Aayush Soni, Feb 12 2022: (Start)
For k < 2^n, a((2^n)+k) + a((2^n)-k-1) = n*(n+1)/2.
Proof: Any (n+1)-bit number 111...11_2 can only be split into two numbers 2^n + k and 2^n - k - 1 which never share any bits in common. Since a(111...11_2) = 0+1+2+...+n, this implies the stated formula. (End)

a(0)=0 and offset corrected by Philippe Deléham, Apr 20 2009

A207642 Expansion of g.f.: Sum_{n>=0} x^n * Product_{k=0..n-1} (1 + x^(n+k)).

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 2, 3, 3, 2, 4, 4, 4, 4, 5, 6, 6, 6, 6, 8, 9, 8, 10, 10, 10, 12, 14, 14, 14, 15, 16, 19, 20, 20, 22, 24, 24, 26, 28, 30, 34, 34, 35, 38, 40, 42, 46, 50, 50, 54, 58, 60, 63, 66, 70, 76, 80, 84, 88, 92, 96, 102, 108, 112, 120, 126, 131, 140, 146, 151

Offset: 0

Paul D. Hanna, Feb 19 2012

nonn

Conjecture: a(n) is the number of partitions p of n into distinct parts such that max(p) <= 1 + 2*min(p), for n >= 1 (as in the Mathematica program at A241061). - Clark Kimberling, Apr 16 2014

			G.f.: A(x) = 1 + x + 2*x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 3*x^7 + 3*x^8 + 2*x^9 + 4*x^10 + 4*x^11 + 4*x^12 + 4*x^13 + 5*x^14 + 6*x^15 + 6*x^16 + 6*x^17 + ...
such that, by definition,
A(x) = 1 + x*(1 + x) + x^2*(1 + x^2)*(1 + x^3) + x^3*(1 + x^3)*(1 + x^4)*(1 + x^5) + x^4*(1 + x^4)*(1 + x^5)*(1 + x^6)*(1 + x^7) + x^5*(1 + x^5)*(1 + x^6)*(1 + x^7)*(1 + x^8)*(1 + x^9) + ... + x^n*Product_{k=0..n-1} (1 + x^(n+k)) + ...
Also
A(x) = 1/(1 - x)  +  x^2/((1 - x^2)*(1 - x^3))  +  x^7/((1 - x^3)*(1 - x^4)*(1 - x^5))  +  x^15/((1 - x^4)*(1 - x^5)*(1 - x^6)*(1 - x^7))  +  x^26/((1 - x^5)*(1 - x^6)*(1 - x^7)*(1 - x^8)*(1 - x^9)) + ... + x^(n*(3*n+1)/2)/(Product_{k=0..n} 1 - x^(n+k+1)) + ...

Vaclav Kotesovec, Table of n, a(n) for n = 0..10000 (terms 0..1000 from Paul D. Hanna)

Cf. A053263, A087135, A241061.

m:=80; R:=PowerSeriesRing(Integers(), m); [1] cat Coefficients(R!( (&+[x^n*(&*[1+x^(n+j): j in [0..n-1]]) : n in [1..m]]) )); // G. C. Greubel, Jan 12 2019

With[{m = 80}, CoefficientList[Series[Sum[x^n*Product[1+x^(n+j), {j,0, n-1}], {n,0,m}], {x,0,m}], x]] (* G. C. Greubel, Jan 12 2019 *)
nmax = 100; pk = x + x^2; s = 1 + pk; Do[pk = Normal[Series[pk * x*(1 + x^(2*k - 2))*(1 + x^(2*k - 1))/(1 + x^(k - 1)), {x, 0, nmax}]]; s = s + pk, {k, 2, nmax}]; Take[CoefficientList[s, x], nmax + 1] (* Vaclav Kotesovec, Jun 18 2019 *)

{a(n)=polcoeff(sum(m=0,n,x^m*prod(k=0,m-1,1+x^(m+k) +x*O(x^n))),n)}
for(n=0,80,print1(a(n),", "))

R = PowerSeriesRing(ZZ, 'x')
m = 80
x = R.gen().O(m)
s = sum(x^n*prod(1+x^(n+j) for j in (0..n-1)) for n in (0..m))
s.coefficients() # G. C. Greubel, Jan 12 2019

G.f.: Sum_{n>=0} x^(n*(3*n+1)/2) / ( Product_{k=0..n} 1 - x^(n+k+1) ). - Paul D. Hanna, Oct 14 2020

a(n) ~ c * exp(r*sqrt(n)) / sqrt(n), where r = 0.926140105877... = 2*sqrt((3/2)*log(z)^2 - polylog(2, 1-z) + polylog(2, 1-z^2)), where z = (-1 + (44 - 3*sqrt(177))^(1/3) + (44 + 3*sqrt(177))^(1/3))/6 = 0.82948354095849703967... is the real root of the equation z^3*(1 - z)/(1 - z^2)^2 = 1 and c = 0.57862299312... - Vaclav Kotesovec, Jun 29 2019, updated Oct 09 2024

A248956 Number of polynomials a_kx^k + ... + a_1x + a_0 with k > 0, integer coefficients and only non-multiple positive integer roots and a_0 = p^n (p is a prime).

Original entry on oeis.org

1, 3, 5, 9, 13, 19, 27, 37, 49, 65, 85, 109, 139, 175, 219, 273, 337, 413, 505, 613, 741, 893, 1071, 1279, 1523, 1807, 2137, 2521, 2965, 3477, 4069, 4749, 5529, 6425, 7449, 8619, 9955, 11475, 13203, 15167, 17393, 19913, 22765, 25985, 29617, 33713, 38321, 43501

Offset: 0

Reiner Moewald, Oct 17 2014

nonn

If D_n = {p^0, ..., p^n} is the set of all positive divisors of p^n (p is a prime), then a(n) gives the number of all subsets of D_n for which the product of all their elements is a divisor of p^n. Furthermore, a(n) gives the number of all strict partitions of n including the integer 0.

			a(1) = 3: -p*x+p; -x+p; x^2 - (p+1)*x + p.

Hiroaki Yamanouchi, Table of n, a(n) for n = 0..1000

Cf. A248955, A248348.

Partial sums of A087135.

a(n) = -1 + 2*Sum_{k=0..n} a*(k) where a*(n) = A000009(n).
a(n) = A248955(p^n), where p is any prime. - Michel Marcus, Nov 07 2014
a(n) = 2*A036469(n) - 1. - Hiroaki Yamanouchi, Nov 21 2014

a(20)-a(22) from Michel Marcus, Nov 07 2014

a(23)-a(47) from Hiroaki Yamanouchi, Nov 21 2014

A087136 Smallest positive number m such that A073642(m)=n.

Original entry on oeis.org

1, 2, 4, 6, 10, 12, 14, 22, 26, 28, 30, 46, 54, 58, 60, 62, 94, 110, 118, 122, 124, 126, 190, 222, 238, 246, 250, 252, 254, 382, 446, 478, 494, 502, 506, 508, 510, 766, 894, 958, 990, 1006, 1014, 1018, 1020, 1022, 1534, 1790, 1918, 1982, 2014, 2030, 2038

Offset: 0

Reinhard Zumkeller, Aug 17 2003

nonn

A073642(a(n))=n and A073642(k)

A073642(A000051(n))=n and A073642(k)>n for k>A000051(n).

Cf. A087135.

i = 1; Table[While[Total[Flatten[Position[Rest[Reverse[IntegerDigits[i, 2]]], 1]]] != k, i++]; i, {k, 0, 52}] (* Jayanta Basu, Aug 12 2013 *)

"Positive" added to definition by N. J. A. Sloane, Aug 25 2019

A216708 Number of compositions (ordered partitions) of n into 2 or more distinct nonnegative parts.

Original entry on oeis.org

0, 2, 2, 10, 10, 18, 48, 56, 86, 124, 298, 336, 540, 722, 1070, 2122, 2614, 3810, 5316, 7496, 9986, 18940, 22558, 33336, 44568, 63074, 82034, 114754, 187642, 234690, 328536, 441872, 602006, 794020, 1072546, 1389408, 2207532, 2706266, 3752462, 4900474, 6681022, 8574906

Offset: 0

César Eliud Lozada, Sep 16 2012

nonn

If permutations are considered equivalent then a(n)=A087135(n)=2*A000009(n) for n>0.

All terms are even. - Alois P. Heinz, Aug 18 2018

			a(2)=2 because 2 = 0+2 = 2+0 (2 ways)
a(3)=10 because 3 = 0+3 = 1+2 = 2+1 = 3+0 = 0+1+2 = 0+2+1 = 1+0+2 = 1+2+0 = 2+0+1 = 2+1+0 (10 ways)

Alois P. Heinz, Table of n, a(n) for n = 0..5000
César Eliud Lozada, Illustration for terms up to n=9

Cf. A216695, A087135, A000009, A032020.

b:= proc(n, i, p) option remember; (m-> `if`(m b(n$2, 0):
seq(a(n), n=0..42);  # Alois P. Heinz, Aug 18 2018

b[n_, i_, p_] := b[n, i, p] = With[{m = i(i+1)/2}, If[m < n, 0, If[n == 0,
     If[p == 0, 0, If[p == 1, 2, p! (p+2)]], b[n, i-1, p] +
     b[n-i, Min[n-i, i-1], p+1]]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 42] (* Jean-François Alcover, Mar 05 2021, after Alois P. Heinz *)

N=66;  x='x+O('x^N);
gf=sum(k=0,N, (k+1)!*x^((k^2+k)/2) / prod(j=1,k+1, 1-x^j)) - 1/(1-x);
v=Vec(gf);
vector(#v+1,n,if(n==1,0,v[n-1]))
/* Joerg Arndt, Sep 17 2012 */

From Joerg Arndt, Sep 17 2012: (Start)
G.f. sum(k>=0, (k+1)!*x^((k^2+k)/2) / prod(j=1..k+1, 1-x^j)) - 1/(1-x);
explanation: the g.f. for partitions into at least two positive parts (A111133) is
sum(k>=0, x^((k^2+k)/2) / prod(j=1..k, 1-x^j)) - 1/(1-x)
(i.e., the g.f. of A000009 minus the g.f. 1/(1-x) for the constant sequence a(n)=1 that counts the single partition n = [n]);
the factor (k+1)! in the g.f. of this function provides for the permutations of the parts, including a zero.
(End)

More terms, Joerg Arndt, Sep 17 2012

Showing 1-5 of 5 results.

cp's OEIS Frontend

A073642 Replace 2^k in the binary representation of n with k (i.e., if n = 2^b + 2^c + 2^d + ... then a(n) = b + c + d + ...).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A207642 Expansion of g.f.: Sum_{n>=0} x^n * Product_{k=0..n-1} (1 + x^(n+k)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Sage

Formula

A248956 Number of polynomials a_k*x^k + ... + a_1*x + a_0 with k > 0, integer coefficients and only non-multiple positive integer roots and a_0 = p^n (p is a prime).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A087136 Smallest positive number m such that A073642(m)=n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Extensions

A216708 Number of compositions (ordered partitions) of n into 2 or more distinct nonnegative parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A248956 Number of polynomials a_kx^k + ... + a_1x + a_0 with k > 0, integer coefficients and only non-multiple positive integer roots and a_0 = p^n (p is a prime).