3 ms·

I assume you also know the trick of adding the columns to test divisibility by three: 387 becomes 3+8+7, which is 18, which becomes 1+8 = 9. This works because

I assume you also know the trick of adding the columns to test divisibility by three: 387 becomes 3+8+7, which is 18, which becomes 1+8 = 9. This works because 10 % 3 = 1, so 100 = 99+1 (etc.), with the effect that each column can be counted as if it was units. To apply the same trick to a multiple of 7, the tens column is worth 3 (10 % 7 = 3), so 91 -> 27 + 1 -> 6 + 8 -> 3 + 4 -> 7. The value is different in the next column (100 % 7 = 2). This trick is no help at all but I still like it. (Finished editing out mistakes now.)

hiAndrewQuinn 1y ago
Hm... 14 => 1 (3^1) + 4 (3^0) => 7 => divisible by 7. 21 => 6 (3^1) + 1 (3^0) => 7 => also divisible by 7. 7 * 53 = 371 => 3 (3^2) + 7 (3^1) + 1 (3^0) => 27 + 21 + 1 => 49 => ALSO divisible by 7! My word! This is the intuition I always suspected was possible after studying how bases worked, but I never took the time to investigate on my own.
- card_zero 1y ago
  Hmm, no. There's a hazard of false positives here (which is why I had mistakes to fix previously). It's not all about the number 3; you don't want to multiply columns by 3², 3¹, 3⁰. Instead you want the remainder of the division of (ten to the column number) by seven (or whatever divisor you're checking). That's a repeating pattern. In the case of 3 the pattern has length 1, and it goes (1, 1, 1, ...). In the case of 7 the pattern has length 6, and it goes (1, 3, 2, 6, 4, 5), starting at the units column. If that looks a bit pseudorandom, there's a good reason, it's vaguely similar to an old-fashioned PRNG. (The pattern starts again with 1 in the millions column, because 142857 * 7 = 999999. Hence 2 million divided by 7 has remainder 2, 3 million divided by 7 has remainder 3, and so on.) So 371 should be understood as 3*2 + 7*3 + 1*1, which is 28. Or as another example, 6993 => 6*6 + 9*2 + 9*3 + 3*1, which is 84.
  - card_zero 1y ago
    Waaait a minute though. The results for (10 to the n) % 7 and the results for (3 to the n) % 7 are the same, so your version works precisely. That's because the difference is 7.

hiAndrewQuinn 1y ago

Hm... 14 => 1 (3^1) + 4 (3^0) => 7 => divisible by 7. 21 => 6 (3^1) + 1 (3^0) => 7 => also divisible by 7. 7 * 53 = 371 => 3 (3^2) + 7 (3^1) + 1 (3^0) => 27 + 21 + 1 => 49 => ALSO divisible by 7! My word! This is the intuition I always suspected was possible after studying how bases worked, but I never took the time to investigate on my own.

card_zero 1y ago
Hmm, no. There's a hazard of false positives here (which is why I had mistakes to fix previously). It's not all about the number 3; you don't want to multiply columns by 3², 3¹, 3⁰. Instead you want the remainder of the division of (ten to the column number) by seven (or whatever divisor you're checking). That's a repeating pattern. In the case of 3 the pattern has length 1, and it goes (1, 1, 1, ...). In the case of 7 the pattern has length 6, and it goes (1, 3, 2, 6, 4, 5), starting at the units column. If that looks a bit pseudorandom, there's a good reason, it's vaguely similar to an old-fashioned PRNG. (The pattern starts again with 1 in the millions column, because 142857 * 7 = 999999. Hence 2 million divided by 7 has remainder 2, 3 million divided by 7 has remainder 3, and so on.) So 371 should be understood as 3*2 + 7*3 + 1*1, which is 28. Or as another example, 6993 => 6*6 + 9*2 + 9*3 + 3*1, which is 84.
- card_zero 1y ago
  Waaait a minute though. The results for (10 to the n) % 7 and the results for (3 to the n) % 7 are the same, so your version works precisely. That's because the difference is 7.