Related Links (Outside this Site)

---

(2002-05-22) [Anonymous query collected by Site's search engine.]
If you multiply together all the odd numbers from 1 to 999, what will be the final digit? and why?

The answer is 5, because the product of a decimal number ending in 5 and any odd number is a number ending in 5.  Your 500-factor product ends with a 5.

As this example is too simple, let's examine a slightly less trivial one:

What's the final digit of the product of all the odd numbers not divisible by 5 from 1 to 999?

This is an example of what's called modular arithmetic: The remainder in the division by some fixed modulus of a sum, a difference or a product depends only on the remainders for both operands. Here, the modulus is 10 and each remainder is simply equal to the last decimal digit of the number involved.

So, the product of 4 decimal numbers ending with 1, 3, 7, and 9, is a number ending with 9. If you multiply together an even number of such products, the result ends in 1 (because if you multiply two such products, the result ends in 1, the same trailing digit as for the ordinary product of 9 and 9, which is 81).

As our product of 400 factors is, in fact, obtained as the product of 100 such 4-tuples, its final digit is thus 1 as well.

How do I find the last [least significant] digits of such huge numbers?

Modular arithmetic is, again, the key to this question: If you want the last 5 digits of a product, use modular arithmetic modulo 100000. A regular pocket calculator with 10-digit accuracy will give an exact result for the product of any pair of two 5-digit numbers, which is what any integer reduces to modulo 100000... This is all you need to find the last 5 digits of the above products of 500 or 400 factors... With less modest means [a precision of several hundred digits], we found that...

• The above product of 500 factors ends with: ...821809277089697420848324327380396425724029541015625.
• The above product of 400 factors ends with: ...251632034302682442928182392469846896720096892926001.

 

What about the leading digits?   [most significant digits]

If you want a few leading digits, as well as the number of digits in the result, the easiest way is to compute the decimal logarithm of such a huge product as the sum of the decimal logarithms of its factors. For the 500-factor product, we find a decimal logarithm of 1283.0032378550076961..., corresponding to a 1284-digit number starting with 100748329763750854004...  For the 400-factor product, we find a decimal logarithm of 1026.28235200247947115..., corresponding to a 1027-digit number starting with 1915808088370632042699972791343618517...

We may summarize both of the above approaches for either product thusly:
500-factor product of 1284 digits:  10074832976375... ...724029541015625.
400-factor product of 1027 digits:  19158080883706... ...720096892926001.

---

Iggy (2004-03-31; e-mail)
What two integers without zero digits have a product of 1000 000 000 ?

Answer:  512 ´ 1953125   =   1000000000.

The first number is the ninth power of 2, the second is the ninth power of 5.  This pair is the only [positive] solution, because neither factor could have both a 2 and a 5 in its prime factorization, or else it would be a multiple of 10 and would thus have a 0 as its last digit, which is ruled out.

Generalization :

We may wonder what powers of 10 are products of two integers without any zero digits.  For large numbers, this is very unlikely because there will normally be 10% of zeroes among many random digits...  In fact, there seems to be only 11 possibilities, of which the above is the third largest.  Namely:

10 0   =           1 x 1
10 1   =           2 x 5
10 2   =           4 x 25
10 3   =           8 x 125
10 4   =          16 x 625
10 5   =          32 x 3125
10 6   =          64 x 15625
10 7   =         128 x 78125
10 9   =         512 x 1953125
10 18  =      262144 x 3814697265625
10 33  =  8589934592 x 116415321826934814453125

The probability is roughly (0.9)ⁿ that the n^th power of 10 would yield a solution.  So, the expected number of solutions above the n^th power of 10 is something like  10 (0.9)ⁿ.  Since we've actually checked that there's no other solution below n = 1500, we can be very confident that we've not missed anything...

---

(Peter of Portland, OR. 2000-10-10)
What is the divisibility rule of 13?
(D. S. of Hurricane, WV. 2000-11-29)
What is the divisibility rule for 7?

Recall that a number is divisible by 3 or 9 iff (if and only if) the sum of its digits is. It is divisible by 11 iff the difference between the sum of its odd digits (units, hundreds, etc.) and the sum of its even digits (tens, thousands, etc.) is so divisible.

The "quick tests" of divisibility by 7 or 13 are somewhat more complex. Strangely enough, these two are very strongly related (see below for an explanation). The basic process is to form an alternating sum of digits using only every third digit:

From the rightmost digit (the units), you subtract the 4^th rightmost (the thousands), add the 7^th, subtract the 10^th, add the 13^th, etc. This gives you the first of three numbers, call this result X.

Do the same thing starting with the second rightmost digit (the tens), subtract the 5^th, add the 8^th, subtract the 11^th, etc. This gives you a second number, say Y.

Finally, you start with the 3^rd rightmost (the hundreds), subtract the 6^th, add the 9^th, subtract the 12^th, add the 15^th, etc. This gives you a third number, say Z.

Now, compute the quantity X+10Y+9Z (which is easy to obtain as X-Z+10(Y+Z), with just three additions and one trivial multiplication by 10). The original number is divisible by 13 iff this quantity is divisible by 13. The original number is divisible by 7 iff this quantity is divisible by 7.

It's remarkable that the same test works for both 7 and 13! The reason is that 7´13=91=100-10+1. We are really dealing with divisibility by 91 here!

Proof :

To see more clearly what happens, consider some base of numeration B, which may or may not be equal to ten, and consider arithmetic modulo M=B²-B+1 (the expression "X mod M" denotes the remainder when X is divided by M):

• (1 mod M) is 1,
• (B mod M) is B,
• (B² mod M) is B-1,
• (B³ mod M) is M-1  (equivalent to "-1" modulo M, that's the ticket ! )
• (B⁴ mod M) is M-B,
• (B⁵ mod M) is M-(B-1) and
• (B⁶ mod M) is 1, after which the sequence repeats with period 6.

Therefore, using for base B the alternating sums X,Y and Z defined above for base ten, we see that the quantity X+BY+(B-1)Z is within a multiple of M of the number whose divisibility by M is being checked. 

In the octal system, for example, the same divisibility test (based on the quantity X+8Y+7Z) works for 3 and 19. Just because 3 times 19 is 57=8²-8+1.

---

(John of Middletown, NJ. 2000-10-14)   Lucky 7's
Any integer N>0 divides a number whose digits include only 7's and 0's.

Let P be the decimal period of the number  9N  (i.e., digits ultimately repeat with period P in the decimal expansion of 1/9N).  We have a relation of the form:

1 / 9N   =   K / 999...99000...00

Since the number 9N divides the number which consists of P nines followed by a certain number J of zeroes,  N divides the number consisting of P ones followed by J zeroes, and also the integer composed of P sevens followed by J zeroes.

---

(S. G.. of San Marcos, TX. 2000-11-22)
How do I represent a floating-point number with hexadecimal normalization? I can't figure out how to convert exponent and mantissa, which should both be expressed in binary.
 
mrjohngribben (2001-08-10)
How would I write a fractional number in a base other than ten?
What is pi in hexadecimal (base sixteen)?

You can't "convert" mantissa and exponent separately. Look at the represented number itself and express it in binary.

What you want is probably "binary floating-point" (it's certainly possible to have "hexadecimal floating-point", but it's unused in practice). A binary floating-point number may be written out with hexadecimal digits for convenience but the exponent still refers to a power of 2 not 16 (again, pure hexadecimal is possible, it's just that we don't use it).

Take p = 3.14159265... for example. Its first two bits are 1 and 1 (the binary representation of 3), the next bit is the integral part of twice 0.1415926... namely 0.2831853... so it's 0. Repeat the process to get each successive bit by doubling the previous fractional part: You get 0 with 0.56637061..., 1 with 1.3127412..., 0 with 0.265482457... etc. All told, the (fixed-point) binary representation of p is

pi = 11.0010 0100 0011 1111 0110 1... 

You may write this in hexadecimal as 3.243F6... if you wish.

What's the binary floating-point representation of p ? Well, do just what you would do in decimal: Shift the pattern so there's just one nonzero digit before the "binary" point (resist the temptation to call it a "decimal" point) and record as "exponent" the length of the shift (that's a negative number if you had to shift the pattern to the left). For p, you shift the bit pattern only once to the right, so the exponent is +1 and the pattern is

pi = 1.1001 0010 0001 1111 1011 01... (two)^(+1)

That's the proper binary floating-point representation of p ("two" is spelled out to avoid using multiple bases of numeration in the same expression, even though "2" would not be ambiguous "16" would be in the discussion that follows).

The commonly used hexadecimal notation is simply a shorthand for the above, but the exponent still represents a power of two (so the first digit before the floating point is always a 1 and is therefore actually omitted from many/most/all internal representations used in computers):

pi = 1.921FA.. (two)^(+1)

What if you wanted everything to use base sixteen? Well, you'd have to shift the bit pattern by a multiple of 4 only (and count one unit of the exponent for each "nybble/nibble" of 4 bits so shifted). For p, this means no shift at all and we have the following purely hexadecimal representation of p (I won't repeat it enough, this is not the one used in computers):

pi = 3.243F6... (sixteen)^(0) 

What if you have to convert a large decimal floating point number?  Well, like it or not, what you have to do is basically work out the fixed-point representation and express it in binary (or hexadecimal) using a procedure similar to the above.  For example, to "convert"  1.965032919280624´10⁷, just use the above (tedious) procedure to express  19560329.19280624  in binary.

---

( T. D. of Fairbanks, AK. 2000-12-04)
How do I find square roots without the use of a calculator, especially when the square root will contain a decimal point?
( J. D. of Cape Coral, FL. 2000-12-07)
How do I extract the square root of a number?

It works a little bit like a long division with two basic differences:

1. Instead of one digit at a time, you handle "slices" of two digits at a time  (the decimal point separates two such slices).
2. You get each new digit by trying at each step to "extend" twice the previously found root with another digit so that the product of this extension by the (largest possible) new digit does not exceed the previously computed remainder.

To make this clear, let's just compute the square root of 2:

1. Remainder is 2, Root is 0, DoubleRoot is 0.
   The largest digit "?" which is such that "0?" times "?" is no greater than 2 happens to be 1 (save this as the first digit in the square root). "01" times "1" is 1, which I subract from 2, the result is 1, which gets augmented by the "next slice" of unprocessed digits, namley "00". So, the new remainder is 100.
2. Remainder is 100, Root is 1, DoubleRoot is 2.
   What's the largest digit such that "2?" times "?" does not exceed 100. Well it's 4 (save this as the second digit in the root). "24" times "4" is 96, which I subtract from 100 and augment with the next slice of "00" digits to get 400 as the new remainder.
3. Remainder is 400, Root is 1.4, DoubleRoot is 28.
   The largest digit such that "28?" times "?" does not exceed 400 is 1 (which is thus our next digit). The new remainder is 400-281=119 augmented by the next "00"; 11900 is the new remainder.
4. Remainder is 11900, Root is 1.41, DoubleRoot is 282.
   The next digit is 4 for which "282?" times "?" is 11296. 11900-11296 is 604; new remainder is thus 60400.
5. Remainder is 60400, Root is 1.414, DoubleRoot is 2828.
   The next digit is 2 for which "2828?" times "?" is 56564. 60400-56564 is 3836; new remainder is thus 383600.
6. Remainder is 383600, Root is 1.4142, DoubleRoot is 28284.
   The next digit is 1 for which "28284?" times "?" is 282841. 383600-282841 is 100759; new remainder is thus 10075900.
7. Remainder is 10075900, Root is 1.41421, DoubleRoot is 282842.
   The next digit is 3 ... etc.

The square root of 2 is: 1.414213562373095048801688724209698...

Below is a binary version of the above algorithm, implemented (and optimized) in 68000 assembly language.  One aspect of it is simpler than the above:  At each step you only have two choices for what the next (binary) digit is going to be, instead of 10 such choices in the decimal case.  Thus, a simple test suffices (see the BLE instruction below) to make the proper decision...

Such an elementary implementation would allow a 12.66 MHz handheld calculator to extract over 16000 square roots per second...

; (c) 2007 - Gerard Michon
;
; SQRT takes a 31-bit integer (z) from register D3
; and returns the square root (y) and remainder (x)
; in D1 and D0 respectively.  Upon exit, x+y^2 = z :
; D0: 0000 XXXX = Remainder (x)
; D1: 0000 YYYY = Square root (y)
; D2: FFFF FFFF = -1
; D3: ZZZZ ZZZZ = Argument (z) unchanged
;
; BSR SQRT = 752 cycles + twice the count of '1' bits in y.
; Min=752, Max=784 (with 18 cycles for BSR instruction).
;
;                        Time: (in clock cycles)
;
7000 SQRT   MOVEQ  #0,D0     4: Clear x
7200        MOVEQ  #0,D1     4: Clear y
7400        MOVEQ  #0,D2     4: Two 16-bit counters

5E42 AGAIN  ADDQ.W #7,D2     4: Branch 7 times, for 8 loops
4843        SWAP   D3        4: Deal with upper 16 bits first
3003        MOVE.W D3,D0     4: Fetch 16-bit slice

EFC0 LOOP   ROL.L  #2,D0    12: Get 2 more radicand bits
D241        ADD.W  D1,D1     4: Shift root one bit
B041        CMP.W  D1,D0     4: OK to set root's new bit?
6F02        BLE    SKIP     10: No, leave 0 bit as is
5241        ADDQ.W #1,D1     2: Time = 4-2 (branch not taken)
51C2 SKIP   DBRA   D2,LOOP  10: Decrement counter (8 times)
FFF2                         4:
4842        SWAP   D2        4:
4A42        TST.W  D2        4: Already been here?
67E6        BEQ    AGAIN    10: No, do second half
4E75        RTS             14: Time = 16-2 (branch not taken)