A070939 -id:A070939 - cp's OEIS frontend

A031443 Digitally balanced numbers: positive numbers that in base 2 have the same number of 0's as 1's.

2, 9, 10, 12, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 135, 139, 141, 142, 147, 149, 150, 153, 154, 156, 163, 165, 166, 169, 170, 172, 177, 178, 180, 184, 195, 197, 198, 201, 202, 204, 209, 210, 212, 216, 225, 226, 228, 232, 240, 527, 535, 539, 541, 542, 551

Offset: 1

Clark Kimberling

Also numbers k such that the binary digital mean dm(2, k) = (Sum_{i=1..d} 2*d_i - 1) / (2*d) = 0, where d is the number of digits in the binary representation of k and d_i the individual digits. - Reikku Kulon, Sep 21 2008
From Reikku Kulon, Sep 29 2008: (Start)
Each run of values begins with 2^(2k + 1) + 2^(k + 1) - 2^k - 1. The initial values increase according to the sequence {2^(k - 1), 2^(k - 2), 2^(k - 3), ..., 2^(k - k)}.
After this, the values follow a periodic sequence of increases by successive powers of two with single odd values interspersed.
Each run ends with an odd increase followed by increases of {2^(k - k), ..., 2^(k - 2), 2^(k - 1), 2^k}, finally reaching 2^(2k + 2) - 2^(k + 1).
Similar behavior occurs in other bases. (End)
Numbers k such that A000120(k)/A070939(k) = 1/2. - Ctibor O. Zizka, Oct 15 2008
Subsequence of A053754; A179888 is a subsequence. - Reinhard Zumkeller, Jul 31 2010
A000120(a(n)) = A023416(a(n)); A037861(a(n)) = 0.
A001700 gives number of terms having length 2*n in binary representation: A001700(n-1) = #{m: A070939(a(m))=2*n}. - Reinhard Zumkeller, Jun 08 2011
The number of terms below 2^k is A079309(floor(k/2)) for k > 1. - Amiram Eldar, Nov 21 2020

			9 is a term because '1001' contains 2 '0's and 2 '1's.

Reikku Kulon, Table of n, a(n) for n = 1..10000
Jason Bell, Thomas F. Lidbetter and Jeffrey Shallit, Additive number theory via approximation by regular languages, International Journal of Foundations of Computer Science, Vol. 31, No. 6 (2020), pp. 667-687; arXiv preprint, arXiv:1804.07996 [cs.FL], 2018.
Thomas Finn Lidbetter, Counting, Adding, and Regular Languages, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
Reinhard Zumkeller, Haskell Programs for Binary Digitally Balanced Numbers.
Index entries for sequences related to binary expansion of n

Subsequences: A144798, A144799, A144800, A144801, A144812, A179888.
Subsequence of A053754.
Row n = 2 of A378000.
Cf. A049354-A049360, A000120, A001316, A006519, A023416, A070939, A144777, A145057, A145058, A145059, A145060, A144912, A145037, A191292, A090050, A014486, A061854, A037861, A079309.
Terms of binary width n are enumerated by A001700.

-- See link, showing that Ulrich Schimkes formula provides a very efficient algorithm. Reinhard Zumkeller, Jun 15 2011

[ n: n in [2..250] | Multiplicity({* z: z in Intseq(n,2) *}, 0) eq &+Intseq(n,2) ];  // Bruno Berselli, Jun 07 2011

a:=proc(n) local nn, n1, n0: nn:=convert(n,base,2): n1:=add(nn[i],i=1..nops(nn)): n0:=nops(nn)-n1: if n0=n1 then n else end if end proc: seq(a(n), n = 1..240); # Emeric Deutsch, Jul 31 2008

