A321171 a(n) is the total number of 1's in binary that n shares with the positive integers less than n.

0, 0, 2, 0, 3, 4, 9, 0, 5, 6, 13, 8, 16, 18, 28, 0, 9, 10, 21, 12, 24, 26, 40, 16, 30, 32, 48, 36, 53, 56, 75, 0, 17, 18, 37, 20, 40, 42, 64, 24, 46, 48, 72, 52, 77, 80, 107, 32, 58, 60, 88, 64, 93, 96, 127, 72, 103, 106, 139, 112, 146, 150, 186, 0, 33, 34, 69, 36, 72, 74, 112

Offset

1,3

Comments

The graph follows a fractal pattern repeating and enlarging after every power of 2. The number of "lines" produced by the scatter plot in each fractal section approaching a power of two is equivalent to log(base 2) of that number.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..8192

Formula

a(n) = Sum_{e >=0, n mod 2^(e+1) >= 2^e} (n - (n mod 2^(e+1)))/2 + (n mod 2^(e+1) - 2^e).

Example

For n = 5: 5 in binary is 101. This shares one 1 with 1 (01), one 1 with 3 (11), and one 1 with 4 (100). Therefore a(5) = 3.
For n = 11: 11 in binary is 1011. This shares one 1 with 1 (01), one 1 with 2 (10), two 1's with 3 (11), one 1 with 5 (101), one 1 with 6 (110), two 1's with 7 (111), one 1 with 8 (1000), two 1's with 9 (1001), and two 1's with 10 (1010). Therefore a(11) = 13.

Maple

a:= n-> add(add(i, i=Bits[Split](Bits[And](n, j))), j=1..n-1):
seq(a(n), n=1..80);  # Alois P. Heinz, Jun 19 2022

Mathematica

a[n_] := Sum[DigitCount[BitAnd[n, k], 2, 1], {k, 1, n-1}];
a /@ Range[1, 100] (* Jean-François Alcover, Sep 28 2019 *)

Prog

(Java)
import java.lang.Math;
public class Binaryish {
  public static void main(String args[]){
    int max = 270; //Generate numbers up to a(max)
    for(int x = 1; x <= max; x++) {
      System.out.print(counter(x) + "\n");
    }
  }
  public static int counter(int amount){
    int a = amount, count = 0, power = 0;
    while(Math.pow(2, power) < a){
      power++;
    }
    for(int z = 1; z <= power; z++){
      if(a % Math.pow(2, z) > Math.pow(2, z-1)-1){
        count += (a/((int) Math.pow(2, z))*Math.pow(2, z-1)) + (a%Math.pow(2, z)-Math.pow(2, z-1));
      }
    }
    return count;
  }
}
(PARI) a(n)={sum(k=1, n-1, hammingweight(bitand(n, k)))} \\ Andrew Howroyd, Aug 27 2019
(PARI) a(n)={sum(e=0, logint(n, 2), if(bittest(n, e), (n>>(e+1)<<e) + bitand(n, (1<<e)-1)))} \\ Andrew Howroyd, Aug 27 2019
(Python)
def a(n): return sum((i&n).bit_count() for i in range(1, n))
print([a(n) for n in range(1, 72)]) # Michael S. Branicky, Jun 19 2022

Crossrefs

Cf. A007088 (binary numbers), A048881.

Sequence in context: A336972 A110990 A254213 * A336973 A369017 A352846

Adjacent sequences: A321168 A321169 A321170 * A321172 A321173 A321174

Keyword

base,nonn

Author

Brandon Weiss, Aug 27 2019

Status

approved