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.)

My favorite

| Comment 2 of 11 |

My favorite algorithm for division by 13 (because it works for 7 and 11 as well) uses the fact that 7*11*13=1001.

It is akin to the divisibility rule for 11 where you take the alternating sum of successive digits. Instead you can take alternating sums of triples (from the right).

So for example

7,890,456,123

123-456+890-7 = 550

Which is not divisible by 13 (R=4)

But is divisible by 11

and is not divisible by 7 (R=4)

Posted by Jer on 2022-04-15 10:37:47

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 (4)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:


perplexus dot info