Select[Range[250],DigitCount[#,2,1]==DigitCount[#,2,0]&] (* Harvey P. Dale, Jul 22 2013 *)
FromDigits[#,2]&/@DeleteCases[Flatten[Permutations/@Table[PadRight[{},2n,{1,0}],{n,5}],1],?(#[[1]]==0&)]//Sort (* _Harvey P. Dale, May 30 2016 *)

for(n=1,100,b=binary(n); l=length(b); if(sum(i=1,l, component(b,i))==l/2,print1(n,",")))

is(n)=hammingweight(n)==hammingweight(bitneg(n,#binary(n))) \\ Charles R Greathouse IV, Mar 29 2013

is(n)=2*hammingweight(n)==exponent(n)+1 \\ Charles R Greathouse IV, Apr 18 2020

for my $half ( 1 .. 4 ) {
  my $N = 2 * $half;  # only even widths apply
  my $vector = (1 << ($N-1)) | ((1 << ($N/2-1)) - 1);  # first key
  my $n = 1; $n *= $_ for 2 .. $N;    # N!
  my $d = 1; $d *= $_ for 2 .. $N/2;  # (N/2)!
  for (1 .. $n/($d*$d*2)) {
    print "$vector, ";
    my ($v, $d) = ($vector, 0);
    until ($v & 1 or !$v) { $d = ($d << 1)|1; $v >>= 1 }
    $vector += $d + 1 + (($v ^ ($v + 1)) >> 2);  # next key
  }
} # Ruud H.G. van Tol, Mar 30 2014

from sympy.utilities.iterables import multiset_permutations
A031443_list = [int('1'+''.join(p),2) for n in range(1,10) for p in multiset_permutations('0'*n+'1'*(n-1))] # Chai Wah Wu, Nov 15 2019

a(n+1) = a(n) + 2^k + 2^(m-1) - 1 + floor((2^(k+m) - 2^k)/a(n))*(2^(2*m) + 2^(m-1)) where k is the largest integer such that 2^k divides a(n) and m is the largest integer such that 2^m divides a(n)/2^k+1. - Ulrich Schimke (UlrSchimke(AT)aol.com)

A145037(a(n)) = 0. - Reikku Kulon, Oct 02 2008

A096111 If n = 2^k - 1, then a(n) = k+1, otherwise a(n) = (A000523(n)+1)*a(A053645(n)).

Original entry on oeis.org

1, 2, 2, 3, 3, 6, 6, 4, 4, 8, 8, 12, 12, 24, 24, 5, 5, 10, 10, 15, 15, 30, 30, 20, 20, 40, 40, 60, 60, 120, 120, 6, 6, 12, 12, 18, 18, 36, 36, 24, 24, 48, 48, 72, 72, 144, 144, 30, 30, 60, 60, 90, 90, 180, 180, 120, 120, 240, 240, 360, 360, 720, 720, 7, 7, 14, 14, 21, 21

Offset: 0

Amarnath Murthy, Jun 29 2004

nonn

Each n > 1 occurs 2*A045778(n) times in the sequence.
f(n+2^k) = (k+1)*f(n) if 2^k > n+1. - Robert Israel, Apr 25 2016
If the binary indices of n (row n of A048793) are the positions 1's in its reversed binary expansion, then a(n) is the product of all binary indices of n + 1. The number of binary indices of n is A000120(n), their sum is A029931(n), and their average is A326699(n)/A326700(n). - Gus Wiseman, Jul 27 2019

Peter Kagey, Table of n, a(n) for n = 0..10000

Permutation of A096115, i.e. a(n) = A096115(A122198(n+1)) [Note the different starting offsets]. Bisection: A121663. Cf. A096113, A052330.
Cf. A029931.
Cf. A000120, A034797, A048793, A070939, A291166, A326031, A326672, A326673.

f:= proc(n) local L;
    L:= convert(2*n+2,base,2);
    convert(subs(0=NULL,zip(`*`,L, [$0..nops(L)-1])),`*`);
end proc:
map(f, [$0..100]); # Robert Israel, Apr 25 2016

CoefficientList[(Product[1 + k x^(2^(k - 1)), {k, 7}] - 1)/x, x] (* Michael De Vlieger, Apr 08 2016 *)
bpe[n_]:=Join@@Position[Reverse[IntegerDigits[n,2]],1];Table[Times@@bpe[n+1],{n,0,100}] (* Gus Wiseman, Jul 26 2019 *)

N=166; q='q+O('q^N);
gf= (prod(n=1,1+ceil(log(N)/log(2)), 1+n*q^(2^(n-1)) ) - 1) / q;
Vec(gf)
/* Joerg Arndt, Oct 06 2012 */

(define (A096111 n) (cond ((pow2? (+ n 1)) (+ 2 (A000523 n))) (else (* (+ 1 (A000523 n)) (A096111 (A053645 n))))))
(define (pow2? n) (and (> n 0) (zero? (A004198bi n (- n 1)))))

G.f.: ( prod(k>=1, 1+k*x^(2^(k-1)) )- 1 ) / x. - Vladeta Jovovic, Nov 08 2005

a(n) is the product of the exponents in the binary expansion of 2*n + 2. - Peter Kagey, Apr 24 2016

Edited, extended and Scheme code added by Antti Karttunen, Aug 25 2006

A374629 Irregular triangle listing the leaders of maximal weakly increasing runs in the n-th composition in standard order.

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 1, 1, 4, 3, 1, 2, 2, 1, 1, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 2, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 3, 3, 2, 1, 3, 1, 3, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 0

Gus Wiseman, Jul 20 2024

The leaders of maximal weakly increasing runs in a sequence are obtained by splitting it into maximal weakly increasing subsequences and taking the first term of each.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The 58654th composition in standard order is (1,1,3,2,4,1,1,1,2), with maximal weakly increasing runs ((1,1,3),(2,4),(1,1,1,2)), so row 58654 is (1,2,1).
The nonnegative integers, corresponding compositions, and leaders of maximal weakly increasing runs begin:
    0:      () -> ()      15: (1,1,1,1) -> (1)
    1:     (1) -> (1)     16:       (5) -> (5)
    2:     (2) -> (2)     17:     (4,1) -> (4,1)
    3:   (1,1) -> (1)     18:     (3,2) -> (3,2)
    4:     (3) -> (3)     19:   (3,1,1) -> (3,1)
    5:   (2,1) -> (2,1)   20:     (2,3) -> (2)
    6:   (1,2) -> (1)     21:   (2,2,1) -> (2,1)
    7: (1,1,1) -> (1)     22:   (2,1,2) -> (2,1)
    8:     (4) -> (4)     23: (2,1,1,1) -> (2,1)
    9:   (3,1) -> (3,1)   24:     (1,4) -> (1)
   10:   (2,2) -> (2)     25:   (1,3,1) -> (1,1)
   11: (2,1,1) -> (2,1)   26:   (1,2,2) -> (1)
   12:   (1,3) -> (1)     27: (1,2,1,1) -> (1,1)
   13: (1,2,1) -> (1,1)   28:   (1,1,3) -> (1)
   14: (1,1,2) -> (1)     29: (1,1,2,1) -> (1,1)

Gus Wiseman, Sequences counting and ranking compositions by their leaders (for six types of runs).

Row-leaders are A065120.
Row-lengths are A124766.
Row-sums are A374630.
Positions of constant rows are A374633, counted by A374631.
Positions of strict rows are A374768, counted by A374632.
For other types of runs we have A374251, A374515, A374683, A374740, A374757.
Positions of non-weakly decreasing rows are A375137.
A011782 counts compositions.
A238130, A238279, A333755 count compositions by number of runs.
A335456 counts patterns matched by compositions.
All of the following pertain to compositions in standard order:
- Length is A000120.
- Sum is A029837(n+1).
- Leader is A065120.
- Parts are listed by A066099, reverse A228351.
- Number of adjacent equal pairs is A124762, unequal A333382.
- Number of max runs: A124765, A124766, A124767, A124768, A124769, A333381.
- Ranks of anti-run compositions are A333489, counted by A003242.
- Run-length transform is A333627, length A124767, sum A070939.
- Run-compression transform is A373948, sum A373953, excess A373954.
- Ranks of contiguous compositions are A374249, counted by A274174.
- Ranks of non-contiguous compositions are A374253, counted by A335548.
Cf. A046660, A106356, A188920, A189076, A238343, A272919, A333213, A373949, A374634, A374635, A374637, A374701, A375123.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[First/@Split[stc[n],LessEqual],{n,0,100}]

A000788 Total number of 1's in binary expansions of 0, ..., n.

Original entry on oeis.org

0, 1, 2, 4, 5, 7, 9, 12, 13, 15, 17, 20, 22, 25, 28, 32, 33, 35, 37, 40, 42, 45, 48, 52, 54, 57, 60, 64, 67, 71, 75, 80, 81, 83, 85, 88, 90, 93, 96, 100, 102, 105, 108, 112, 115, 119, 123, 128, 130, 133, 136, 140, 143, 147, 151, 156, 159, 163, 167, 172, 176, 181, 186

Offset: 0

N. J. A. Sloane

Partial sums of A000120.
The graph of this sequence is a version of the Takagi curve: see Lagarias (2012), Section 9, especially Theorem 9.1. - N. J. A. Sloane, Mar 12 2016
a(n-1) is the largest possible number of ordered pairs (a,b) such that a/b is a prime in a subset of the positive integers with n elements. - Yifan Xie, Feb 21 2025

J.-P. Allouche & J. Shallit, Automatic sequences, Cambridge University Press, 2003, p. 94
R. Bellman and H. N. Shapiro, On a problem in additive number theory, Annals Math., 49 (1948), 333-340. See Eq. 1.9. [From N. J. A. Sloane, Mar 12 2009]
L. E. Bush, An asymptotic formula for the average sums of the digits of integers, Amer. Math. Monthly, 47 (1940), pp. 154-156. [From the bibliography of Stolarsky, 1977]
P. Cheo and S. Yien, A problem on the k-adic representation of positive integers (Chinese; English summary), Acta Math. Sinica, 5 (1955), pp. 433-438. [From the bibliography of Stolarsky, 1977]
M. P. Drazin and J. S. Griffith, On the decimal representation of integers, Proc. Cambridge Philos. Soc., (4), 48 (1952), pp. 555-565. [From the bibliography of Stolarsky, 1977]
E. N. Gilbert, Games of identification or convergence, SIAM Review, 4 (1962), 16-24.
Grabner, P. J.; Kirschenhofer, P.; Prodinger, H.; Tichy, R. F.; On the moments of the sum-of-digits function. Applications of Fibonacci numbers, Vol. 5 (St. Andrews, 1992), 263-271, Kluwer Acad. Publ., Dordrecht, 1993.
R. L. Graham, On primitive graphs and optimal vertex assignments, pp. 170-186 of Internat. Conf. Combin. Math. (New York, 1970), Annals of the NY Academy of Sciences, Vol. 175, 1970.
E. Grosswald, Properties of some arithmetic functions, J. Math. Anal. Appl., 28 (1969), pp.405-430.
Donald E. Knuth, The Art of Computer Programming, volume 3 Sorting and Searching, section 5.3.4, subsection Bitonic sorting, with C'(p) = a(p-1).
Hiu-Fai Law, Spanning tree congestion of the hypercube, Discrete Math., 309 (2009), 6644-6648 (see p(m) on page 6647).
Z. Li and E. M. Reingold, Solution of a divide-and-conquer maximin recurrence, SIAM J. Comput., 18 (1989), 1188-1200.
B. Lindström, On a combinatorial problem in number theory, Canad. Math. Bull., 8 (1965), 477-490.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. I. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 6, 274-276.
Mauclaire, J.-L.; Murata, Leo; On q-additive functions. II. Proc. Japan Acad. Ser. A Math. Sci. 59 (1983), no. 9, 441-444.
M. D. McIlroy, The number of 1's in binary integers: bounds and extremal properties, SIAM J. Comput., 3 (1974), 255-261.
L. Mirsky, A theorem on representations of integers in the scale of r, Scripta Math., 15 (1949), pp. 11-12.
I. Shiokawa, On a problem in additive number theory, Math. J. Okayama Univ., 16 (1974), pp.167-176. [From the bibliography of Stolarsky, 1977]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
K. B. Stolarsky, Power and exponential sums of digital sums related to binomial coefficient parity, SIAM J. Appl. Math., 32 (1977), 717-730.
Trollope, J. R. An explicit expression for binary digital sums. Math. Mag. 41 1968 21-25.

T. D. Noe and Hieronymus Fischer, Table of n, a(n) for n = 0..10000 (terms up to n=1000 by T. D. Noe).
G. Agnarsson, On the number of hypercubic bipartitions of an integer, arXiv preprint arXiv:1106.4997 [math.CO], 2011.
G. Agnarsson, Induced subgraphs of hypercubes, arXiv preprint arXiv:1112.3015 [math.CO], 2011.
G. Agnarsson and K. Lauria, Extremal subgraphs of the d-dimensional grid graph, arXiv preprint arXiv:1302.6517 [math.CO], 2013.
J.-P. Allouche, On an Inequality in a 1970 Paper of R. L. Graham, INTEGERS 21A (2021), #A2.
Mathias Hauan Arbo, Esten Ingar Grøtli, and Jan Tommy Gravdahl, CASCLIK: CasADi-Based Closed-Loop Inverse Kinematics, arXiv:1901.06713 [cs.RO], 2019.
Venkata Sai Narayana Bavisetty, Matthew Wheeler, Reinhard Laubenbacher, and Claus Kadelka, Upper bound for the stability of Boolean networks, arXiv:2506.12310 [q-bio.MN], 2025. See p. 8.
Johann Cigler, A curious class of Hankel determinants, arXiv:1803.05164 [math.CO], 2018.
G. F. Clements and B. Lindström, A sequence of (+-1) determinants with large values, Proc. Amer. Math. Soc., 16 (1965), pp. 548-550. [From the bibliography of Stolarsky, 1977]
Jean Coquet, Power sums of digital sums, J. Number Theory 22 (1986), no. 2, 161-176.
H. Delange, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math., (2), 21 (1975), pp. 31-47. [From the bibliography of Stolarsky, 1977]
Laurent Feuilloley, Brief Announcement: Average Complexity for the LOCAL Model, arXiv preprint arXiv:1505.05072 [cs.DC], 2015.
S. R. Finch, P. Sebah and Z.-Q. Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
Oscar E. González, An observation of Rankin on Hankel determinants, Department of Mathematics, University of Illinois at Urbana-Champaign, 2018.
P. J. Grabner and H.-K. Hwang, Digital sums and divide-and-conquer recurrences: Fourier expansions and absolute convergence
Milton W. Green, Letter to N. J. A. Sloane, 1973 (note "A360" refers to N0360 which is the present sequence).
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and asymptotic solutions of the recurrence f(n) = f(floor(n/2)) + f(ceiling(n/2)) + g(n): theory and applications, Preprint 2016.
Hsien-Kuei Hwang, S. Janson, and T.-H. Tsai, Exact and Asymptotic Solutions of a Divide-and-Conquer Recurrence Dividing at Half: Theory and Applications, ACM Transactions on Algorithms, 13:4 (2017), #47; DOI: 10.1145/3127585.
Hsien-Kuei Hwang, Svante Janson, and Tsung-Hsi Tsai, Identities and periodic oscillations of divide-and-conquer recurrences splitting at half, arXiv:2210.10968 [cs.DS], 2022, p. 36 and 44.
Jeffrey C. Lagarias, The Takagi function and its properties, arXiv:1112.4205 [math.CA], 2011-2012.
Jeffrey C. Lagarias, The Takagi function and its properties, In Functions in number theory and their probabilistic aspects, 153--189, RIMS Kôkyûroku Bessatsu, B34, Res. Inst. Math. Sci. (RIMS), Kyoto, 2012. MR3014845.
Julien Leroy, Michel Rigo, and Manon Stipulanti, Behavior of Digital Sequences Through Exotic Numeration Systems, Electronic Journal of Combinatorics 24(1) (2017), #P1.44.
Raoul Nakhmanson-Kulish, Graphic representation of K(n)=a(n)/(n log2(n)/2) from n=63 to 131071
D. J. Newman, On the number of binary digits in a multiple of three, Proc. Amer. Math. Soc., 21 (1969), pp. 719-721. [From the bibliography of Stolarsky, 1977]
Ralf Stephan, Some divide-and-conquer sequences ...
Ralf Stephan, Table of generating functions
S. C. Tang, An improvement and generalization of Bellman-Shapiro's theorem on a problem in additive number theory, Proc. Amer. Math. Soc., 14 (1963), pp. 199-204. [From the bibliography of Stolarsky, 1977]
Eric Weisstein's World of Mathematics, Binary
David W. Wilson, Fast C++ function for computing a(n)
Index entries for sequences related to binary expansion of n

For number of 0's in binary expansion of 0, ..., n see A059015.
The basic sequences concerning the binary expansion of n are A000120, A000788, A000069, A001969, A023416, A059015, A070939, A083652.
Cf. A005183, A360189.
Cf. A027868, A037123, A054899, A055640, A055641, A102669-A102685, A117804, A122840, A122841, A160093, A160094, A196563, A196564 (for base 10).

a000788_list = scanl1 (+) A000120_list
-- Walt Rorie-Baety, Jun 30 2012

{a000788 0 = 0; a00788 n = a000788 n2 + a000788 (n-n2-1) + (n-n2) where n2 = n `div` 2}
-- Walt Rorie-Baety, Jul 15 2012

a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+add(i, i=Bits[Split](n))) end:
seq(a(n), n=0..62);  # Alois P. Heinz, Nov 11 2024

a[n_] := Count[ Table[ IntegerDigits[k, 2], {k, 0, n}], 1, 2]; Table[a[n], {n, 0, 62}] (* Jean-François Alcover, Dec 16 2011 *)
Table[Plus@@Flatten[IntegerDigits[Range[n], 2]], {n, 0, 62}] (* Alonso del Arte, Dec 16 2011 *)
Accumulate[DigitCount[Range[0,70],2,1]] (* Harvey P. Dale, Jun 08 2013 *)

A000788(n)={ n<3 && return(n); if( bittest(n,0) \\
, n+1 == 1<A000788(n>>1)*2+n>>1+1 \\
, n == 1<A000788(n>>=1)+A000788(n-1)+n )} \\ M. F. Hasler, Nov 22 2009

a(n)=sum(k=1,n,hammingweight(k)) \\ Charles R Greathouse IV, Oct 04 2013

a(n) = if (n==0, 0, m = logint(n, 2); r = n % 2^m; m*2^(m-1) + r + 1 + a(r)); \\ Michel Marcus, Mar 27 2018

a(n)={n++; my(t, i, s); c=n; while(c!=0, i++; c\=2); for(j=1, i, d=(n\2^(i-j))%2; t+=(2^(i-j)*(s*d+d*(i-j)/2)); s+=d); t} \\ David A. Corneth, Nov 26 2024
(C++) /* See David W. Wilson link. */

def A000788(n): return sum(i.bit_count() for i in range(1,n+1)) # Chai Wah Wu, Mar 01 2023

def A000788(n): return (n+1)*n.bit_count()+(sum((m:=1<>j)-(r if n<<1>=m*(r:=k<<1|1) else 0)) for j in range(1,n.bit_length()+1))>>1) # Chai Wah Wu, Nov 11 2024

McIlroy (1974) gives bounds and recurrences. - N. J. A. Sloane, Mar 24 2014
Stolarsky (1977) studies the asymptotics, and gives at least nine references to earlier work on the problem. I have added all the references that were not here already. - N. J. A. Sloane, Apr 06 2014
a(n) = Sum_{k=1..n} A000120(k). - Benoit Cloitre, Dec 19 2002
a(0) = 0, a(2n) = a(n)+a(n-1)+n, a(2n+1) = 2a(n)+n+1. - Ralf Stephan, Sep 13 2003
a(n) = n*log_2(n)/2 + O(n); a(2^n)=n*2^(n-1)+1. - Benoit Cloitre, Sep 25 2003 (The first result is due to Bellman and Shapiro, - N. J. A. Sloane, Mar 24 2014)
a(n) = n*log_2(n)/2+n*F(log_2(n)) where F is a nowhere differentiable continuous function of period 1 (see Allouche & Shallit). - Benoit Cloitre, Jun 08 2004
G.f.: (1/(1-x)^2) * Sum_{k>=0} x^2^k/(1+x^2^k). - Ralf Stephan, Apr 19 2003
a(2^n-1) = A001787(n) = n*2^(n-1). - M. F. Hasler, Nov 22 2009
a(4^n-2) = n(4^n-2).
For real n, let f(n) = [n]/2 if [n] even, n-[n+1]/2 otherwise. Then a(n) = Sum_{k>=0} 2^k*f((n+1)/2^k).
a(A000225(n)) = A173921(A000225(n)) = A001787(n); a(A000079(n)) = A005183(n). - Reinhard Zumkeller, Mar 04 2010
From Hieronymus Fischer, Jun 10 2012: (Start)
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/2^j + 1/2)*(2n + 2 - floor(n/2^j + 1/2))*2^j - floor(n/2^j)*(2n + 2 - (1 + floor(n/2^j)) * 2^j)), where m=floor(log_2(n)).
a(n) = (n+1)*A000120(n) - 2^(m-1) + 1/4 + (1/2)*Sum_{j=1..m+1} ((floor(n/2^j) + 1/2)^2 - floor(n/2^j + 1/2)^2)*2^j, where m=floor(log_2(n)).
a(2^m-1) = m*2^(m-1).
(This is the total number of '1' digits occurring in all the numbers with <= m bits.)
Generic formulas for the number of digits >= d in the base p representations of all integers from 0 to n, where 1<= d < p.
a(n) = (1/2)*Sum_{j=1..m+1} (floor(n/p^j + (p-d)/p)*(2n + 2 + ((p-2*d)/p - floor(n/p^j + (p-d)/p))*p^j) - floor(n/p^j)*(2n + 2 - (1+floor(n/p^j)) * p^j)), where m=floor(log_p(n)).
a(n) = (n+1)*F(n,p,d) + (1/2)*Sum_{j=1..m+1} ((((p-2*d)/p)*floor(n/p^j+(p-d)/p) + floor(n/p^j))*p^j - (floor(n/p^j+(p-d)/p)^2 - floor(n/p^j)^2)*p^j), where m=floor(log_p(n)) and F(n,p,d) = number of digits >= d in the base p representation of n.
a(p^m-1) = (p-d)*m*p^(m-1).
(This is the total number of digits >= d occurring in all the numbers  with <= m digits in base p representation.)
G.f.: g(x) = (1/(1-x)^2)*Sum_{j>=0} (x^(d*p^j) - x^(p*p^j))/(1-x^(p*p^j)). (End)
a(n) = Sum_{k=1..n} A000120(A240857(n,k)). - Reinhard Zumkeller, Apr 14 2014
For n > 0, if n is written as 2^m + r with 0 <= r < 2^m, then a(n) = m*2^(m-1) + r + 1 + a(r). - Shreevatsa R, Mar 20 2018
a(n) = n*(n+1)/2 + Sum_{k=1..floor(n/2)} ((2k-1)((g(n,k)-1)*2^(g(n,k) + 1) + 2) - (n+1)*(g(n,k)+1)*g(n,k)/2), where g(n,k) = floor(log_2(n/(2k-1))). - Fabio Visonà, Mar 17 2020
From Jeffrey Shallit, Aug 07 2021: (Start)
A 2-regular sequence, satisfying the identities
a(4n+1) = -a(2n) + a(2n+1) + a(4n)
a(4n+2) = -2a(2n) + 2a(2n+1) + a(4n)
a(4n+3) = -4a(n) + 4a(2n+1)
a(8n) = 4a(n) - 8a(2n) + 5a(4n)
a(8n+4) = -9a(2n) + 5a(2n+1) + 4a(4n)
for n>=0. (End)
a(n) = Sum_{k=0..floor(log_2(n+1))} k * A360189(n,k). - Alois P. Heinz, Mar 06 2023

