As requested I'm posting this an answer. I wrote a short sage script to check the primality of numbers of the form $10^n+333$ where $n$ is in the range $[4,2000]$. I found that the following values of $n$ give rise to prime numbers:
$$4,5,6,12,53,222,231,416.$$
Edit 3: I stopped my laptop's search between 2000 and 3000, since it hadn't found anything in 20 minutes. I wrote a quick program to check numbers of the form $10^n+3*10^i+33$. Here are a couple
- 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000300033
- 100000000000000000000000000000000000000000000000000000300000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000033
- 100000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000033
- 10000000000000000000000000000000003000000033
- 10000000000000000000000000000030000000000033
- 10000000000000000000000030000000000000000033
- 10000000003000000000000000000000000000000033
There seemed to be plenty of numbers of this form and presumably I could find more if I checked some of the other possible forms as outlined by dr jimbob.
Note: I revised the post a bit after jimbob pointed out I was actually looking for primes that didn't quite fit the requirements.
Edit 4: As requested here are the sage scripts I used.
To check if $10^n+333$ was prime:
for n in range(0,500):
k=10^n+333
if(is_prime(k)):
print n
And to check for numbers of the form $10^n+3*10^i+33$:
for n in range(0,500):
k=10^n+33
for i in range(2,n):
l=k+3*10^i
if(is_prime(l)):
print l
Best Answer
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.