perplexus.info :: Algorithms : Divisible by 13

Divisible by 13 (Posted on 2022-04-15)

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.

See The Solution Submitted by K Sengupta

Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)

re: No Subject

| Comment 5 of 11 |

(In reply to No Subject by Larry)

Similar to larry's but keeps repeating the algorithm until the total (larry's temp) is small enough that repeated addition (for negative) or repeated subtraction (for larger than 12) can be used instead of mod function, which is really a remainder after division function.

function [div, r]=rem13(n)

ns=sym(n);

nstr=char(string(ns));

factors = [1,-3,-4,-1,3,4];

loops=0;

while length(nstr)>2 || loops==0

loops=loops+1;

tot=sym(0); f=1;

for i=length(nstr):-1:1

tot=tot+factors(f)*str2double(nstr(i));

f=f+1;

if f>6

f=1;

end

while tot<0

tot=tot+13;

end

nstr=char(string(tot));

end

while tot>12

tot=tot-13;

end

if tot == 0

div=true; r=double(tot);

else

div=false; r=double(tot);

end

driven by

clearvars

for i=[sym('98767676123456666777777534'):sym('98767676123456666777777534')+100]

[a b]=rem13(i);

disp([i a b])

end

if results in

>> divisibilityBy13

    i                       div
                                             t/f 
                                                 remainder

                             
[98767676123456666777777534, 1, 0]
[98767676123456666777777535, 0, 1]
[98767676123456666777777536, 0, 2]
[98767676123456666777777537, 0, 3]
[98767676123456666777777538, 0, 4]
[98767676123456666777777539, 0, 5]
[98767676123456666777777540, 0, 6]
[98767676123456666777777541, 0, 7]
[98767676123456666777777542, 0, 8]
[98767676123456666777777543, 0, 9]
[98767676123456666777777544, 0, 10]
[98767676123456666777777545, 0, 11]
[98767676123456666777777546, 0, 12]
[98767676123456666777777547, 1, 0]
[98767676123456666777777548, 0, 1]
[98767676123456666777777549, 0, 2]
[98767676123456666777777550, 0, 3]
[98767676123456666777777551, 0, 4]
[98767676123456666777777552, 0, 5]
[98767676123456666777777553, 0, 6]
[98767676123456666777777554, 0, 7]
[98767676123456666777777555, 0, 8]
[98767676123456666777777556, 0, 9]
[98767676123456666777777557, 0, 10]
[98767676123456666777777558, 0, 11]
[98767676123456666777777559, 0, 12]
[98767676123456666777777560, 1, 0]
[98767676123456666777777561, 0, 1]
[98767676123456666777777562, 0, 2]
[98767676123456666777777563, 0, 3]
[98767676123456666777777564, 0, 4]
[98767676123456666777777565, 0, 5]
[98767676123456666777777566, 0, 6]
[98767676123456666777777567, 0, 7]
[98767676123456666777777568, 0, 8]
[98767676123456666777777569, 0, 9]
[98767676123456666777777570, 0, 10]
[98767676123456666777777571, 0, 11]
[98767676123456666777777572, 0, 12]
[98767676123456666777777573, 1, 0]
[98767676123456666777777574, 0, 1]
[98767676123456666777777575, 0, 2]
[98767676123456666777777576, 0, 3]
[98767676123456666777777577, 0, 4]
[98767676123456666777777578, 0, 5]
[98767676123456666777777579, 0, 6]
[98767676123456666777777580, 0, 7]
[98767676123456666777777581, 0, 8]
[98767676123456666777777582, 0, 9]
[98767676123456666777777583, 0, 10]
[98767676123456666777777584, 0, 11]
[98767676123456666777777585, 0, 12]
[98767676123456666777777586, 1, 0]
[98767676123456666777777587, 0, 1]
[98767676123456666777777588, 0, 2]
[98767676123456666777777589, 0, 3]
[98767676123456666777777590, 0, 4]
[98767676123456666777777591, 0, 5]
[98767676123456666777777592, 0, 6]
[98767676123456666777777593, 0, 7]
[98767676123456666777777594, 0, 8]
[98767676123456666777777595, 0, 9]
[98767676123456666777777596, 0, 10]
[98767676123456666777777597, 0, 11]
[98767676123456666777777598, 0, 12]
[98767676123456666777777599, 1, 0]
[98767676123456666777777600, 0, 1]
[98767676123456666777777601, 0, 2]
[98767676123456666777777602, 0, 3]
[98767676123456666777777603, 0, 4]
[98767676123456666777777604, 0, 5]
[98767676123456666777777605, 0, 6]
[98767676123456666777777606, 0, 7]
[98767676123456666777777607, 0, 8]
[98767676123456666777777608, 0, 9]
[98767676123456666777777609, 0, 10]
[98767676123456666777777610, 0, 11]
[98767676123456666777777611, 0, 12]
[98767676123456666777777612, 1, 0]
[98767676123456666777777613, 0, 1]
[98767676123456666777777614, 0, 2]
[98767676123456666777777615, 0, 3]
[98767676123456666777777616, 0, 4]
[98767676123456666777777617, 0, 5]
[98767676123456666777777618, 0, 6]
[98767676123456666777777619, 0, 7]
[98767676123456666777777620, 0, 8]
[98767676123456666777777621, 0, 9]
[98767676123456666777777622, 0, 10]
[98767676123456666777777623, 0, 11]
[98767676123456666777777624, 0, 12]
[98767676123456666777777625, 1, 0]
[98767676123456666777777626, 0, 1]
[98767676123456666777777627, 0, 2]
[98767676123456666777777628, 0, 3]
[98767676123456666777777629, 0, 4]
[98767676123456666777777630, 0, 5]
[98767676123456666777777631, 0, 6]
[98767676123456666777777632, 0, 7]
[98767676123456666777777633, 0, 8]
[98767676123456666777777634, 0, 9]

Fixed typo in listing (tot = tot-12 chgd to tot=tot-13) to get the modular value. The actual program had the correct number.

Edited on April 15, 2022, 2:52 pm

Edited on April 15, 2022, 4:13 pm

Posted by Charlie on 2022-04-15 14:02:01

Please log in:

Login:
Password:
Remember me:

Sign up! \| Forgot password

Search:

Search body:

Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (10)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info