More terms from Larry Reeves (larryr(AT)acm.org), Jan 15 2001

A124762 Number of levels for compositions in standard order.

Original entry on oeis.org

0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 2, 2, 0, 0, 1, 3, 0, 0, 0, 1, 0, 1, 0, 2, 1, 1, 2, 2, 2, 2, 3, 5, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 1, 1, 0, 0, 1, 3, 0, 0, 0, 1, 1, 2, 1, 3, 0, 0, 1, 1, 1, 1, 2, 4, 0, 0, 0, 1, 1, 0, 0, 2, 0

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions. This sequence gives the number of adjacent equal terms in the n-th composition in standard order. Alternatively, a(n) is one fewer than the number of maximal anti-runs in the same composition, where anti-runs are sequences without any adjacent equal terms. For example, the 1234567th composition in standard order is (3,2,1,2,2,1,2,5,1,1,1) with anti-runs ((3,2,1,2),(2,1,2,5,1),(1),(1)), so a(1234567) = 4 - 1 = 3. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; 2>1=1, so a(11) = 1.
The table starts:
  0
  0
  0 1
  0 0 0 2
  0 0 1 1 0 0 1 3
  0 0 0 1 0 1 0 2 0 0 1 1 1 1 2 4
  0 0 0 1 1 0 0 2 0 0 2 2 0 0 1 3 0 0 0 1 0 1 0 2 1 1 2 2 2 2 3 5

