Depending on what does or doesn’t count, it might be possible to be sure of whether 1033 is prime without “trying to factor” it (i.e., by checking whether it’s divisible (without actually carry out the divisions) by any prime number less than sqrt(1033)).
So I interpreted “try to factor it” pessimistically as “try to figure out for sure whether it’s prime”.
Right. And, indeed, when I need to check in my head whether a smallish number like 1033 is prime, most of what I do isn’t factoring. E.g.: 1033+17 = 1050 = 50.21, ruling out {2,3,5,7,17} in a single go but not identifying any factors or (even approximate) quotients. 1033-13 = 1020 = 20.51, ruling out {2,3,5,13,17} instead. Etc.
I also assumed that Eliezer’s intention was that you shouldn’t be doing this sort of thing.
[EDITED to fix formatting screwage—asterisks treated as markup rather than multiplication—my apologies for any mystification this caused.]
(Initial remark: damn, I see that what I wrote got screwed up by asterisks getting treated as markup characters; perhaps everything would have been clear without that. Will fix once I’ve finished writing this.)
I’m not sure it really warrants dignifying with the term “method”, but:
The relations I’m looking for are of the form n=a+b or n=a-b where a,b (1) are easy to factor because they’re products of small primes, and (2) have no common factor. In that case, you know that n isn’t a multiple of any of those prime numbers—so, e.g., if a, but not b, is a multiple of p, then a+b and a-b are not multiples of p.
The easiest case is where b is itself a small prime number like 17 or 13. Why 17 and 13? Because the number ends in 3, so subtracting something ending in 3 or adding something ending in 7 will give us (an easy-to-deal-with factor of 10, and) something nicely smaller. In some cases it’s easier to remove digits from the start of the number rather than the end; for a trivial example, 1033 isn’t a multiple of 103 because it’s 1030 + 3.
Let’s do 1033 a bit more thoroughly. It’s between 32^2=1024 and 33^2=1089, so we need to check primes up to 31. 1033=1050-17 rules out 2,3,5,7,17. 1033=1020+13 rules out 2,3,5,13,17. 1033=1000+33 rules out 2,3,5,11. (That’s all the primes up to 17 done, leaving 19,23,29,31.) 1033=1010+23 rules out 2,5,(101),23. At this point, actually, I’d try dividing by 19,29,31, but let’s carry on. For 31 we’ll subtract 93: 1033=940+93, and 940=2.2.5.47 so we’ve ruled out 31. For 19 we’ll subtract 950, leaving 83 which is prime, so 19 is ruled out. For 29 I suppose the best we can do is to subtract 870, leaving 163 which I happen to know is prime because of exp(pi sqrt(163)) but in any case clearly isn’t a multiple of 29. So we’re done and 1033 is prime. And I didn’t factorize 1033 unless proving something is prime by a roundabout route counts as factorizing it. If one of these things had turned out to have the same prime number dividing both summands, there’d still have been extra work to do to get the quotient.
Primes less than sqrt(1033) for which I know of no really obvious tricks (i.e. the digit adding tricks for them aren’t so simple one can trivially do them in your head): 7, 13, 17, 19, 23, 29, 31
Also, since the scenario said we’ve done this many times and we haven’t been trolleyed yet, it can’t be all that easy to get trolleyed.
(eta: why the −1? Both points seem solid to me, even in the light of the additional trick below—there are several possible factors remaining, and it’s not like I was enumerating these during my 2 minutes. Moreover, the 1001 trick works for 1033, but doesn’t help so much with other typical numbers of that general magnitude—say, 1537, that it’s something you’re liable to do by accident)
Also, since the scenario said we’ve done this many times and we haven’t been trolleyed yet, it can’t be all that easy to get trolleyed.
Maybe you get run over by the trolley only if you try to factor Omega’s number, and all the times before this Omega’s number and the lottery number were different, and there’s no much point in trying to factor the lottery number in that case since (assuming linear utility of money) it has no relevance on how many boxes you should take.
I trust that observing that it’s not a multiple of 2, 3, 5, or 11 doesn’t count.
Depending on what does or doesn’t count, it might be possible to be sure of whether 1033 is prime without “trying to factor” it (i.e., by checking whether it’s divisible (without actually carry out the divisions) by any prime number less than sqrt(1033)).
So I interpreted “try to factor it” pessimistically as “try to figure out for sure whether it’s prime”.
Right. And, indeed, when I need to check in my head whether a smallish number like 1033 is prime, most of what I do isn’t factoring. E.g.: 1033+17 = 1050 = 50.21, ruling out {2,3,5,7,17} in a single go but not identifying any factors or (even approximate) quotients. 1033-13 = 1020 = 20.51, ruling out {2,3,5,13,17} instead. Etc.
I also assumed that Eliezer’s intention was that you shouldn’t be doing this sort of thing.
[EDITED to fix formatting screwage—asterisks treated as markup rather than multiplication—my apologies for any mystification this caused.]
I’m curious, what’s the method you’re using there?
(Initial remark: damn, I see that what I wrote got screwed up by asterisks getting treated as markup characters; perhaps everything would have been clear without that. Will fix once I’ve finished writing this.)
I’m not sure it really warrants dignifying with the term “method”, but:
The relations I’m looking for are of the form n=a+b or n=a-b where a,b (1) are easy to factor because they’re products of small primes, and (2) have no common factor. In that case, you know that n isn’t a multiple of any of those prime numbers—so, e.g., if a, but not b, is a multiple of p, then a+b and a-b are not multiples of p.
The easiest case is where b is itself a small prime number like 17 or 13. Why 17 and 13? Because the number ends in 3, so subtracting something ending in 3 or adding something ending in 7 will give us (an easy-to-deal-with factor of 10, and) something nicely smaller. In some cases it’s easier to remove digits from the start of the number rather than the end; for a trivial example, 1033 isn’t a multiple of 103 because it’s 1030 + 3.
Let’s do 1033 a bit more thoroughly. It’s between 32^2=1024 and 33^2=1089, so we need to check primes up to 31. 1033=1050-17 rules out 2,3,5,7,17. 1033=1020+13 rules out 2,3,5,13,17. 1033=1000+33 rules out 2,3,5,11. (That’s all the primes up to 17 done, leaving 19,23,29,31.) 1033=1010+23 rules out 2,5,(101),23. At this point, actually, I’d try dividing by 19,29,31, but let’s carry on. For 31 we’ll subtract 93: 1033=940+93, and 940=2.2.5.47 so we’ve ruled out 31. For 19 we’ll subtract 950, leaving 83 which is prime, so 19 is ruled out. For 29 I suppose the best we can do is to subtract 870, leaving 163 which I happen to know is prime because of exp(pi sqrt(163)) but in any case clearly isn’t a multiple of 29. So we’re done and 1033 is prime. And I didn’t factorize 1033 unless proving something is prime by a roundabout route counts as factorizing it. If one of these things had turned out to have the same prime number dividing both summands, there’d still have been extra work to do to get the quotient.
Primes less than sqrt(1033) for which I know of no really obvious tricks (i.e. the digit adding tricks for them aren’t so simple one can trivially do them in your head): 7, 13, 17, 19, 23, 29, 31
Also, since the scenario said we’ve done this many times and we haven’t been trolleyed yet, it can’t be all that easy to get trolleyed.
(eta: why the −1? Both points seem solid to me, even in the light of the additional trick below—there are several possible factors remaining, and it’s not like I was enumerating these during my 2 minutes. Moreover, the 1001 trick works for 1033, but doesn’t help so much with other typical numbers of that general magnitude—say, 1537, that it’s something you’re liable to do by accident)
Maybe you get run over by the trolley only if you try to factor Omega’s number, and all the times before this Omega’s number and the lottery number were different, and there’s no much point in trying to factor the lottery number in that case since (assuming linear utility of money) it has no relevance on how many boxes you should take.
1001 = 7 x 11 x 13, so each of those divides 1033 iff it divides 32 (and divides 314,159,265 iff it divides 265 − 159 + 314).