Every year I attempt to compete in math competitions at my school and I encounter problems such as...
How many prime numbers between 1000-10000 (inclusive) that if you take the sum of their digits, that number is divisible by 8. For example 17, 1+7=8. Which is divisible by 8.
We have to show our work. Does anyone have a solutions for these types of problems and how I could solve the problem above.
You know the maximum possible digit sum (ignoring the prime condition for a moment) is $36$, due to the digitsum from $9999$ within your range.
The possible digitsums under that barrier that are divisible by $8$ (ignoring $0$) are $8, 16, 24, 32$.
How many ways can you write each of these as a sum of $4$ digits where each digit falls within $0 \leq d \leq 9$?
If you were working in a team and had to do this by hand, you could probably divide-and-conquer and have each person tackle a different digitsum in order to enumerate all the cases more quickly.
However, you already know the $24$ digitsum is a waste of time, since any number whose digitsum is divisible by $24$ will also be divisible by $3$, which means the number itself will be divisible by $3$ and therefore not prime.
Then you can eliminate the cases that can't possibly be rearranged to form a prime number (such as those missing a $1, 3, 7$, or $9$ to form the last digit of the prime).
This leaves you with the following cases:
$8 = [[0, 0, 1, 7], [0, 0, 3, 5], [0, 1, 1, 6], [0, 1, 2, 5], [0, 1, 3, 4], [0, 2, 3, 3], [1, 1, 1, 5], [1, 1, 2, 4], [1, 1, 3, 3], [1, 2, 2, 3]]$
$16 = [[0, 0, 7, 9], [0, 1, 6, 9], [0, 1, 7, 8], [0, 2, 5, 9], [0, 2, 7, 7], [0, 3, 4, 9], [0, 3, 5, 8], [0, 3, 6, 7], [0, 4, 5, 7], [1, 1, 5, 9], [1, 1, 6, 8], [1, 1, 7, 7], [1, 2, 4, 9], [1, 2, 5, 8], [1, 2, 6, 7], [1, 3, 3, 9], [1, 3, 4, 8], [1, 3, 5, 7], [1, 3, 6, 6], [1, 4, 4, 7], [1, 4, 5, 6], [1, 5, 5, 5], [2, 2, 3, 9], [2, 2, 5, 7], [2, 3, 3, 8], [2, 3, 4, 7], [2, 3, 5, 6], [3, 3, 3, 7], [3, 3, 4, 6], [3, 3, 5, 5], [3, 4, 4, 5]]$
$32 = [[5, 9, 9, 9], [6, 8, 9, 9], [7, 7, 9, 9], [7, 8, 8, 9]]$
Then for each unique permutation of each case that falls within your acceptable range (also ending in $1, 3, 7$, or $9$), test if the number is actually prime. There are only $276$ numbers to test.
One way you can do this is by listing the (relevant) primes under $\sqrt{10000} = 100$:
$7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97$
Then you test each one for divisibility into your candidate number. If they all fail the test, then the candidate number is prime.
I assume you can at least use a calculator for this step, because otherwise this is probably too tedious a problem to do by hand. The size of your team would need to be large enough to be able to perform all the primality-check calculations in the time allotted.
Another approach (assuming you had a large enough team) is to divide the $1000-10000$ range up into chunks and have each person enumerate their section of the range and then use the segmented Sieve of Eratosthenes approach using the primes under $100$ to cross out the composite numbers. Then you can check the digitsums of the resulting primes directly.
Another approach is to start with all the three-digit numbers from $100$ to $999$. You append a units digit to each one to make the total digital sum $8$, $16$, or $32$ (not $24$ as this would imply a multiple of $3$). Each four-digit number is then tested for primality.
You do not really need to keep all the three-digit starting numbers. Those where the sum of the three digits is even are rejected because the units digit would have to be even, which is a problem. We also find:
Three-digit sums of $17$, $19$, and $21$ fail because we can't get the four-digit sum to $32$.
Three-digit sums of $3$, $11$, and $27$ fail because the appended units digit is $5$.
A three-digit sum of $7$ allows two candidates with $1$ or $9$ as a units digit, but other surviving three-digit sums give only one candidate per three-digit seed.
With these properties you drop your trials to a few hundred. Here is the beginning of the list of candidates:
1007 1043 1061 1069 1087 1133 1151 1159 1177 1223 1241 1249 1267 1313 1331 1339 1357 1393 1403 1421 1429 1447 1483 1511 1519 1537 1573 1591 1601 1609 1627 1663 1681 1717 1753 1771 1807 1843 1861 1933 1951 etc.