Cf. A066099, A124760, A124761, A124763, A124764, A011782 (row lengths), A059570 (row sums).
Anti-runs summing to n are counted by A003242(n).
A triangle counting maximal anti-runs of compositions is A106356.
A triangle counting maximal runs of compositions is A238279.
Partitions whose first differences are an anti-run are A238424.
All of the following pertain to compositions in standard order (A066099):
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766.
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Adjacent unequal pairs are counted by A333382.
- Anti-runs are A333489.
Cf. A000120, A029931, A048793, A059893, A070939, A114994, A225620, A228351.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Select[Partition[stc[n],2,1],SameQ@@#&]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

For a composition b(1),...,b(k), a(n) = Sum_{1<=i=1

For n > 0, a(n) = A333381(n) - 1. - Gus Wiseman, Apr 08 2020

A225620 Indices of partitions in the table of compositions of A228351.

Original entry on oeis.org

1, 2, 3, 4, 6, 7, 8, 10, 12, 14, 15, 16, 20, 24, 26, 28, 30, 31, 32, 36, 40, 42, 48, 52, 56, 58, 60, 62, 63, 64, 72, 80, 84, 96, 100, 104, 106, 112, 116, 120, 122, 124, 126, 127, 128, 136, 144, 160, 164, 168, 170, 192, 200, 208, 212, 224, 228, 232, 234, 240, 244, 248, 250, 252, 254, 255

Offset: 1

Omar E. Pol, Aug 03 2013

Also triangle read by rows in which T(n,k) is the decimal representation of a binary number whose mirror represents the k-th partition of n according with the list of juxtaposed reverse-lexicographically ordered partitions of the positive integers (A026792).
In order to construct this sequence as a triangle we use the following rules:
- In the list of A026792 we replace each part of size j of the k-th partition of n by concatenation of j - 1 zeros and only one 1.
- Then replace this new set of parts by the concatenation of its parts.
- Then replace this string by its mirror version which is a binary number.
T(n,k) is the decimal value of this binary number, which represents the k-th partition of n (see example).
The partitions of n are represented by a subsequence with A000041(n) integers starting with 2^(n-1) and ending with 2^n - 1, n >= 1. The odd numbers of the sequence are in A000225.
First differs from A065609 at a(23).
Conjecture: this sequence is a sorted version of b(n) where b(2^k) = 2^k for k >= 0, b(n) = A080100(n)*(2*b(A053645(n)) + 1) otherwise. - Mikhail Kurkov, Oct 21 2023

			T(6,8) = 58 because 58 in base 2 is 111010 whose mirror is 010111 which is the concatenation of 01, 01, 1, 1, whose number of digits are 2, 2, 1, 1, which are also the 8th partition of 6.
Illustration of initial terms:
The sequence represents a table of partitions (see below):
--------------------------------------------------------
.            Binary                        Partitions
n  k  T(n,k) number  Mirror   Diagram       (A026792)
.                                          1 2 3 4 5 6
--------------------------------------------------------
.                             _
1  1     1       1    1        |           1,
.                             _ _
1  1     2      10    01      _  |           2,
2  2     3      11    11       | |         1,1,
.                             _ _ _
3  1     4     100    001     _ _  |           3,
3  2     6     110    011     _  | |         2,1,
3  3     7     111    111      | | |       1,1,1,
.                             _ _ _ _
4  1     8    1000    0001    _ _    |           4,
4  2    10    1010    0101    _ _|_  |         2,2,
4  3    12    1100    0011    _ _  | |         3,1,
4  4    14    1110    0111    _  | | |       2,1,1,
4  5    15    1111    1111     | | | |     1,1,1,1,
.                             _ _ _ _ _
5  1    16   10000    00001   _ _ _    |           5,
5  2    20   10100    00101   _ _ _|_  |         3,2,
5  3    24   11000    00011   _ _    | |         4,1,
5  4    26   11010    01011   _ _|_  | |       2,2,1,
5  5    28   11100    00111   _ _  | | |       3,1,1,
5  6    30   11110    01111   _  | | | |     2,1,1,1,
5  7    31   11111    11111    | | | | |   1,1,1,1,1,
.                             _ _ _ _ _ _
6  1    32  100000    000001  _ _ _      |           6
6  2    36  100100    001001  _ _ _|_    |         3,3,
6  3    40  101000    000101  _ _    |   |         4,2,
6  4    42  101010    010101  _ _|_ _|_  |       2,2,2,
6  5    48  110000    000011  _ _ _    | |         5,1,
6  6    52  110100    001011  _ _ _|_  | |       3,2,1,
6  7    56  111000    000111  _ _    | | |       4,1,1,
6  8    58  111010    010111  _ _|_  | | |     2,2,1,1,
6  9    60  111100    001111  _ _  | | | |     3,1,1,1,
6  10   62  111110    011111  _  | | | | |   2,1,1,1,1,
6  11   63  111111    111111   | | | | | | 1,1,1,1,1,1,
.
Triangle begins:
  1;
  2,   3;
  4,   6,  7;
  8,  10, 12, 14, 15;
  16, 20, 24, 26, 28, 30, 31;
  32, 36, 40, 42, 48, 52, 56, 58, 60, 62, 63;
  ...
From _Gus Wiseman_, Apr 01 2020: (Start)
Using the encoding of A066099, this sequence ranks all finite nonempty multisets, as follows.
   1: {1}
   2: {2}
   3: {1,1}
   4: {3}
   6: {1,2}
   7: {1,1,1}
   8: {4}
  10: {2,2}
  12: {1,3}
  14: {1,1,2}
  15: {1,1,1,1}
  16: {5}
  20: {2,3}
  24: {1,4}
  26: {1,2,2}
  28: {1,1,3}
  30: {1,1,1,2}
  31: {1,1,1,1,1}
(End)

Column 1 is A000079. Row n has length A000041(n). Right border gives A000225.
Cf. A026792, A065609, A135010, A141285, A186114, A194446, A194546, A206437, A207779, A211978, A225600, A225610, A228351.
The case covering an initial interval is A333379 or A333380.
All of the following pertain to compositions in the order of A066099.
- The weakly increasing version is this sequence.
- The weakly decreasing version is A114994.
- The strictly increasing version is A333255.
- The strictly decreasing version is A333256.
- The unequal version is A233564.
- The equal version is A272919.
- The case covering an initial interval is A333217.
- Initial intervals are ranked by A164894.
- Reversed initial intervals are ranked by A246534.
Cf. A000120, A029931, A048793, A070939, A124766, A233249, A333219, A333220.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],LessEqual@@stc[#]&] (* Gus Wiseman, Apr 01 2020 *)

Conjecture: a(A000070(m) - k) = 2^m - A228354(k) for m > 0, 0 < k <= A000041(m). - Mikhail Kurkov, Oct 20 2023

A333219 Heinz number of the n-th composition in standard order.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 8, 7, 10, 9, 12, 10, 12, 12, 16, 11, 14, 15, 20, 15, 18, 18, 24, 14, 20, 18, 24, 20, 24, 24, 32, 13, 22, 21, 28, 25, 30, 30, 40, 21, 30, 27, 36, 30, 36, 36, 48, 22, 28, 30, 40, 30, 36, 36, 48, 28, 40, 36, 48, 40, 48, 48, 64, 17, 26, 33, 44

Offset: 1

Gus Wiseman, Mar 16 2020

nonn

Includes all positive integers.
The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again.
The Heinz number of a composition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   1: {}           15: {2,3}          25: {3,3}
   2: {1}          20: {1,1,3}        30: {1,2,3}
   3: {2}          15: {2,3}          30: {1,2,3}
   4: {1,1}        18: {1,2,2}        40: {1,1,1,3}
   5: {3}          18: {1,2,2}        21: {2,4}
   6: {1,2}        24: {1,1,1,2}      30: {1,2,3}
   6: {1,2}        14: {1,4}          27: {2,2,2}
   8: {1,1,1}      20: {1,1,3}        36: {1,1,2,2}
   7: {4}          18: {1,2,2}        30: {1,2,3}
  10: {1,3}        24: {1,1,1,2}      36: {1,1,2,2}
   9: {2,2}        20: {1,1,3}        36: {1,1,2,2}
  12: {1,1,2}      24: {1,1,1,2}      48: {1,1,1,1,2}
  10: {1,3}        24: {1,1,1,2}      22: {1,5}
  12: {1,1,2}      32: {1,1,1,1,1}    28: {1,1,4}
  12: {1,1,2}      13: {6}            30: {1,2,3}
  16: {1,1,1,1}    22: {1,5}          40: {1,1,1,3}
  11: {5}          21: {2,4}          30: {1,2,3}
  14: {1,4}        28: {1,1,4}        36: {1,1,2,2}

The length of the k-th composition in standard order is A000120(k).
The sum of the k-th composition in standard order is A070939(k).
The maximum of the k-th composition in standard order is A070939(k).
A partial inverse is A333220. See also A233249.
Cf. A048793, A056239, A066099, A112798, A114994, A124767, A213925, A225620, A228351, A233564, A272919, A333218.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Times@@Prime/@stc[n],{n,0,100}]

A056239(a(n)) = A070939(n).

A124754 Alternating sum of compositions in standard order.

Original entry on oeis.org

0, 1, 2, 0, 3, 1, -1, 1, 4, 2, 0, 2, -2, 0, 2, 0, 5, 3, 1, 3, -1, 1, 3, 1, -3, -1, 1, -1, 3, 1, -1, 1, 6, 4, 2, 4, 0, 2, 4, 2, -2, 0, 2, 0, 4, 2, 0, 2, -4, -2, 0, -2, 2, 0, -2, 0, 4, 2, 0, 2, -2, 0, 2, 0, 7, 5, 3, 5, 1, 3, 5, 3, -1, 1, 3, 1, 5, 3, 1, 3, -3, -1, 1, -1, 3, 1, -1, 1, 5, 3, 1, 3, -1, 1, 3, 1, -5, -3, -1, -3, 1, -1, -3, -1, 3

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

The sum of row n is 2^{n-1} for n>0.

			Composition number 11 is 2,1,1; 2-1+1 = 2, so a(11) = 2.
The table starts:
0
1
2 0
3 1 -1 1

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

Cf. A066099, A070939, A124756, A011782 (row lengths), A106400.

For a composition b(1),...,b(k), a(n) = Sum_{i=1}^k (-1)^{i-1} b(i).
a(2^k) = k+1. If n = 2^e_1 + 2^e_2 + k, 0 <= k < 2^e_2 < 2^e_1, then a(n) = (e_1 - e_2) - a(2^e_2 + k).
a(0) = 0; for n>0, a(n) = a(floor(n/2)) - A106400(n).

A124766 Number of monotonically increasing runs for compositions in standard order.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 1, 3, 2, 2, 1, 2, 1, 2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 2, 2, 1, 2, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 1, 2, 2, 2, 1, 3, 2, 2, 1

Offset: 0

Franklin T. Adams-Watters, Nov 06 2006

The standard order of compositions is given by A066099.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. a(n) is the number of maximal weakly increasing runs in this composition. Alternatively, a(n) is one plus the number of strict descents in the same composition. For example, the weakly increasing runs of the 1234567th composition are ((3),(2),(1,2,2),(1,2,5),(1,1,1)), so a(1234567) = 5. The 4 strict descents together with the weak ascents are: 3 > 2 > 1 <= 2 <= 2 > 1 <= 2 <= 5 > 1 <= 1 <= 1. - Gus Wiseman, Apr 08 2020

			Composition number 11 is 2,1,1; the increasing runs are 2; 1,1; so a(11) = 2.
The table starts:
  0
  1
  1 1
  1 2 1 1
  1 2 1 2 1 2 1 1
  1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 1
  1 2 2 2 1 3 2 2 1 2 1 2 2 3 2 2 1 2 2 2 1 2 2 2 1 2 1 2 1 2 1 1

Cf. A066099, A124761, A011782 (row lengths).
Compositions of n with k strict descents are A238343.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Sum is A070939.
- Weakly decreasing compositions are A114994.
- Adjacent equal pairs are counted by A124762.
- Weakly decreasing runs are counted by A124765.
- Weakly increasing runs are counted by A124766 (this sequence).
- Equal runs are counted by A124767.
- Strictly increasing runs are counted by A124768.
- Strictly decreasing runs are counted by A124769.
- Weakly increasing compositions are A225620.
- Reverse is A228351 (triangle).
- Strict compositions are A233564.
- Initial intervals are A246534.
- Constant compositions are A272919.
- Normal compositions are A333217.
- Permutations are A333218.
- Strictly decreasing compositions are A333255.
- Strictly increasing compositions are A333256.
- Runs-resistance is A333628.
Cf. A124760, A124763, A124764, A333213, A333220, A333379.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Table[Length[Split[stc[n],#1<=#2&]],{n,0,100}] (* Gus Wiseman, Apr 08 2020 *)

a(0) = 0, a(n) = A124761(n) + 1 for n > 0.

Previous Showing 81-90 of 853 results. Next

cp's OEIS Frontend

A272020 Irregular triangle read by rows: strictly decreasing sequences of positive numbers given in lexicographic order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A031443 Digitally balanced numbers: positive numbers that in base 2 have the same number of 0's as 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

PARI

Perl

Python

Formula

A096111 If n = 2^k - 1, then a(n) = k+1, otherwise a(n) = (A000523(n)+1)*a(A053645(n)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Scheme

Formula

Extensions

A374629 Irregular triangle listing the leaders of maximal weakly increasing runs in the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A000788 Total number of 1's in binary expansions of 0, ..., n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Python

Python

Formula

Extensions

A124762 Number of levels for compositions in standard order.

Views

Author

Keywords