login
A321171
a(n) is the total number of 1's in binary that n shares with the positive integers less than n.
1
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
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
KEYWORD
base,nonn
AUTHOR
Brandon Weiss, Aug 27 2019
STATUS
approved