5
$\begingroup$

Take away $ \overline{MAD} $ from $ \overline{MADMADAM} $ to make her prime. $ \overline{ADAM} $ is prime too if he does not get mad: $ \overline{MADADAM}. $

$ M, A, D $ are 3 distinct digits that are to be determined by you so that the statements in this puzzle are true.

$\endgroup$
  • 2
    $\begingroup$ I don't know why but this puzzle infuriates me! (nice puzzle +1) $\endgroup$ – Adam May 4 at 21:06
  • 1
    $\begingroup$ @Adam computers fix everything :D $\endgroup$ – Brandon_J May 4 at 21:14
  • 4
    $\begingroup$ I understand Adam..nothing personal ..I couldn’t resist the palindrome rhyme to be included in the problem.. $\endgroup$ – Uvc May 4 at 21:16
  • 2
    $\begingroup$ From the statement "ADAM" is prime too if he does not get mad: "MADADAM", can we conclude that ADAM is a four-digit number, hence A != 0? Thus constraining A to 1..9? $\endgroup$ – smci May 6 at 11:16
  • 1
    $\begingroup$ Also, from "ADAM" is prime too if he does not get mad, are you saying MADADAM must be composite? or that's unspecified? If MADADAM must be composite, we can apply the simple divisiblity-by-n congruences for n=3,7,11 etc. to prune candidates. $\endgroup$ – smci May 7 at 2:28
9
$\begingroup$

So, we have two prime numbers (MADMADAM-MAD, ADAM).

Consequently, from a more mathematical standpoint,

$M*10,010,001 + A* 1,001,010 + D*100,100 - (M*100 + A*10 + D)$ is prime, as is $A*1,010 + D*100 + M$.

I ran this through a little program that I wrote, and I discovered that there are three distinct solution sets. They are:

  1. M: 1 A: 5 D: 8 --> $15,815,851 - 158 = 15,815,693‬$, which is prime. $5851$ is also prime.

  2. M: 3 A: 1 D: 6 --> $31,631,613 - 316 = 31,631,297‬$, which is prime. $1613$ is also prime.

  3. M: 3 A: 5 D: 6 --> $35,635,653 - 356 = 35,635,297$, which is prime. $5653$ is also prime.

If you're interested, here's the Java program that I wrote to find the answer. It probably isn't super efficient, but it works.

public class Test {

  public static void main(String[] args) {
      int big = 0;
      for(int i = 1; i<=9; i++) {
          for(int j = 1; j<=9; j++) {
              for(int k = 0; k<=9; k++) { //k (or d) is the only digit which could be 0.
                  if(isPrime(i*10010001 + j* 1001010 + k*100100 - (i*100 + j*10 + k))&&
                          isPrime(j*1010 + k*100 + i)) {
                      big = i*10010001 + j* 1001010 + k*100100 - (i*100 + j*10 + k);
                      System.out.println("M: " + i + " A: " + j + " D: " + k);
                      System.out.println(""+i+j+k+i+j+k+j+i+"-"+ i+j+k+"="+big+
                              ", which is prime. "+j+k+j+i+" is also prime.\n");
                  }
              }
          }
      }
  }
  public static boolean isPrime(int i) {
      boolean prime = true;
      for(int j = 2; j<=i/2; j++) {
          if (i%j==0) {
              prime = false;
              break;
          }
      }
      return prime;
  }
} 

$\endgroup$
  • 2
    $\begingroup$ Nice, but can you try a little more constraining and less brute-force in the solution? M has to be one of 1,3,7,9. D has to be even since MADMADAM-MAD is also prime and cannot end in 5. Hence (D-M) has to be congruent to one of 2,4,6,8 mod 10. A is then constrained by the D,M values such that ADAM is not divisible by either 3,9 or 11. $\endgroup$ – smci May 5 at 0:22
  • 1
    $\begingroup$ @smci perhaps you could create an answer with that logic? As it stands, the OP has not disallowed brute force, so my post fully answers the question. The logic that you mentioned would be a bit "extra" in my solution, but I'm fairly certain that you could craft a new answer where the logic fits in perfectly. My original algorithm didn't contain the modifications you mentioned largely because (just being honest) it was most straightforward to program it with minimal constraints. $\endgroup$ – Brandon_J May 5 at 0:43
  • $\begingroup$ I think algebraic solution is preferable (e.g. the 'MADMAD' part is clearly a multiple of 1001 = 7×11×13), but constrained-heuristic is okay. If anyone can give me more hints on constraints, I would code it up. Maybe if we develop the constraints enough, algebraic and constrained-heuristic will sort of meet-in-the-middle... $\endgroup$ – smci May 5 at 2:35
  • 1
    $\begingroup$ Yo, I posted my heuristic code that only needs to test 160 candidates for ADAM, of which only 52 prime candidates need to get the final check for the eight-digit (MADMADAM-MAD) also being prime. I think it's quite beautiful ;-) But perhaps you or others can suggest further improvements. $\endgroup$ – smci May 6 at 12:18
  • $\begingroup$ I am not a programmer currently. Your logic is good. When I created it, started from the phrase and known 1001 properties, came up with 193 91 3 193 91. I knew it won’t be unique. $\endgroup$ – Uvc May 8 at 12:33
