71
$\begingroup$

I sat an exam 2 months ago and the question paper contains the problem:

Given that there are $168$ primes below $1000$. Then the sum of all primes below 1000 is

(a) $11555$ (b) $76127$ (c) $57298$ (d) $81722$

My attempt to solve it: We know that below $1000$ there are $167$ odd primes and 1 even prime (2), so the sum has to be odd, leaving only the first two numbers. Then I tried to use the formula "Every prime can be written in of the form $6n-1$,$6n+1$ except $2$ and $3$.", but I got stuck at that.

$\endgroup$
  • 7
    $\begingroup$ Only (b) is really plausible on size. I'd expect the average size to be in the 400-500 area, but definitely less than 500. Then you have eliminated (c) and (d) on parity anyway. $\endgroup$ – Joffan Jan 30 '17 at 2:27
  • 11
    $\begingroup$ Just by "multiple-choice psychology" I expect both obviously wrong answers (c) and (d) to be somehow close to (and ideally on both sides of) the correct answer. This is the case only if (b) is the correct answer. $\endgroup$ – Curd Jan 30 '17 at 16:22
  • 3
    $\begingroup$ @SlimsGhost: I know what a mathematical proof looks like, but nobody was asking for a proof. I'm just making fun of multiple-choice tests. $\endgroup$ – Curd Jan 30 '17 at 20:24
  • 4
    $\begingroup$ I have to say, that this test question is horrible. It's gimicky and relies on a lot of mental jumps, the opposite of what a test question should do. $\endgroup$ – HopefullyHelpful Jan 31 '17 at 9:18
  • 3
    $\begingroup$ According to OEIS A034387 (both "Comments" and "Formula") one can approximate the answer by $1000^2/(2\log 1000)$ which gives $72382.4$. This suggests that (a) could be wrong. That same reference has a "Link" with Table of n, a(n) for n = 1..10000. $\endgroup$ – Jeppe Stig Nielsen Jan 31 '17 at 12:44
144
$\begingroup$

The sum of the first 168 positive integers is $\frac{168^2+168}{2}=14196$, which is greater than answer (a). The sum of the first 168 primes must be even greater than that.

$\endgroup$
  • $\begingroup$ Oscar Lanzi has a similar answer (which is earlier); yours is a bit more simple (but your bound is only half as good, though already good enough to exclude (a)). $\endgroup$ – Jeppe Stig Nielsen Jan 31 '17 at 14:59
  • 3
    $\begingroup$ I agree Oscar's answer is similar, and it helped inspire this one. But I think it's instructive to show just how obviously too low (a) is, and how trivially simple the bound that excludes it can be. That said I didn't quite expect this answer to be so popular, I guess people like simplicity... $\endgroup$ – Meni Rosenfeld Jan 31 '17 at 21:19
  • 2
    $\begingroup$ Beauty lies in simplicity. $\endgroup$ – Brian Feb 1 '17 at 3:33
55
$\begingroup$

you just have to decide between $11555$ and $76127$.

Notice that the first implies the average prime under $1000$ is $11555/168<69$. Which is clearly false.

$\endgroup$
  • 8
    $\begingroup$ To clarify, note that there are only 19 primes under 69 and the remaining 149 primes are larger. Hence there is no way to arrive at this average. $\endgroup$ – user1952500 Jan 30 '17 at 9:27
  • 1
    $\begingroup$ Or the other way round, the average of the primes <1000 should be below 500, since the density decreases. So the sum should be below 168*500 = 84000. That leaves only 76127. $\endgroup$ – Florian F Jan 30 '17 at 11:39
  • 5
    $\begingroup$ @FlorianF Well… no, not really. 11,555 is obviously wrong, but it is definitely below 84,000. $\endgroup$ – Janus Bahs Jacquet Jan 30 '17 at 17:51
  • $\begingroup$ I just independently used the same method. Florian's estimate for (B) is a ballpark overestimate. Accuracy doesn't matter because (A) is infeasible because it implies an impossibly low mean. So we already know the answer can only be (B), whatever (B) is. We weren't asked to estimate (B) more accurately, in which case we'd integrate some Prime-counting function e.g. per the OEIS sequence @JeppeStigNielsen cites. $\endgroup$ – smci Feb 1 '17 at 1:00
  • $\begingroup$ One doesn't even need to count the number of primes under $69$. We're told that there are $168$ primes below $1000$, so the average of the primes below $1000$ is certainly greater than the average of the first $168$ positive integers, which is $169/2$. Of course, this is essentially the content of Meni Rosenfeld's answer... $\endgroup$ – Alex Wertheim Feb 2 '17 at 2:17
