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

Home > Numbers
All 1's (Posted on 2013-12-14) Difficulty: 3 of 5
(1) Find a test for divisibility by 111.

(2) Extending this, find a test for divisibility by any number consisting solely of 1's.

Please explain why your tests work.

No Solution Yet Submitted by Danish Ahmed Khan    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Divide and conquer (spoiler) | Comment 1 of 3
In general, to test any number for divisibility by n, 
multiply the units digit by 1,
multiply the 10's digit by 10 mod n,
multiply the 100's digit by 100 mod n,
multiply the 1000's digit by 1000 mod n,
etc.

and the sum necessarily has the same value mod n as the original number.  If this is still a large number, then repeat the process.

For instance, if n = 111,
then multiply the units digit by 1,
multiply the 10's digit by 10,
multiply the 100's digit by 100,
multiply the 1000's digit by 1,
multiply the 10000's digit by 10, etc.
and sum.

This can readily be achieved by dividing the number into a series of three digit numbers starting at the right, and summing these.

For instance, 946572 mod 111 
= (946+572) mod 111 = 1518 mod 111 
= (1 + 518) mod 111 = 519 mod 111
 
519 is not divisible by 111, so neither is the original number.

To test for divisibility by a repunit of length k,  divide the number into groups of k digits (starting from the right), sum those groups, and repeat the process until the resulting sum is k digits or less. The original number is divisible if and only if the resulting number has k digits all the same.  This works, of course, because 10^k -1 = 999...999 (k digits), so 10^k = 1 mod repunit of length k.

For instance, to test 946572 for divisibility by 1111, calculate 94 + 6572 = 6666, so it is divisible by 1111!

Edited on December 14, 2013, 9:15 pm
  Posted by Steve Herman on 2013-12-14 21:12:35

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

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