In my previous post I detailed a program for obtaining the remainder when a number like 4593 is divided by 7. I now want to show how this works and how we can find remainders even when the numbers exceed the range of input of the fx-50F.
Let's start by finding the remainder when 4593 is divided by 7. On executing the program the display shows A? A is the divisor and so input 7 and press [EXE]. Next X? is displayed. The digits of 4593 are entered here and so begin with the digit furthest to the right and input 3 and press [EXE]. Continue by entering 9, then 5, and then 4 in a similar fashion. Once 4 has been processed X? will be displayed again and to notify the program that all the digits of the number have been entered, input -1 and press [EXE]. The program then displays the value of memory C which is the result, 1. This is as expected. The remainder on dividing 4593 by 7 is 1.
In an earlier post I also showed that the 21 digit number 122130132904968017083 leaves remainder 12 when divided by 41. To confirm this we can run the program again. Enter 41 for A and then process the digits from right to left starting with 3. We obtain the result that C displays 12 as expected. Note that 21 digits exceeds the limit of 15 digits that can be stored in the fx-50F.
Finally, I return to prove that Frank Cole's calculation that the Mersenne number 147573952589676412927 is the product 193707721 × 761838257287. First, we show that 193707721 divides this number. We run the program again with 193707721 entered for A and then the 21 digits of the number 147573952589676412927 entered from right to left, finishing with -1 to terminate the input. The result is remainder 0 which is as expected since 193707721 is a factor. Secondly we run the program again with 761838257287 entered for A and then the 21 digits of 147573952589676412927. Again the remainder is 0 which shows that 761838257287 does divide 147573952589676412927.
Tuesday, 17 March 2015
Tuesday, 3 March 2015
Remainder on division - the program
I discussed the logic for this program in a previous blog. Here is the logic converted into a program for the fx-50F:-
This program is 104 steps in length.
1→B:0→C:10→D:?→A:While D≥A:D-A→D:WhileEnd:Lbl
1:?→X:X=-1=>Goto 2:While X≥A:X-A→X:WhileEnd:C+BX→C:While C≥A:C-A→C:WhileEnd:DB→B:While B≥A:B-A→B:WhileEnd:Goto 1:Lbl 2:C▲
This program is 104 steps in length.
Friday, 27 February 2015
Remainder on division - comments on the logic
In my previous post I presented some logic for obtaining the remainder when a number like 4593 is divided by 7. I now want to go through how this logic works.
Some initial values are first stored in memory locations B, C and D and the use of these memories is explained as we go along. The divisor (in our example 7) is input in memory A and remains fixed. Memory D contains the common factor of 10 in our process and the first while loop finds the remainder when 10 is divided by 7 and the result, 3, is stored in D.
The first digit of our number (in our example this is 3) is input after label 1. Essentially this is the main loop of our program. The digits of 4593 are entered reading from right to left and when the last digit has been read, the process is terminated by entering -1 in X.
Each digit is processed as follows. Firstly, the initial while loop determines the remainder on dividing X by A. For the first digit in our example this is the remainder on dividing 3 by 7 (which is 3). Each time we process a new digit of our number 4593 we add to memory C the product of X (the remainder on dividing our digit by 7) and the remainder on dividing the power of 10 by 7 stored in B. For example, for the third digit 5, B at this stage would contain the remainder on dividing 100 by 7, namely 2. We then calculate the remainder on dividing C by A in the following while loop.
Finally, before going on to input the next digit we calculate the remainder on dividing the next power of 10 by A.
When the last digit has been processed, the required remainder in C is displayed.
Some initial values are first stored in memory locations B, C and D and the use of these memories is explained as we go along. The divisor (in our example 7) is input in memory A and remains fixed. Memory D contains the common factor of 10 in our process and the first while loop finds the remainder when 10 is divided by 7 and the result, 3, is stored in D.
The first digit of our number (in our example this is 3) is input after label 1. Essentially this is the main loop of our program. The digits of 4593 are entered reading from right to left and when the last digit has been read, the process is terminated by entering -1 in X.
Each digit is processed as follows. Firstly, the initial while loop determines the remainder on dividing X by A. For the first digit in our example this is the remainder on dividing 3 by 7 (which is 3). Each time we process a new digit of our number 4593 we add to memory C the product of X (the remainder on dividing our digit by 7) and the remainder on dividing the power of 10 by 7 stored in B. For example, for the third digit 5, B at this stage would contain the remainder on dividing 100 by 7, namely 2. We then calculate the remainder on dividing C by A in the following while loop.
Finally, before going on to input the next digit we calculate the remainder on dividing the next power of 10 by A.
When the last digit has been processed, the required remainder in C is displayed.
Wednesday, 25 February 2015
Remainder on division - the logic
In my previous post I described a method for calculating the remainder on dividing one integer by another. I now give the logic that can
be used to solve this problem on a programmable calculator.
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
Store 1 in B
Store 0 in C
Store 10 in D
Input A
While D ≥ A
Store D-A in D
WhileEnd
Label 1
Input X
If X=-1 then
Goto Label 2
EndIf
While X ≥ A
Store X-A in X
WhileEnd
Store C+BX in C
While C ≥ A
Store C-A in C
WhileEnd
Store DB in B
While B ≥ A
Store B-A in B
WhileEnd
Goto Label 1
Label 2
Display C
Tuesday, 24 February 2015
Remainder on division - methodology
So how do we go about creating a program on the fx-50F which can calculate the remainder on dividing one integer by another? Let's go back to the example of dividing 4593 by 7. We can write this number as
4593=4000+500+90+3=4x1000+5x100+9x10+3x1
Suppose we want to calculate the remainder of 90 on division by 7. We find that 90=12x7+6 and so the remainder is 6. Alternatively we could have seen that 9=1x7+2 and 10=1x7+3 and 2x3=6. This means that we could have found the remainder we wanted by multiplying the remainders of dividing 9 and 10 by 7. A similar rule applies for addition. Suppose we want the remainder when 590 is divided by 7. This is 2 since 590=84x7+2. However, 500=71x7+3 and, as we have just seen, 90=12x7+6 and 3+6=9 and 9=1x7+2. The moral of this is that we don't have to divide the complete number 4593 by 7 but divide it in parts and work with remainders.
So how do we proceed in a way which makes it easy for a programmable calculator? Let's start with the right-most digit 3 and record the power of 10, namely 0, that goes with it. 10 to the power 0 is 1 and 1 divided by 7 leaves remainder 1 (since 1=0x7+1). 3 divided by 7 leaves remainder 3 (again since 3=0x7+3). Multiplying remainders gives 3x1=3.
Now before going on to the next digit to the left, 9, we note that the powers of 10 that go with each digit increase by 1 for each new digit we encounter. For example 1000=10x100. So rather than calculate the remainder of 1000 divided by 7 we multiply the remainder of 10 divided by 7 (i.e. 3) and the remainder of 100 divided by 7 (i.e. 2) that we calculated previously. So corresponding to the powers of 10 of 0, 1, 2, 3, ... the remainders are 1, 3, 3x3=9 which is 2, 3x2=6, etc.
Now going on to the next digit 9 we have 9 divided by 7 leaves remainder 2 and as, we have seen, the remainder for 10 divided by 7 is 3 and so 2x3=6. Adding this to the remainder for the first digit gives 6+3=9 and 9 divided by 7 leaves remainder 2.
The next digit is 5 and 5 divided by 7 leaves remainder 5. The factor of 100 divided by 7 leaves remainder 2 and 5x2=10. 10 divided by 7 leaves remainder 3 and adding this to the remainder for our first two digits gives 3+2=5.
Finally, the last digit is 4 and 4 divided by 7 leaves remainder 4. The factor of 1000 divided by 7 leaves remainder 6 (as we discussed above) and 4x6=24. 24 divided by 7 leaves remainder 3 and adding this to the remainder for our first three digits gives 5+3=8 and 8 divided by 7 leaves remainder 1. This is our final result, that is 4593 divided by 7 leaves remainder 1, as expected.
This may seem like a tedious way of going about things, but with a pocket programmable calculator the digits can be entered one by one and the time to compute the intermediate remainders is very quick and hardly interferes with the input process. The advantage is that this keeps the size of the computations down to manageable amounts and allows an integer of indeterminate length to be entered and divided (the limit being only how long before you get bored of keying in digits!).
4593=4000+500+90+3=4x1000+5x100+9x10+3x1
Suppose we want to calculate the remainder of 90 on division by 7. We find that 90=12x7+6 and so the remainder is 6. Alternatively we could have seen that 9=1x7+2 and 10=1x7+3 and 2x3=6. This means that we could have found the remainder we wanted by multiplying the remainders of dividing 9 and 10 by 7. A similar rule applies for addition. Suppose we want the remainder when 590 is divided by 7. This is 2 since 590=84x7+2. However, 500=71x7+3 and, as we have just seen, 90=12x7+6 and 3+6=9 and 9=1x7+2. The moral of this is that we don't have to divide the complete number 4593 by 7 but divide it in parts and work with remainders.
So how do we proceed in a way which makes it easy for a programmable calculator? Let's start with the right-most digit 3 and record the power of 10, namely 0, that goes with it. 10 to the power 0 is 1 and 1 divided by 7 leaves remainder 1 (since 1=0x7+1). 3 divided by 7 leaves remainder 3 (again since 3=0x7+3). Multiplying remainders gives 3x1=3.
Now before going on to the next digit to the left, 9, we note that the powers of 10 that go with each digit increase by 1 for each new digit we encounter. For example 1000=10x100. So rather than calculate the remainder of 1000 divided by 7 we multiply the remainder of 10 divided by 7 (i.e. 3) and the remainder of 100 divided by 7 (i.e. 2) that we calculated previously. So corresponding to the powers of 10 of 0, 1, 2, 3, ... the remainders are 1, 3, 3x3=9 which is 2, 3x2=6, etc.
Now going on to the next digit 9 we have 9 divided by 7 leaves remainder 2 and as, we have seen, the remainder for 10 divided by 7 is 3 and so 2x3=6. Adding this to the remainder for the first digit gives 6+3=9 and 9 divided by 7 leaves remainder 2.
The next digit is 5 and 5 divided by 7 leaves remainder 5. The factor of 100 divided by 7 leaves remainder 2 and 5x2=10. 10 divided by 7 leaves remainder 3 and adding this to the remainder for our first two digits gives 3+2=5.
Finally, the last digit is 4 and 4 divided by 7 leaves remainder 4. The factor of 1000 divided by 7 leaves remainder 6 (as we discussed above) and 4x6=24. 24 divided by 7 leaves remainder 3 and adding this to the remainder for our first three digits gives 5+3=8 and 8 divided by 7 leaves remainder 1. This is our final result, that is 4593 divided by 7 leaves remainder 1, as expected.
This may seem like a tedious way of going about things, but with a pocket programmable calculator the digits can be entered one by one and the time to compute the intermediate remainders is very quick and hardly interferes with the input process. The advantage is that this keeps the size of the computations down to manageable amounts and allows an integer of indeterminate length to be entered and divided (the limit being only how long before you get bored of keying in digits!).
Thursday, 19 February 2015
Remainder on division
One function that appears to be missing from the fx-50F Plus is finding the remainder when one integer is divided by another. For example, what is the remainder when 4593 is divided by 7, or putting this another way, what is 4593 congruent to modulo 7? The fx-50F does have the ability to calculate fractions and if you key in 4593 [a b/c] 7 [EXE] you obtain 656_1_7 which shows that 4593=656x7+1, that is the remainder when 4593 is divided by 7 is 1. Equivalently 4593 is congruent to 1 modulo 7. You have to be wary that if your divisor is not prime, then you may have to adjust the numerator of your fraction accordingly to obtain the correct remainder. For example, if you enter 4593 [a b/c] 21 [EXE] you obtain 218_5_7. Here the remainder is not 5 but 5x3=15 since the denominator is 7, not 21, in the resulting fraction. You need to multiply the fraction 5/7 top and bottom by 3 to get the correct result, that is 4593=218x21+15.
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
An alternative method is, of course, to carry out the division in decimals 4593/7=656.1428571. If you then take this number, subtract 656 and multiply by 7 you obtain remainder 1. This seems simple enough. But what happens if you want to do division on very large numbers? It all starts to get a bit messy and inaccurate, partly because of the number of digits that the fx-50F can accurately hold and partly because only ten digits are displayed on the screen.
For example, Edouard Lucas had shown in 1876 that the number 267-1 =147,573,952,589,676,412,927 is not prime but no one knew what its factors were. In 1903 Frank Nelson Cole (1861-1926) famously gave a presentation to the American Mathematical Society where he proceeded to calculate, in silence, 267-1 on side of the blackboard and then, on the other, the result, by hand, of 193,707,721 × 761,838,257,287. Cole, having demonstrated that the two numbers were equal, sat down, not uttering a word. He received a standing ovation!
What I would like to do is to demonstrate that we can show that either of these factors will divide this number by creating a program that will calculate that the remainder on division is zero. Furthermore, this program will cope with a natural number of any length (though, the divisor will have to less than the largest positive integer that the calculator can accurately hold).
Monday, 5 January 2015
The largest known prime number
The largest known prime as of the 5th January 2015 is the 17,425,170 decimal digit Mersenne prime 257885161-1. Assuming that you could write at one digit a second, it would take you about six and a half months even to write this number down. I want to demonstrate the power of the exponentiation modulo n program that I wrote for the Casio fx-50F by calculating some of the last digits of this number.
Firstly, though, I will look at some Mersenne primes that we can write down relatively easily. M31 can be computed on the fx50F and is the number 231-1=2147483647. We can verify that the last digit is 7 by computing M31 modulo 10. What we actually do is compute 231 (mod 10) and subtract 1 (mod 10) which comes to the same thing. Running the exponentiation program with X=2, A=31 and B=10 gives the result D=8. That is 231 (mod 10) is congruent to 8 (mod 10). Subtracting 1 (mod 10) from this gives us 7, which is the anticipated last digit of M31.
M127 is the number 2127-1=170141183460469231731687303715884105727. Running the program with X=2, A=127 and B=10 gives the result D=8 from which we again deduce that the last digit is 7.
So what about M57885161? Can the program compute the last decimal digit of such a large number? Running the program with X=2, A=57885161 and B=10 gives D=2 after 27 seconds of processing. This means that the last digit of this number is 1. We can also find the last two digits by computing M57885161 (mod 100) and after 2 minutes 47 seconds the program calculates these to be 51. A further calculation (mod 1000) lasting 23 minutes shows that the last three digits are 951.
So what's the next largest Mersenne number? The next largest prime after 57885161 is 57885167 and so 257885167-1 may or may not be a prime. If it isn't prime then it will have a factor which is a number of the form 115770334n+1 where n is a positive integer. Good luck with trying out your long division!
Firstly, though, I will look at some Mersenne primes that we can write down relatively easily. M31 can be computed on the fx50F and is the number 231-1=2147483647. We can verify that the last digit is 7 by computing M31 modulo 10. What we actually do is compute 231 (mod 10) and subtract 1 (mod 10) which comes to the same thing. Running the exponentiation program with X=2, A=31 and B=10 gives the result D=8. That is 231 (mod 10) is congruent to 8 (mod 10). Subtracting 1 (mod 10) from this gives us 7, which is the anticipated last digit of M31.
M127 is the number 2127-1=170141183460469231731687303715884105727. Running the program with X=2, A=127 and B=10 gives the result D=8 from which we again deduce that the last digit is 7.
So what about M57885161? Can the program compute the last decimal digit of such a large number? Running the program with X=2, A=57885161 and B=10 gives D=2 after 27 seconds of processing. This means that the last digit of this number is 1. We can also find the last two digits by computing M57885161 (mod 100) and after 2 minutes 47 seconds the program calculates these to be 51. A further calculation (mod 1000) lasting 23 minutes shows that the last three digits are 951.
So what's the next largest Mersenne number? The next largest prime after 57885161 is 57885167 and so 257885167-1 may or may not be a prime. If it isn't prime then it will have a factor which is a number of the form 115770334n+1 where n is a positive integer. Good luck with trying out your long division!
Subscribe to:
Posts (Atom)