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

 All 1's (Posted on 2013-12-14)
(1) Find a test for divisibility by 111.

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

 No Solution Yet Submitted by Danish Ahmed Khan No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
 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

 Search: Search body:
Forums (0)