A positive integer is called "maybe prime" if all of its digits are primes and the number is not divisible by 2 or 3. Find the number of positive integers less than 10000 that are "maybe prime".
Seriously, GET RID OF THE COMPUTER PROGRAM!!!!!! This is only difficulty 2!
The valid digits are 2, 3, 5 and 7.
2 cannot be the last digit because the number needs to be odd.
Also exactly two of 3, 5 or 7 can be the last digit since they represent the three different congruency classes mod 3 and we need the last digit to not create a multiple of 3. Example, if we have 235X then the last digit X can be either 3 or 7; it cannot be 5 since 2355 is a multiple of 3.
So then for a number of d digits there are 2*4^(d-1) = 2^(2d-1) possible "maybe primes".
Less than 10000 means we look at d=1 through 4. 2^1 + 2^3 + 2^5 + 2^7 = 2 + 8 + 32 + 128 = 170 "maybe primes" under 10000.
Analytic Solution
