Alice, Samantha, and Patricia are relaxing on the porch, when Alice suddenly says: _"I'm thinking of two numbers, both greater than or equal to 2. I shall tell Samantha the sum of the two numbers and Patricia the product of the two numbers."_ 

She takes Samantha aside and whispers in her ear the sum so that Patricia cannot hear it. Then she takes Patricia aside and whispers in her ear the product so that Samantha cannot hear it.

After a moment of reflection, Samantha says:

 **Statement 1:** _"Patricia cannot know what the two numbers are."_

After which Patricia says:

 **Statement 2:**  _"In that case, I do know what the two numbers are."_

To which Samantha replies:

 **Statement 3:**  _"Then I too know what the two numbers are."_

Your first task is to write a function `statement1(s)` that takes an `int` argument `s` and returns `True` if and only if Samantha could have made statement 1 if given the number `s`. You may assume that `s` is the sum of two numbers both greater than or equal to 2.  

Your second task is to write a function `statement2(p)` that takes an `int` argument `p` and returns `True` if and only if Patricia, when given the number `p`, could have made statement 2 after hearing Samantha make statement 1. You may assume that `p` is the product of two numbers both greater than or equal to 2 and that Patricia would not have been able to determine the two numbers by looking at `p` alone.

Your third task is to write a function `statement3(s)` that takes an `int` argument `s` and returns `True` if and only if Samantha, when given the number `s`, could have made statement 3 after hearing Patricia make statement 2.

Finally, it is to you to figure out what two numbers Alice was thinking of. Since there are multiple solutions, you must write a function `is_solution(a, b)` that returns `True` if and only if `a` and `b` could have been two numbers that Alice was thinking of.

Hint: To get you started, think of what Samantha's first statement implies. Samantha knows that Patricia was not given the product of two primes. That means that the sum that Samantha was given cannot be written as the sum of two primes. Goldbach's conjecture stipulates that every even number greater than 3 can be written as the sum of two primes. Although Goldbach's conjecture has not yet been proven, you may assume that it has been verified for all numbers involved in the test cases here. So we know that the sum that Samantha was given must be odd. The only way to write an odd number as the sum of two primes is when one of the primes is 2, the only even prime. This means that the number given to Samantha is not the sum of 2 and a prime.

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Complete search

Ad-hoc

Starter code: def statement1(s):
	

Solutions:
def is_prime(n):
	return n == 2 or (n % 2 != 0 and all((n % k != 0 for k in range(3, root(n) + 1, 2))))

def root(p):
	return int(p ** 0.5)

def statement1(s):
	return not (s % 2 == 0 or is_prime(s - 2))

def statement2(p):
	return sum((statement1(i + p / i) for i in range(2, root(p) + 1) if p % i == 0)) == 1

def statement3(s):
	return sum((statement2(i * (s - i)) for i in range(2, s / 2 + 1))) == 1

def is_solution(a, b):
	return statement1(a + b) and statement2(a * b) and statement3(a + b)


def statement1(s):
	return not prime(s - 2) and (not s % 2 == 0)

def statement2(p):
	l = [i for i in factor_pairs(p) if i[0] >= 2 and i[1] >= 2]
	l_ = [i for i in l if statement1(sum(i))]
	return l != l_ and len(l_) == 1

