# Crack the Code #1

You are a bank robber, and you come across a safe. It has a combination lock of 4 digits. Careful research (and stealing papers at the bank) has given you multiple clues as to the code - just barely enough to figure it out.

Digits are referred to as A-B-C-D in the clues. "A + B" is the sum of the first and second digit. All math follows the standard order of operations

Clues

• The sum of the digits is greater than (A * B) - (C * D).
• The product of the digits plus their sum is divisible by A and C only.
• The number is prime
• The first digit is greater than 6

What four digit number matches these criteria? Also, if you want, post your methodology for finding the correct answer, as this will help me in the future.

Note: I am pretty sure that only one number matches all these clues. However, I may have miscalculated. Please correct me in the comments.

edited to match intended question:

given that the number is prime, the only potentially valid combination is 8017.

8017:

• 8+0+1+7 = 16, 8*0 - 1*7 = -7, 16 > -7
• 8*0*1*7 + 8+0+1+7 = 16, divisible by 8 and 1, but not 7. 0 is undefined.
• 8017 is prime.
• 8 > 6.

This depends on the assumption that 0 does not divide 16 evenly, which depends on your definition. This can go either way - 16/0 is undefined, so you could say that (0 divides 16) is undefined. Or, since there's no m such that m*0 = 16, you could say that (0 divides 16) is false.

Methodology is pretty simple. for all numbers 0000-9999, have a computer check if it matches all conditions.

• Nice. I was kind of afraid people would use a program to find it, but this is the easiest way (and this is how I generated it). Glad to see that my puzzle was at least solvable. – mdc32 Oct 22 '14 at 23:33
• @mdc32 You could ask on Mathematics, but it seems unlikely that this is solvable without brute force. – MattPutnam Oct 23 '14 at 5:50

C# Version:

var numbers = (from int n in Enumerable.Range(7000, 3000)
let a = (n / (int)Math.Pow(10, 3)) % 10
let b = (n / (int)Math.Pow(10, 2)) % 10
let c = (n / (int)Math.Pow(10, 1)) % 10
let d = n % 10
let prodSum = a + b + c + d + (a * b * c * d)
where ((c > 0) &&
((a + b + c + d) > ((a * b) - (c * d))) &&
(prodSum % a == 0) &&
((b == 0) || (prodSum % b != 0)) &&
(prodSum % c == 0) &&
((d == 0) || (prodSum % d != 0)) &&
(!Enumerable.Range(2, (n - 2)).Any(o => n % o == 0)))
select n);

Console.WriteLine(string.Join(", ", numbers));


My Ruby version had an optimization: I started here and got a list of all primes greater than or equal to 7000 (since the first digit was strictly larger than 6) and less than or equal to 9999 (the largest possible combination). There are only 329 of those values, so it's a much better place to start than iterating through 10,000 values blindly.

vals = [7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973]
vals.each do |v|
digits = v.to_s.chars.map(&:to_i)
digitsum = digits.inject(:+)
digitprod = digits.inject(:*)
digitval = digitprod+digitsum
if (digitsum > digits[0]*digits[1] - digits[2]*digits[3]) &&
(digits[0] != 0) &&
(digitval % digits[0] == 0) &&
(digits[2] != 0) &&
(digitval % digits[2] == 0)
puts "#{v}"
end
end


Methodology is pretty simple. for all numbers 0000-9999, have a computer check if it matches all conditions.

Here you have the actual programme (Python 3.x):

for A in range(7,10):
for B in range(0,10):
for C in range(1,10):
for D in range(0,10):
if sum([A,B,C,D]) > ((A*B)-(C*D)):
prod_and_sum = (A*B*C*D) + sum([A,B,C,D])
if prod_and_sum % A == 0 and prod_and_sum % C == 0:
number = A*(10**3) + B*(10**2) + C*(10**1) + D
if not [i for i in range(2,number) if number % i == 0]:
print(number)


8017

Trick is here to iterate until all conditions return true thus meaning that this is the number the bank robber is looking for.

This is program I used for this computation. It is written in standard Java.

public class BankRobberProblem implements SingleSolution<Integer> {

public static void main(String[] args) {
SingleSolution bankRobberProblem = new BankRobberProblem();
System.out.println(bankRobberProblem.solveSingle());
}

@Override
public Integer solveSingle() {
for (int a = 0; a < 10; a++) {
for (int b = 0; b < 10; b++) {
for (int c = 0; c < 10; c++) {
for (int d = 0; d < 10; d++) {
if ((a * b) - (c * d) < a + b + c + d) {
int productAndSum = (a * b * c * d) + (a + b + c + d);
if (a != 0 && c != 0) {
if (productAndSum % a == 0 && productAndSum % c == 0) {
Integer n = Integer.valueOf(String.format("%s%s%s%s", a, b, c, d));
boolean prime = true;
if (n % 2 == 0) prime = false;
for (int i = 3; i * i <= n; i += 2) {
if(n % i == 0) prime = false;
}
if (prime) {
if (a > 6) {
return n;
}
}
}
}
}
}
}
}
}

return null;
}
}


This program is for Java 8 only but yields faster results then the previous.

public class BankRobberProblem implements SingleSolution<Integer> {

public static void main(String[] args) {
BankRobberProblem bankRobberProblem = new BankRobberProblem();
System.out.println(bankRobberProblem.solveSingle());
}

@Override
public Integer solveSingle() {
return IntStream.rangeClosed(7000, 9999).parallel() // The first digit is greater than 6
.filter(n -> {
boolean prime = true;
if (n % 2 == 0) prime = false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) prime = false;
}
return prime;
}) // The number is prime
.filter(value -> {
List<Integer> s = seperate(value);
if (a(s) != 0 && c(s) != 0) {
int productAndSum = (a(s) * b(s) * c(s) * d(s)) + (a(s) + b(s) + c(s) + d(s));
if (productAndSum % a(s) == 0 && productAndSum % c(s) == 0) {
return true;
}
}
return false;
}) // The product of the digits plus their sum is divisible by A and C only.
.filter(value -> {
List<Integer> s = seperate(value);
if ((a(s) * b(s)) - (c(s) * d(s)) < a(s) + b(s) + c(s) + d(s)) {
return true;
}
return false;
}) // The sum of the digits is greater than (A * B) - (C * D).
.findFirst()
.orElse(0);
}

private List<Integer> seperate(Integer n) {
List<Integer> result = new ArrayList<>();
while (n > 0) {
n = n / 10;
}
Collections.reverse(result);
return result;
}

private Integer a(List<Integer> l) {return l.get(0);}
private Integer b(List<Integer> l) {return l.get(1);}
private Integer c(List<Integer> l) {return l.get(2);}
private Integer d(List<Integer> l) {return l.get(3);}

}


I, as well, have written a program for this, this time in Node.js

Also, you do not need to start at 0; the number has to be at least 4 digits and a has to be bigger than 6, so start at 7000 (Or 7111 if there's no 0 on it)!

The answer I got was 8017 as well

Code:

http://pastebin.com/LFiQGLMU