document.write( "Question 1101136: How many times do write digit 1 if you write all possible natural numbers up to seven digits using digits 0 and 1 only? \n" ); document.write( "
Algebra.Com's Answer #715740 by math_helper(2461)\"\" \"About 
You can put this solution on YOUR website!
The number of ones, s, in the binary representation of n, when n is \"+2%5Er+\" , is:\r
\n" ); document.write( "\n" ); document.write( " \"+s+=+n%2A%282%5En+%2F+2%29+=+n%2A2%5E%28n-1%29+\"\r
\n" ); document.write( "\n" ); document.write( "However, 7 digits is reached at 1,000,000 and the closest power of 2 to that is \"2%5E20+=+1048576+\"
\n" ); document.write( "
\n" ); document.write( "So we need to either figure out how to subtract those extra 48577 numbers (48577 because we're including 1,000,000). \r
\n" ); document.write( "\n" ); document.write( "—
\n" ); document.write( " 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 \"+highlight%289884992%29+\"\r
\n" ); document.write( "\n" ); document.write( "—————————————————
\n" ); document.write( "C source code below
\n" ); document.write( "—————————————————
\n" ); document.write( "

\n" );
document.write( "// Took out angle brackets around include files to allow posting, next 3 lines
\n" );
document.write( "#include  stdio.h
\n" );
document.write( "#include  stdlib.h
\n" );
document.write( "#include  strings.h\r
\n" );
document.write( "
\n" );
document.write( "\n" );
document.write( "// Compute how many 1's in binary representation of 0..n\r
\n" );
document.write( "\n" );
document.write( "// This array converts index 0..15 to number of 1's in its binary representation
\n" );
document.write( "int hdig2ones[16] = { 0, 1, 1, 2, 
\n" );
document.write( "                      1, 2, 2, 3,
\n" );
document.write( "                      1, 2, 2, 3,
\n" );
document.write( "                      2, 3, 3, 4 };\r
\n" );
document.write( "\n" );
document.write( "//--------------------------------------
\n" );
document.write( "// count ones in hex string
\n" );
document.write( "//
\n" );
document.write( "int count_ones(char *hs)
\n" );
document.write( "{
\n" );
document.write( "  int count=0, i, idx;\r
\n" );
document.write( "
\n" );
document.write( "\n" );
document.write( "  for(i=0; i\n" );
document.write( "    if (hs[i] >= 'a') {
\n" );
document.write( "      idx = hs[i] - 'a' + 10;
\n" );
document.write( "    }
\n" );
document.write( "    else {
\n" );
document.write( "      idx = hs[i] - '0';
\n" );
document.write( "    }
\n" );
document.write( "    //printf(\"input = '%c'\n\", hs[i]);
\n" );
document.write( "    //printf(\"n_ones = %d\n\", hdig2ones[idx]);
\n" );
document.write( "    count += hdig2ones[idx];
\n" );
document.write( "  }\r
\n" );
document.write( "\n" );
document.write( "  return count;
\n" );
document.write( "}\r
\n" );
document.write( "\n" );
document.write( "//--------------------------------------
\n" );
document.write( "// MAIN
\n" );
document.write( "int main(int argc, char **argv) 
\n" );
document.write( "{
\n" );
document.write( "  int i,j;\r
\n" );
document.write( "\n" );
document.write( "  if (argc != 2) {
\n" );
document.write( "    printf(\"ERROR: howmanyones \n\");
\n" );
document.write( "    exit(1);
\n" );
document.write( "  }\r
\n" );
document.write( "\n" );
document.write( "  int n = strtol(argv[1],0,0);
\n" );
document.write( "  char foo[20];
\n" );
document.write( "  int total_ones = 0;\r
\n" );
document.write( "\n" );
document.write( "  for(i=0; i\n" );
document.write( "    // Convert to hex
\n" );
document.write( "    sprintf(foo, \"%x\", i);
\n" );
document.write( "    total_ones += count_ones(foo);
\n" );
document.write( "  }\r
\n" );
document.write( "\n" );
document.write( "  printf(\"Total 1's written = %d\n\", total_ones);\r
\n" );
document.write( "\n" );
document.write( "  return 0;    
\n" );
document.write( "}
\n" );
document.write( "  \n" );
document.write( "
\n" );