def statement3(s):
	return len([(i, s - i) for i in range(2, s // 2 + 1) if statement2(i * (s - i))]) == 1

def is_solution(a, b):
	return statement1(a + b) and statement2(a * b) and statement3(a + b)

def prime(x):
	x = int(x)
	for i in range(2, x):
		if x % i == 0:
			return False
	return True

def factor_pairs(x):
	res = set([])
	for i in range(1, x):
		if x % i == 0:
			res.add(tuple(sorted([i, x / i])))
	return sorted([[int(j) for j in i] for i in list(res)], key=lambda x: x[0])


from math import sqrt
is_prime = lambda x: all((x % y != 0 for y in range(2, int(sqrt(x)) + 1)))
statement1 = lambda s: s % 2 > 0 and (not is_prime(s - 2))
statement2 = lambda p: 1 == sum((p % i == 0 and statement1(i + p // i) for i in range(2, int(sqrt(p)) + 1)))
statement3 = lambda s: 1 == sum((statement2(i * (s - i)) for i in range(2, s // 2 + 1)))
is_solution = lambda a, b: statement1(a + b) and statement2(a * b) and statement3(a + b)


from functools import reduce

def isPrime(n):
	d = 2
	while True:
		if n % d == 0:
			return False
		if d * d > n:
			return True
		d += 1

def primeFactor(n):
	d = 2
	factors = []
	while True:
		if n % d == 0:
			factors.append(d)
			n = n // d
		else:
			d += 1
		if n == 1:
			return factors
		elif d * d > n:
			return factors + [n]

def get_cases(nums):
	nums_plus = list(map(lambda x: x + 1, nums))
	total_cases = reduce(lambda x, y: x * y, nums_plus)
	for i in range(total_cases):
		v = i
		cases = []
		for n in nums_plus:
			cases.append(v % n)
			v = v // n
		yield cases

def statement1(s):
	if s % 2 == 0:
		return False
	return not isPrime(s - 2)

def statement2(p):
	factors = primeFactor(p)
	if len(factors) == 2:
		return False
	factors_set = set(factors)
	factor_tuples = []
	for factor in factors_set:
		factor_tuples.append((factor, factors.count(factor)))
	sum_set = set()
	nums = [x[1] for x in factor_tuples]
	for case in get_cases(nums):
		v1 = v2 = 1
		if sum(case) == 0 or sum(case) == len(factors):
			continue
		for (i, n) in enumerate(case):
			v1 *= factor_tuples[i][0] ** (factor_tuples[i][1] - n)
			v2 *= factor_tuples[i][0] ** n
		sum_set.add(v1 + v2)
	if sum([statement1(x) for x in sum_set]) == 1:
		return True
	return False

def statement3(s):
	if statement1(s) == False:
		return False
	if sum([statement2(x * (s - x)) for x in range(2, s // 2 + 1)]) == 1:
		return True
	return False

def is_solution(a, b):
	return statement3(a + b)


import math

def statement1(s):
	if s % 2 == 0:
		return False
	if is_prime(s - 2):
		return False
	return True

def statement2(p):
	if p % 2 != 0:
		return False
	facs = []
	for i in range(2, int(math.sqrt(p)) + 1):
		if p % i == 0:
			facs.append((i, int(p / i)))
	c = 0
	for f in facs:
		if statement1(f[0] + f[1]):
			c += 1
			if c > 1:
				return False
	return c == 1

def statement3(s):
	c = 0
	if not statement1(s):
		return False
	for i in range(2, s // 2):
		if statement2(i * (s - i)):
			c += 1
			if c > 1:
				return False
	return c == 1

def is_solution(a, b):
	return statement1(a + b) and statement2(a * b) and statement3(a + b)

def is_prime(n):
	if n < 2 or (n > 2 and n % 2 == 0):
		return False
	for i in range(3, int(math.sqrt(n)) + 1, 2):
		if n % i == 0:
			return False
	return True


def is_prime(n):
	if n == 2:
		return True
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def factor(n):
	res = []
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			res.append((i, n // i))
	return res

def statement1(s):
	if s % 2 == 0:
		return False
	elif is_prime(s - 2):
		return False
	else:
		return True

def statement2(p):
	factors = factor(p)
	count = 0
	for (f1, f2) in factors:
		tests = [(f1 + f2) % 2 != 0, not is_prime(f1 + f2 - 2), not (is_prime(f1) and is_prime(f2))]
		if all(tests):
			count += 1
	return count == 1

def statement3(s):
	if not statement1(s):
		return False
	pairs = [(x, s - x) for x in range(2, s // 2)]
	count = 0
	for (p1, p2) in pairs:
		if statement2(p1 * p2):
			count += 1
	return count == 1

def is_solution(a, b):
	return all([statement1(a + b), statement2(a * b), statement3(a + b)])


def isPrime(n):
	return n is 2 or (n % 2 is not 0 and all((n % i != 0 for i in range(3, int(n ** 0.5) + 1, 2))))

def statement1(s):
	return not (s % 2 is 0 or isPrime(s - 2))

def statement2(p):
	return sum((statement1(i + int(p / i)) for i in range(2, int(p ** 0.5) + 1) if p % i == 0)) is 1

def statement3(s):
	return sum((statement2(i * (s - i)) for i in range(2, int(s / 2) + 1))) is 1

def is_solution(a, b):
	return statement3(a + b)


import itertools

def statement1(s):
	return s % 2 and (not is_prime(s - 2))

def statement2(p):
	return len(get_posses(p)) == 1

def statement3(s):
	posses = ([a, s - a] for a in range(s))
	posses = {tuple(sorted(i)) for i in posses if min(i) >= 2}
	finals = [[a, b] for [a, b] in posses if statement2(a * b)]
	return len(finals) == 1

def is_solution(a, b):
	return statement1(a + b) and statement2(a * b) and statement3(a + b)

def get_posses(p):
	posses = [(a, b) for (a, b) in ineff_poss_factors(p) if statement1(a + b)]
	return posses

def is_prime(n):
	return len(list(prime_factors(n))) == 1

def ineff_poss_factors(n):
	for i in itertools.count(start=2):
		if i ** 2 > n:
			break
		if not n % i:
			yield (i, n // i)

def prime_factors(n):
	for i in itertools.count(start=2):
		if i ** 2 > n:
			break
		if not n % i:
			yield i
			n //= i
	if n > 1:
		yield n


primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
for i in range(37, 500, 2):
	if all((i % j for j in primes)):
		primes.append(i)

def statement1(s):
	return s % 2 and s - 2 not in primes

def statement2(p):
	possible_pairs = set()
	for i in range(2, int(p ** 0.5) + 2):
		if p % i == 0:
			possible_pairs.add((i, p // i))
	good_pairs = [statement1(i + j) for (i, j) in possible_pairs]
	return sum(good_pairs) == 1

def statement3(s):
	possible_pairs = set()
	for i in range(2, s // 2 + 2):
		possible_pairs.add((i, s - i))
	good_pairs = [statement2(i * j) for (i, j) in possible_pairs]
	return sum(good_pairs) == 1

def is_solution(a, b):
	return statement1(a + b) and statement2(a * b) and statement3(a + b)