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

Author

Clark Kimberling

Keywords

• nonn
• base
• easy
• nice

Comments

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

Examples

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

Links

• 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

Crossrefs

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.

Programs

Haskell

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

Magma

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

Maple

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

Mathematica

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 *)

PARI

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

PARI

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

PARI

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

Perl

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

Python

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

Formula

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