document.write( "<A HREF=/cgi-bin/jump-to-question.mpl?question=1210170>Question 1210170</A>: <I><SPAN STYLE=\"word-break: break-all;\"> How many zeroes do we write when we write all the integers from 1 to 625 in base 4? </SPAN>\n" );
document.write( "</I><HR><TABLE width=100%><TR><TD><B><A HREF=http://www.algebra.com/>Algebra.Com's</A> Answer #851437 by </B><A HREF=/tutors/aboutme.mpl?userid=CPhill><B>CPhill(1959)</B></A><img src=\"/images/stars/stars-12.gif\" alt=\"\" >&nbsp;<A HREF=/tutors/aboutme.mpl?userid=CPhill><IMG SRC=http://www.algebra.com/images/aboutme-small.gif BORDER=0 alt=\"About Me\" VALIGN=MIDDLE></A>&nbsp;<IMG SRC=http://www.algebra.com/cgi-bin/show-face.mpl?user=CPhill><BR>You can <A HREF=\"/cgi-bin/embed-solution.mpl?show=1&solution=851437\">put this solution on YOUR website!</A><BR><SPAN STYLE=\"word-break: break-all;\"> Let's solve this problem by analyzing the number of zeroes in each place value when writing the numbers from 1 to 625 in base 4.\r<BR>\n" );
document.write( "\n" );
document.write( "**1. Convert 625 to Base 4**\r<BR>\n" );
document.write( "\n" );
document.write( "* $625 \div 4 = 156$ remainder 1<BR>\n" );
document.write( "* $156 \div 4 = 39$ remainder 0<BR>\n" );
document.write( "* $39 \div 4 = 9$ remainder 3<BR>\n" );
document.write( "* $9 \div 4 = 2$ remainder 1<BR>\n" );
document.write( "* $2 \div 4 = 0$ remainder 2\r<BR>\n" );
document.write( "\n" );
document.write( "So, $625_{10} = 21301_4$. This means the largest base 4 number we're dealing with has 5 digits.\r<BR>\n" );
document.write( "\n" );
document.write( "**2. Analyze Place Values**\r<BR>\n" );
document.write( "\n" );
document.write( "We need to count the number of zeroes in each place value (units, fours, sixteens, sixty-fours, and two-hundred-fifty-sixes).\r<BR>\n" );
document.write( "\n" );
document.write( "* **Units Place (4^0):**<BR>\n" );
document.write( "    * Numbers ending in 0 in base 4 are multiples of 4.<BR>\n" );
document.write( "    * From 1 to 625, there are $\lfloor 625/4 \rfloor = 156$ multiples of 4. So, there are 156 zeroes in the units place.<BR>\n" );
document.write( "* **Fours Place (4^1):**<BR>\n" );
document.write( "    * We are looking for numbers with a 0 in the fours place.<BR>\n" );
document.write( "    * We look at the pattern in base 4: \_ \_ 0 \_<BR>\n" );
document.write( "    * For every 16 numbers, there are 4 numbers with 0 in the fours place.<BR>\n" );
document.write( "    * From 1 to 624, we have $624/16 = 39$ sets of 16. In each set, there are 4 zeroes. So, $39 \times 4 = 156$ zeroes.<BR>\n" );
document.write( "    * 625 is $21301_4$ so it also includes one zero in the fours place.<BR>\n" );
document.write( "    * total 156+1=157 zeroes<BR>\n" );
document.write( "* **Sixteens Place (4^2):**<BR>\n" );
document.write( "    * We are looking for numbers with a 0 in the sixteens place.<BR>\n" );
document.write( "    * We look at the pattern in base 4: \_ 0 \_ \_<BR>\n" );
document.write( "    * For every 64 numbers, there are 16 numbers with 0 in the sixteens place.<BR>\n" );
document.write( "    * From 1 to 576 we have $576/64 = 9$ sets of 64. In each set there are 16 zeroes.<BR>\n" );
document.write( "    * $9 \times 16 = 144$ zeroes.<BR>\n" );
document.write( "    * From 577 to 625, the numbers in base 4 are:<BR>\n" );
document.write( "    * 21001, 21002, 21003, 21010, 21011, 21012, 21013, 21020, 21021, 21022, 21023, 21030, 21031, 21032, 21033, 21100, 21101, 21102, 21103, 21110, 21111, 21112, 21113, 21120, 21121, 21122, 21123, 21130, 21131, 21132, 21133, 21200, 21201, 21202, 21203, 21210, 21211, 21212, 21213, 21220, 21221, 21222, 21223, 21230, 21231, 21232, 21233, 21300, 21301.<BR>\n" );
document.write( "    * There are 13 more numbers with a zero in the sixteens place.<BR>\n" );
document.write( "    * 144+13 = 157 zeroes.\r<BR>\n" );
document.write( "\n" );
document.write( "* **Sixty-fours Place (4^3):**<BR>\n" );
document.write( "    * We are looking for numbers with a 0 in the sixty-fours place.<BR>\n" );
document.write( "    * We look at the pattern in base 4: 0 \_ \_ \_<BR>\n" );
document.write( "    * For every 256 numbers, there are 64 numbers with 0 in the sixty-fours place.<BR>\n" );
document.write( "    * From 1 to 512, there are $512/256 = 2$ sets of 256. In each set, there are 64 zeroes.<BR>\n" );
document.write( "    * $2 \times 64 = 128$ zeroes.<BR>\n" );
document.write( "    * From 513 to 625, we have<BR>\n" );
document.write( "    * 20001 to 21301.<BR>\n" );
document.write( "    * 20001, 20002, 20003, 20010, 20011, 20012, 20013, 20020, 20021, 20022, 20023, 20030, 20031, 20032, 20033, 20100, 20101, 20102, 20103, 20110, 20111, 20112, 20113, 20120, 20121, 20122, 20123, 20130, 20131, 20132, 20133, 20200, 20201, 20202, 20203, 20210, 20211, 20212, 20213, 20220, 20221, 20222, 20223, 20230, 20231, 20232, 20233, 21000, 21001, 21002, 21003, 21010, 21011, 21012, 21013, 21020, 21021, 21022, 21023, 21030, 21031, 21032, 21033.<BR>\n" );
document.write( "    * We have 49 numbers with a zero in the 64's place.<BR>\n" );
document.write( "    * 128+49=177 zeroes\r<BR>\n" );
document.write( "\n" );
document.write( "* **Two-hundred-fifty-sixes Place (4^4):**<BR>\n" );
document.write( "    * We are looking for numbers with a 0 in the 256's place.<BR>\n" );
document.write( "    * We look at the pattern in base 4: 0 \_ \_ \_ \_<BR>\n" );
document.write( "    * From 1 to 255, there are 255 numbers and no numbers with a zero in the 4^4 position.<BR>\n" );
document.write( "    * From 256 to 511 we have 10000 to 13333, and no zeros in the 256 position.<BR>\n" );
document.write( "    * From 512 to 625, we have 20000 to 21301. all of these numbers have a 2 in the 256's place, and no zeroes.<BR>\n" );
document.write( "    * 0 zeroes.\r<BR>\n" );
document.write( "\n" );
document.write( "**3. Total Zeroes**\r<BR>\n" );
document.write( "\n" );
document.write( "* Total zeroes = 156 + 157 + 157 + 177 + 0 = 647.\r<BR>\n" );
document.write( "\n" );
document.write( "**Therefore, we write 647 zeroes when writing all the integers from 1 to 625 in base 4.**<BR>\n" );
document.write( " </SPAN>\n" );
document.write( "</TD></TR></TABLE>\n" );