2
$\begingroup$

Here's a better heuristic that only needs to test 52 candidates for ADAM, not all 10×9×8=720 candidates for M,D,A. Brute-forcing is an ugly sledgehammer, it's not scaleable. We can't get a pure algebraic solution, but let's try to refine things into an efficient constrained-search:

  • The prime 'ADAM' ends in M, hence M has to be one of [1,3,7,9]
  • D has to be even [0,2,4,6,8] since (MADMADAM-MAD) is also prime and thus cannot end in 5. (In fact you can get a better constraint due to its last digit (M-D) needing to be congruent to one of 2,4,6,8 mod 10, cannot be 0, but let's ignore that 20% improvement).
  • Last, A could be nearly anything: odd or even (and might even be zero, although the hint ADAM is prime is ambiguous about A==0). But also M,D,A must all be distinct, so there are only 8 choices for A (given M,D) instead of 10:
    • we only have to test at most 4×5×10 = 200 candidates for M,D,A
    • in fact only 4×5×8 = 160, due to the M,D,A-all-distinct constraint
  • But we were told ADAM is prime, which prunes it to only 52 ADAM candidates to check further...! Prime-testing 160 four-digit numbers is cheap.
  • (Ballpark estimation would have estimated since there are 1061 four-digit primes, D being even reduces those by 2x, and the 'ADAM' pattern locks the value of the third digit to the first, should further reduce them by ~10x, hence ~20x overall giving us 53. Actually turns out only 52 candidates.)
  • Last, we postpone the far most computationally expensive check if (MADMADAM-MAD) is prime, to only our 52 candidates for which ADAM is prime. I'm sure someone can find a better way than brute-force-testing 52 eight-digit numbers (e.g. we can prune a little with the well-known divisibility-by-3,7,11 tests).
  • (Update: Brandon_J: pointed out we all missed that MADADAM apparently must also be checked to be composite. That's just a trivial extra one-liner.)

Here's my Python 3 code:

from sympy import isprime

for m in [1,3,7,9]:
  for d in [0,2,4,6,8]:
    for a in range(10): # TODO refine constraints on a

      # Check all digits distinct
      if a==d or a==m: continue

      # Check ADAM must be prime
      if not isprime(1010*a + 100*d +m): continue
      #print(f'Checking A={a}, D={d}, M={m} | ADAM={a}{d}{a}{m} is prime')

      # Check MADMADAM-MAD is prime
      MADMADAM_minus_MAD = 10009901*m + 1001000*a + 100099*d
      if not isprime(MADMADAM_minus_MAD): continue

      print(f'Checking A={a}, D={d}, M={m} | ADAM={a}{d}{a}{m} prime | (MADMADAM-MAD)={MADMADAM_minus_MAD} prime')

# Solutions:    
Checking A=5, D=8, M=1 | ADAM=5851 prime | (MADMADAM-MAD)=15815693 prime
Checking A=1, D=6, M=3 | ADAM=1613 prime | (MADMADAM-MAD)=31631297 prime
Checking A=5, D=6, M=3 | ADAM=5653 prime | (MADMADAM-MAD)=35635297 prime

Can anyone suggest any further improvements on constraints or algebraically? In the for-loop that picks A, we could further constrain the choice of A (by congruences) such that it will not later fail either the divisibility-by-3 or -11 tests on either ADAM or (MADMADAM-MAD). Ballpark we might expect that to reduce to (2/3) * (10/11) ≈ 60% of candidates.

$\endgroup$
  • $\begingroup$ Very nice! It's definitely more elegant than my solution, although I guess we get to the same spot in the end. You might want to include your final answer, though :) $\endgroup$ – Brandon_J May 6 at 14:33
  • $\begingroup$ @Brandon_J: actually the three solutions are the ones shown in my answer. Confirms what you found. $\endgroup$ – smci May 6 at 15:12
  • $\begingroup$ Whoops, I was on mobile when I made that comment and I couldn't see the solutions :(. A thought: could we possibly improve the heuristics by noting that MADADAM and MADMADAM are not prime? $\endgroup$ – Brandon_J May 6 at 16:41
  • $\begingroup$ @Brandon_J: oh, I totally missed that: that MADADAM must also be checked to be composite. Sure, that's a trivial extra one-liner. But I'm really more interested in refining the constrained-search, to reduce the number of candidates as early, aggressively and simply as possible, before we get to primality-testing. $\endgroup$ – smci May 6 at 16:56

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.