If we consider having the non-natural number 0000000 along
with the natural numbers in binary from 0000001 through 1111111,
along with all the natural numbers in a list, like this:
0000000
0000001
0000010
0000011
0000100
0000101
0000110
0000111
...
1111110
1111111
Each column of digits in that list contains
the same number of 1's as 0's
The last binary number in that list, 1111111, has decimal
value
1(2^6)+1(2^5)+1(2^4)+1(2^3)+1(2^2)+1(2^1)+1(2^0) =
1(64)+1(32)+1(16)+1(8)+1(4)+1(2)+1(1) =
64+32+16+8+4+2+1 = 127,
so counting 0000000 there are 128 binary numbers in that list.
Each column of digits contains 128 digits, 64 or which
are 0's and 64 of which are 1's. Since there are 7
columns of digits, there are 7(64) = 448 0's and 448 1's.
Edwin
The number of ones, s, in the binary representation of n, when n is , is:
However, 7 digits is reached at 1,000,000 and the closest power of 2 to that is
So we need to either figure out how to subtract those extra 48577 numbers (48577 because we're including 1,000,000).
—
I took a short cut and wrote a C program. Tested on 2^20 and it gave me 10485760, in agreement with the equation above. When I feed the program the input 1,000,000 it outputs
—————————————————
C source code below
—————————————————
// Took out angle brackets around include files to allow posting, next 3 lines
#include stdio.h
#include stdlib.h
#include strings.h
// Compute how many 1's in binary representation of 0..n
// This array converts index 0..15 to number of 1's in its binary representation
int hdig2ones[16] = { 0, 1, 1, 2,
1, 2, 2, 3,
1, 2, 2, 3,
2, 3, 3, 4 };
//--------------------------------------
// count ones in hex string
//
int count_ones(char *hs)
{
int count=0, i, idx;
for(i=0; i
if (hs[i] >= 'a') {
idx = hs[i] - 'a' + 10;
}
else {
idx = hs[i] - '0';
}
//printf("input = '%c'\n", hs[i]);
//printf("n_ones = %d\n", hdig2ones[idx]);
count += hdig2ones[idx];
}
return count;
}
//--------------------------------------
// MAIN
int main(int argc, char **argv)
{
int i,j;
if (argc != 2) {
printf("ERROR: howmanyones \n");
exit(1);
}
int n = strtol(argv[1],0,0);
char foo[20];
int total_ones = 0;
for(i=0; i
// Convert to hex
sprintf(foo, "%x", i);
total_ones += count_ones(foo);
}
printf("Total 1's written = %d\n", total_ones);
return 0;
}