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
KEYWORD
base,nonn
AUTHOR
Brandon Weiss, Aug 27 2019
STATUS
approved