All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Algorithms
Divisible by 11 (Posted on 2008-01-02) Difficulty: 3 of 5
Give an algorithm that determines whether a given number is divisible by 11 or not. The number could have up to one million digits.

(Note that simply dividing by 11, or doing long division by 11 is not allowed as a solution.)

See The Solution Submitted by Chesca Ciprian    
Rating: 3.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution without proof | Comment 1 of 3
I learned this when I was a math tutor years ago. I do not know the proof, nor do I know if it's guaranteed to be correct; however, I have yet to find a contradiction.

Algorithm: Add up all digits in even positions to get a number, and add up all digits in odd positions to get another number. Subtract these two numbers and if the total is divisible by 11 then the original number is divisible by 11 as well. (Therefore, you may need to use the algorithm recursively.)

Examples:

135802467913580246790
Add up 1 + 5 + 0 + 4 + 7 + 1 + 5 + 0 + 4 + 7 + 0 = 34
Add up 3 + 8 + 2 + 6 + 9 + 3 + 8 + 2 + 6 + 9 = 56
Subtract 56 - 34 = 22 which as we know is divisible by 11, thus 135802467913580246790 is divisible by 11.

1234
Add up 1 + 3 = 4
Add up 2 + 4 = 6
Subtract 6 - 4 = 2 which is not divisible by 11 and so 1234 isn't either.

A quick Google search reveals an interesting page on this type of divisibility algorithms, and provides an algebraic proof at the end:
http://www.egge.net/~savory/maths1.htm

Interestingly, the algorithm for 11 is different (and easier!) than that which I've given. So... I wonder if anyone can prove or disprove the algorithm I've given above... :)

  Posted by Kurious on 2008-01-02 17:46:02
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 (12)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information