45
$\begingroup$

We have to decide among $\text{(A)}$ and $\text{(B)}$. Note that the $26$th prime is $101$. This implies that if $p_{n}$ denotes the $n$ th prime, then $$\sum_{n=1}^{168}p_{n} = \sum_{n=1}^{25}p_{n}+\sum_{n=26}^{168} p_{n} > \sum_{n=26}^{168} 101 =101 \times 143=14443 >\text{(A)}=11555$$

The answer is thus $\text{(B)}$, $76127$. The answer can be confirmed through direct calculation or can be verfied here.

$\endgroup$
  • 4
    $\begingroup$ Why did you choose the 26th prime here? Or is it just arbitrary? $\endgroup$ – MarioDS Jan 30 '17 at 14:22
  • 44
    $\begingroup$ It is somewhat commonly known piece of a trivia - there are 25 primes below 100 and the primes below 25 sum to 100. $\endgroup$ – Jon Claus Jan 30 '17 at 14:31
  • 1
    $\begingroup$ @MarioDS It is as Jon Claus said; many people memorized it, so I was able to answer it quickly. $\endgroup$ – S.C.B. Jan 30 '17 at 15:00
31
$\begingroup$

There are $168$ primes with the first one equal to $2$ the rest $\ge 2k-1$ for $k=2,3,4,...,168$. So their sum is at least $168^2+1=28 225$.

$\endgroup$
  • $\begingroup$ (a) would mean that the average prime is $<70$, which is horrendously implausible, for me good enough to pick (b) instead. - But this answer is the formal reason why it's implausible $\endgroup$ – Hagen von Eitzen Jan 30 '17 at 20:22
14
$\begingroup$

I just wanted to carry forward your observation about "Every prime can be written in of the form $(6n-1),(6n+1)$ except $2$ & $3$".

We can quickly get a minimum sum out of this. Assume that the $166$ primes not $2$ or $3$ are the smallest such numbers obeying the above; then $83$ are $6k{-}1$, $83$ are $6k{+}1$ and the minimum bound total is $83$ terms of $12k$, which is $12\cdot 84 \cdot 83 /2 = 504\cdot 83 = 41832$ - and we can decoratively add the $2$ and $3$ to get $41837$. This is more than big enough to eliminate option (a) as required.

$\endgroup$
  • 3
    $\begingroup$ The only problem here is that I feel cheated at the too-obvious wrongness of option (a) - it could've been say 41555 instead of 11555 :-) $\endgroup$ – Joffan Jan 30 '17 at 15:36
  • 1
    $\begingroup$ Interestingly, 41837 isn't that far away from 76127. $\endgroup$ – gnasher729 Jan 30 '17 at 23:22
  • 2
    $\begingroup$ Using that all primes > 7 are 30k ± 1, 7, 11, 13, the lower bound is 51,677. $\endgroup$ – gnasher729 Jan 30 '17 at 23:33
12
$\begingroup$

Your analysis that the answer must be (a) or (b) is convincing. Considering that (a) and (b) are much different, just about any simplistic method to approximate the sum of all primes should tell which is the right answer. For example, the sum of all numbers less than 1000 is about 500,000. So, 168/1000*500,000 or 84,000 should be in the right ballpark. 76127 is the right answer, by this reasoning.

$\endgroup$
  • $\begingroup$ Yup you got me to upvote. A comparison test, see another answer, easily limits the size of the "ballpark" thus settling the question. $\endgroup$ – Oscar Lanzi Jan 30 '17 at 2:08
  • 2
    $\begingroup$ I edited out the meta-commentary (as we call it... well, at least as I call it) because we try to stay away from that stuff on SE. Anyway, I think you've got nothing to worry about. This method is legit, because the four answer choices are separated by enough to easily distinguish between them. $\endgroup$ – David Z Jan 30 '17 at 5:12
8
$\begingroup$

Primes except for $2$ are all odd, and you have $168$ distinct primes, so their sum must be at least $2 + \sum_{k=2}^{168} (2k-1) = 2 + (168^2-1) > 160^2 = 25600 > 11555$. So option (a) is out and only (b) remains.

$\endgroup$
  • 1
    $\begingroup$ Of course, the question is so weak that taking the first $168$ positive integers suffices, but it's even easier to get a bound using odd positive integers! $\endgroup$ – user21820 Jan 30 '17 at 11:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.