3 ms·

Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end a

Up to 100 it is relatively simple, if you remove the even numbers, the multiples of 3 (summing up their digits recursively gives 3 6 or 9), and those that end at 5, you end up with 25 numbers out of which 22 (88%) are primes. If you further exclude 49 which you should remember is 7^2 from the multiplication table, and 77 that is obviously divisible by 7, you are left with 22/23 chance a number that passes these exclusion criteria is not 91 and hence it is a prime.

jeffbee 11mo ago
> summing up their digits recursively gives 3 6 or 9 What does this part mean? For example 57.
- hollerith 11mo ago
  5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
- zdimension 11mo ago
  57 is 3 times 19. The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
  - jeffbee 11mo ago
    Ah I see what is meant by recursively here. Thanks!
  - squigz 11mo ago
    Math is not my strong suit at all, so I probably won't grok this, but that kind of blows my mind, so I'm curious... how?! That works for any arbitrarily large number? Math is crazy!... still don't want to study it though!
    - moring 11mo ago
      Yes. A number like 123456 = 1 * 100000 + 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6 = 1 * (99999+1) + 2 * (9999+1) + 3 * (999+1) + 4 * (99+1) + 5 * (9+1) + 6 When checking whether it is a multiple of some k, you can add/subtract multiples of k without changing the result, and those 99...9 are multiples of both 3 and 9. So 123456 is a multiple of 3 (or 9) iff 1 * 1 + 2 * 1 + 3 * 1 + 4 * 1 + 5 * 1 + 6 * 1 = 1 + 2 + 3 + 4 + 5 + 6 is. Apply the same rule as often as you want -- that is, until you only have one digit left, because then it won't get simpler anymore.
    - deleted 11mo ago
      [deleted]
    - freehorse 11mo ago
      It is basically because $10 mod 3 == 1$ (as 10 = 3*3 + 1). So if you are in the ring modulo 3, where every number is equal to the remainder of its division by 3, the sum of the digits of the number in its decimal representation equals the number itself (modulo 3), because in that ring 10 is actually 1, so the 10s in the decimal sum become 1s. Ie if n_k is the kth digit of n, you have (mod 3) n == n_0 + n_1*10 + n_2*10^2 + ... == n_0 + n_1 + n_2 + ... Hence, n is divisible by 3 iff $n mod 3 == 0$ iff $(n_0 + n_1 + n_2 + ...) mod 3 == 0$. Of course, summing up the digits may not give you a 1-digit number, but it gives you a number that you know is divisible by 3 (if the original number is divisible by 3). So you can apply the same idea/process again, summing up the digits of that number, and get another number that is divisible by 3. Repeat until you end up with one digit (hence the recursion mentioned).
maxbond 11mo ago
> (summing up their digits recursively gives 3 6 or 9) My fun fact is that this type of operation (repeatedly applying a child operation until you reach a fixed point) is called persistence. https://en.wikipedia.org/wiki/Persistence_of_a_number https://en.wikipedia.org/wiki/Persistence_of_a_number The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence. https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture I'm partial to multiplicative persistence. https://www.youtube.com/watch?v=Wim9WJeDTHQ https://www.youtube.com/watch?v=Wim9WJeDTHQ [15m]

jeffbee 11mo ago

> summing up their digits recursively gives 3 6 or 9 What does this part mean? For example 57.

hollerith 11mo ago
5 plus 7 is 12, which of course has a 1 and a 2, the sum of which is 3.
zdimension 11mo ago
57 is 3 times 19. The standard divisibility rule for 3, 6 and 9 in base 10 is to sum the digits until you only have one left and check if it's one of those. Here, 5+7=12, 1+2=3, so 57 is divisible by 3.
- jeffbee 11mo ago
  Ah I see what is meant by recursively here. Thanks!
- squigz 11mo ago
  Math is not my strong suit at all, so I probably won't grok this, but that kind of blows my mind, so I'm curious... how?! That works for any arbitrarily large number? Math is crazy!... still don't want to study it though!
  - moring 11mo ago
    Yes. A number like 123456 = 1 * 100000 + 2 * 10000 + 3 * 1000 + 4 * 100 + 5 * 10 + 6 = 1 * (99999+1) + 2 * (9999+1) + 3 * (999+1) + 4 * (99+1) + 5 * (9+1) + 6 When checking whether it is a multiple of some k, you can add/subtract multiples of k without changing the result, and those 99...9 are multiples of both 3 and 9. So 123456 is a multiple of 3 (or 9) iff 1 * 1 + 2 * 1 + 3 * 1 + 4 * 1 + 5 * 1 + 6 * 1 = 1 + 2 + 3 + 4 + 5 + 6 is. Apply the same rule as often as you want -- that is, until you only have one digit left, because then it won't get simpler anymore.
  - deleted 11mo ago
    [deleted]
  - freehorse 11mo ago
    It is basically because $10 mod 3 == 1$ (as 10 = 3*3 + 1). So if you are in the ring modulo 3, where every number is equal to the remainder of its division by 3, the sum of the digits of the number in its decimal representation equals the number itself (modulo 3), because in that ring 10 is actually 1, so the 10s in the decimal sum become 1s. Ie if n_k is the kth digit of n, you have (mod 3) n == n_0 + n_1*10 + n_2*10^2 + ... == n_0 + n_1 + n_2 + ... Hence, n is divisible by 3 iff $n mod 3 == 0$ iff $(n_0 + n_1 + n_2 + ...) mod 3 == 0$. Of course, summing up the digits may not give you a 1-digit number, but it gives you a number that you know is divisible by 3 (if the original number is divisible by 3). So you can apply the same idea/process again, summing up the digits of that number, and get another number that is divisible by 3. Repeat until you end up with one digit (hence the recursion mentioned).

maxbond 11mo ago

> (summing up their digits recursively gives 3 6 or 9) My fun fact is that this type of operation (repeatedly applying a child operation until you reach a fixed point) is called persistence. https://en.wikipedia.org/wiki/Persistence_of_a_number https://en.wikipedia.org/wiki/Persistence_of_a_number The fixed point here being that if you add up a list of 1 digits, you'll always reach the same number (`sum([1]) = 1`). The best known is probably the hailstone sequence. https://en.wikipedia.org/wiki/Collatz_conjecture https://en.wikipedia.org/wiki/Collatz_conjecture I'm partial to multiplicative persistence. https://www.youtube.com/watch?v=Wim9WJeDTHQ https://www.youtube.com/watch?v=Wim9WJeDTHQ [15m]