Devise an algorithm that determines whether a given positive integer N is divisible by 13, and if NOT, to find the remainder.
N can contain up to 20,220 digits.
Note: Simply dividing by 13 or, performing long division by 13 is NOT permissible.
(In reply to
re: No Subject by Charlie)
To test the viability up to 20,220 digits, this driver
clearvars
n='';
for i=1:20220
n=[n char(string(randi(10)-1))];
end
n=sym(n);
for i=n:n+100
[a b]=rem13(i);
disp([a b])
end
creates a 20,220-digit number made up of random digits and then uses the algorithm on that number and the next 100 numbers (still for course of 20,220 digits each). The results are tabulated below. Of course the numbers thamselves are not listed for an obvious reason. But the sequence of remainders is consistent.
The list is followed by Matlab's own computation of n mod 13, and it agrees with the first line of the tabulation.
div
t/f rem
>> divisibilityBy13
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
0 3
0 4
0 5
0 6
0 7
0 8
0 9
0 10
0 11
0 12
1 0
0 1
0 2
>> mod(n,13)
ans =
6
While the algorithm took about 9 seconds for each 20,220-digit number, the mod function took a fraction of a second.
|
|
Posted by Charlie
on 2022-04-15 14:48:27 |
Test for 20,220-digit numbers
