I don’t usually keep the factors, but I have a variety of techniques. Putting aside the trivial cases of divisibility by 2, 3, 5, 11¹ and 37², a lot of it comes down to find ways to make the numbers smaller, so, for example. my current odometer reading is 13,857. To test for divisibility by 7, I can turn that into 14,000-13852=143 which I can tell at a glance isn’t divisible by 7. It is divisible by 3, so I can reduce it to 4619 which isn’t divisible by 3 and I can also tell it’s not divisible by 11. I can also rule out 19 at a glance. To check 13, I might do my right-side divisibility test where I start by subtracting 39 from the right, which gives 458. I could continue with that, but taking 39 from the left gets me to a small enough number faster of 68 which isn’t divisible by 13. Right-side divisibility for 17 takes 119 from the right leaving 45 which isn’t divisible by 17. For 23, I can do a left-side removal of 46 to rule that out. 29, go right to bring it to 459 and then 43, not divisible by 29. For 31, I’ll do right side to get 434 and then 31 so 4619=149×31 and 149 is prime and I’m done.
⸻
1. To check for divisibility by 11, subtract the sum of even numbered digits from the sub of odd numbered digits. If 11∣n, then you’ll have a multiple of 11. E.g., for 13,857, we compare (3+5)-(1+8+7)=-8 which is not a multiple of 11.³
2. To check for divisibility by 111, we take advantage of the fact that 3×37=111, 27×37=999 and thus 1000≡1(mod 37) and we can then add up the digits in groups of 3, and pull out the most convenient multiple of 111 to see if we have 0, 37 or 74. E.g., with our example about, 13+852=865-888=-23 which is not a multiple of 37.
3. As an added bonus that number is the remainder when dividing by 11. Similarly the number I get with the check in footnote 2 is the remainder when dividing by 37.
alt Hacker News
I don’t usually keep the factors, but I have a variety of techniques. Putting aside the trivial cases of divisibility by 2, 3, 5, 11¹ and 37², a lot of it comes down to find ways to make the numbers smaller, so, for example. my current odometer reading is 13,857. To test for divisibility by 7, I can turn that into 14,000-13852=143 which I can tell at a glance isn’t divisible by 7. It is divisible by 3, so I can reduce it to 4619 which isn’t divisible by 3 and I can also tell it’s not divisible by 11. I can also rule out 19 at a glance. To check 13, I might do my right-side divisibility test where I start by subtracting 39 from the right, which gives 458. I could continue with that, but taking 39 from the left gets me to a small enough number faster of 68 which isn’t divisible by 13. Right-side divisibility for 17 takes 119 from the right leaving 45 which isn’t divisible by 17. For 23, I can do a left-side removal of 46 to rule that out. 29, go right to bring it to 459 and then 43, not divisible by 29. For 31, I’ll do right side to get 434 and then 31 so 4619=149×31 and 149 is prime and I’m done.
⸻
1. To check for divisibility by 11, subtract the sum of even numbered digits from the sub of odd numbered digits. If 11∣n, then you’ll have a multiple of 11. E.g., for 13,857, we compare (3+5)-(1+8+7)=-8 which is not a multiple of 11.³
2. To check for divisibility by 111, we take advantage of the fact that 3×37=111, 27×37=999 and thus 1000≡1(mod 37) and we can then add up the digits in groups of 3, and pull out the most convenient multiple of 111 to see if we have 0, 37 or 74. E.g., with our example about, 13+852=865-888=-23 which is not a multiple of 37.
3. As an added bonus that number is the remainder when dividing by 11. Similarly the number I get with the check in footnote 2 is the remainder when dividing by 37.