77
$\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$
11
  • 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, 2017 at 2:27
  • 12
    $\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, 2017 at 16:22
  • 4
    $\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, 2017 at 20:24
  • 5
    $\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$ Jan 31, 2017 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$ Jan 31, 2017 at 12:44

8 Answers 8

150
$\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$
3
  • $\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$ Jan 31, 2017 at 14:59
  • 4
    $\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$ Jan 31, 2017 at 21:19
  • 4
    $\begingroup$ Beauty lies in simplicity. $\endgroup$
    – Brian
    Feb 1, 2017 at 3:33
57
$\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$
5
  • 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$ Jan 30, 2017 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, 2017 at 11:39
  • 5
    $\begingroup$ @FlorianF Well… no, not really. 11,555 is obviously wrong, but it is definitely below 84,000. $\endgroup$ Jan 30, 2017 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, 2017 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$ Feb 2, 2017 at 2:17
44
$\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$
3
  • 4
    $\begingroup$ Why did you choose the 26th prime here? Or is it just arbitrary? $\endgroup$
    – MarioDS
    Jan 30, 2017 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, 2017 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, 2017 at 15:00
33
$\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$
1
  • 1
    $\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$ Jan 30, 2017 at 20:22
15
$\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
  • 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, 2017 at 15:36
  • 1
    $\begingroup$ Interestingly, 41837 isn't that far away from 76127. $\endgroup$
    – gnasher729
    Jan 30, 2017 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, 2017 at 23:33
13
$\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, $\cfrac{168}{1000} \times 500,000$ or $84,000$ should be in the right ballpark. $76127$ is the right answer, by this reasoning.

$\endgroup$
2
  • $\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$ Jan 30, 2017 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, 2017 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
  • 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, 2017 at 11:48
0
$\begingroup$

The methods provided previously are very correct. However, I would like to share my approach as I believe this is even simpler. It's less calculative, and more logical.

Sum is odd ⇒ answer is either (a) or (b)

Taking the number in (a) 11555 we divide it by 168 [to get the average]

11555/168≈69

69<168/2

An average of 168 distinct numbers can be less than 168/2(=84) iff at-least some of them are negative.

Which is clearly not possible since we are dealing with whole numbers.

⇒ only possible answer remain (b).

$\endgroup$
0

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.