I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder by division. Is it possible in MATLAB?
12 views (last 30 days)
Show older comments
I want to show that 17^21 + 19^21 is divisible by 36 by actual computation of the integers and getting the remainder and quotient by division. Is it possible in MATLAB? I know to prove by algebra. But I want to compute the actual values. My machine is 64 bit. uint64 saturates for these numbers and you dont get the exact values.
3 Comments
John D'Errico
on 1 Oct 2015
@Jon - Sorry, but you are simply wrong here. Those numbers overflow the precision available to a double.
Jon
on 2 Oct 2015
Technically nothing I stated was wrong, but I concede I had no business answering this question. Nice answer below.
Answers (2)
John D'Errico
on 1 Oct 2015
Jon was wrong in his comment. Why? I'll show the true answer using my vpi toolbox.
vpij(17)^21 + vpij(19)^21
ans =
783301429606381938554583636
See that the number is large. Larger than you can store in a double. The limit of a double to represent a number as a flint (a floating point number that represents an exact integer, and does so with no error) is 2^53 - 1.
log2((17)^21 + (19)^21)
ans =
89.34
In fact, the above shows the number is too large to be stored in a uint64, which would be limited to 64 bits.
Is it divisible by 36? Yes. Again, my vpi toolbox gives a result that you can trust.
mod(vpi(17)^21 + vpi(19)^21,36)
ans =
0
Can we know this is true using only arithmetic based on doubles? Yes. It is not even that terribly difficult, just a short loop.
m17 = 1;
m19 = 1;
for i = 1:21
m17 = mod(m17*17,36);
m19 = mod(m19*19,36);
end
mod(m17 + m19,36)
ans =
0
So clearly this is quite doable using only small integers and a short loop, all of which numbers fit easily into a double. In fact, we could have done the computation using uint16 integers, since nothing in that computation could possibly ever be larger than 18*19+16*17=614.
Had the exponent been larger, it is actually possible to do the computation efficiently in O(log2( p)), where p is the exponent. Of course, the loop I wrote above is only O( p), so not as good if p were immensely large.
0 Comments
Walter Roberson
on 1 Oct 2015
John D'Errico will probably mention his Variable Precision Integer package from the File Exchange.
You can also proceed using the Symbolic Toolbox:
S = sym(17)^21 + sym(19)^21;
mod(S, 36)
1 Comment
John D'Errico
on 1 Oct 2015
Edited: John D'Errico
on 1 Oct 2015
:)
Or its successor, vpij. But you can also do it using uint16 integers.
See Also
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!