For every m and n in the set of natural numbers, there exists an k in the natural numbers such that m = 7k + 3 and there exists a j in the natural numbers such that n = 7j + 4 imples that there exists an i in the natural numbers such that mn = 7i + 5.
First, I made the following:
def is_m(num): #7k + 3 = m
return ((num - 3) // 7) == ((num - 3) / 7)
def is_n(num): #7j + 4 = n
return ((num - 4) // 7) == ((num - 4) / 7)
def is_mn(num): #7i + 5 = mn
return ((num - 5) // 7) == ((num - 5) / 7)
This checks that we can represent the number as m or n or as mn. Let's consider 10, 18, 26, 27.
10 18 26 27
is_m T F F F
is_n F T F F
is_mn F F T F
As we can see here, we can write 10 in m-form, 18 in n-form and 26 in mn-form. But what are the values of k, j or i? We use the following to figure it out.
def k_value(m): #check with is_m(m)
m = m - 3
temp = m / 7
if (m // 7) == temp:
return int(temp)
else:
return False
def j_value(n): #check with is_n(n)
n = n - 4
temp = n / 7
if (n // 7) == temp:
return int(temp)
else:
return False
k_value(10) returns 1 which means that if we considered m = 10, then in m = 7k + 3, k = 1. With j_value(18), 2 is returned meaning that if n = 18 and n = 7j + 4, j = 2. Using these random m and n, we can try to see if the two imply an mn:
def m_and_n_imply_mn_v1(m, n): #simple
k = k_value(m)
j = j_value(n)
mn = m * n
polynomial = 7*(7*j*k + 3*j + 4*k + 1) + 5
return mn == polynomial
m_and_n_imply_mn_v1(10, 18) returns True but the explanation behind why polynomial is written the way it is seems unclear. First we need to consider what the i value, which seems to be replaced by the polynomial within polynomial.
def i_value(m, n): #check with is_mn(m * n)
mn = m * n
mn = mn - 5
temp = mn / 7
if (mn // 7) == temp:
return int(temp)
else:
return False
i_value(10, 18) returns 25 meaning that the product of 10 and 18 equals to 7 times 25 plus 5. To see this more clearly, we use a more complex version of m_and_n_imply_mn:
def m_and_n_imply_mn_v2(m, n): #detailed
i = i_value(m, n)
k = k_value(m)
j = j_value(n)
if i == (7*j*k + 3*j + 4*k + 1):
sub_poly = str(7*j*k) + ' + ' + str(3*j) + ' + ' + str(4*k) + ' + 1'
seven_jk = '7*' + str(j) + '*' + str(k)
three_j = '3*' + str(j)
four_k = '4*' + str(k)
sub_rep = seven_jk + ' + ' + three_j + ' + ' + four_k + ' + 1'
print('j = ' + str(j) + ', k = ' + str(k) + ', i = ' + str(i) + ', m = '
+ str(m) + ', n = ' + str(n) + ', mn = ' + str(m * n) )
print('i = 7jk + 3j + 4k + 1')
print(str(i) + ' = ' + sub_poly)
print(sub_poly + ' = ' + sub_rep)
print('7i + 5 = mn -> ' + '7*' + str(i) + ' + 5 = ' + str(m * n))
print('m*n = ' + str(m) + '*' + str(n) + ' = ' + str(m * n))
print('Therefore m = 7k + 3 and n = 7j + 4 imply mn = 7i + 5')
else:
return False
m_and_n_imply_mn_v2(10, 18) prints out the following:
j = 2, k = 1, i = 25, m = 10, n = 18, mn = 180
i = 7jk + 3j + 4k + 1
25 = 14 + 6 + 4 + 1
14 + 6 + 4 + 1 = 7*2*1 + 3*2 + 4*1 + 1
7i + 5 = mn -> 7*25 + 5 = 180
m*n = 10*18 = 180
Therefore m = 7k + 3 and n = 7j + 4 imply mn = 7i + 5
Now if we consider a random mn such as 26, we need to modify i_value like so:
def i_value_mn(mn): #check with is_mn(mn)
mn = mn - 5
temp = mn / 7
if (mn // 7) == temp:
return int(temp)
else:
return False
i_value_mn(26) returns 3. This makes the converse implication false since there is no way that 3 = 7jk + 3j + 4k + 1 can be represented by natural numbers. Consider the following.
m_and_n_imply_mn_v2(3, 4):
j = 0, k = 0, i = 1
i = 7jk + 3j + 4k + 1
1 = 0 + 0 + 0 + 1
0 + 0 + 0 + 1 = 7*0*0 + 3*0 + 4*0 + 1
7i + 5 = mn -> 7*1 + 5 = 12
m_and_n_imply_mn_v2(10, 4):
j = 0, k = 1, i = 5
i = 7jk + 3j + 4k + 1
5 = 0 + 0 + 4 + 1
0 + 0 + 4 + 1 = 7*0*1 + 3*0 + 4*1 + 1
7i + 5 = mn -> 7*5 + 5 = 40
m_and_n_imply_mn_v2(3, 11):
j = 1, k = 0, i = 4
i = 7jk + 3j + 4k + 1
4 = 0 + 3 + 0 + 1
0 + 3 + 0 + 1 = 7*1*0 + 3*1 + 4*0 + 1
7i + 5 = mn -> 7*4 + 5 = 33
i can equal 1, 4 and 5 at low values of natural j and k but not 2 nor 3.
Conclusion:
- m and n imply mn
- mn does not completely imply m or n
#####################################
Bonus: As an extension of my previous entry, I have here all of the code for the penny piles problem:
def half_l2r(drawers):
""" (list of ints) -> list of ints
Precondition: len(drawers) == 2
Return drawers with half of drawers[0] added to drawers[1]
>>> half_l2r([64, 0])
[32, 32]
"""
ret = list(drawers)
if drawers[0] % 2 == 0:
ret[0] = drawers[0] // 2
ret[1] = drawers[1] + ret[0]
return ret
def half_r2l(drawers):
""" (list of ints) -> list of ints
Precondition: len(drawers) == 2
Return drawers with half of drawers[1] added to drawers[0]
>>> half_r2l([16, 32])
[32, 16]
"""
ret = list(drawers)
if drawers[1] % 2 == 0:
ret[1] = drawers[1] // 2
ret[0] = drawers[0] + ret[1]
return ret
def prime_factors(n): #returns the prime factors of a number
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
def product_list(L): #returns the product of the items in a list
product = 1
for item in L:
product = product * item
return product
def is_multiple(x, n): #is x a multiple of n?
is_it = False
if x == n:
is_it = True
else:
i = 1
y = n
while x != y and y < x:
i = i + 1
y = n * i
if x == y:
is_it = True
return is_it
def possible_products(L): #returns the possible products
poss_prod = []
if len(L) == 2:
product = L[0] * L[1]
poss_prod.append(product)
elif len(L) > 2:
i = 0
while i < len(L):
sub = list(L)
sub.remove(sub[i])
sub_prods = possible_products(sub)
j = 0
while j < len(sub_prods):
temp1 = sub_prods[j] * L[i]
temp2 = sub_prods[j]
j = j + 1
if temp1 not in poss_prod:
poss_prod.append(temp1)
if temp2 not in poss_prod:
poss_prod.append(temp2)
i = i + 1
return poss_prod
def poss_prod_fixer(poss_prod): #fixes the results of possible_products
poss_prod.sort()
poss_prod.reverse()
poss_prod.remove(poss_prod[0]) #we do not want the product of all integers
def penny_possible_halving(drawers, penny_goal):
""" (list of ints, int) -> bool
Precondition: len(drawers) == 2 and (drawers[0] == 0 or drawers[1] == 0)
Return if drawers can be resorted so that one value equals penny_goal
using half_l2r and half_r2l
>>> penny_possible([64, 0], 40)
True
>>> penny_possible([0, 34], 2)
False
"""
gen_L = [] #For convenience, we will refer to this as a generic list
gen_L.append(drawers)
i = 0
while i < len(gen_L):
if gen_L[i][0] == penny_goal or gen_L[i][1] == penny_goal:
return True
if gen_L[i][0] % 2 == 0 and gen_L[i][0] != 0:
l1 = half_l2r(gen_L[i])
if l1 not in gen_L:
gen_L.append(l1)
if gen_L[i][1] % 2 == 0 and gen_L[i][1] != 0:
l2 = half_r2l(gen_L[i])
if l2 not in gen_L:
gen_L.append(l2)
i = i + 1
return False
def penny_possible_conditions(drawers, penny_goal):
"""(list of ints, int) -> bool
Precondition: len(drawers) == 2 and (drawers[0] == 0 or drawers[1] == 0)
Return if drawers can be resorted so that one value equals penny_goal
using conditions and factorization
>>> penny_possible([64, 0], 40)
True
>>> penny_possible([0, 34], 2)
False
"""
q = drawers[0] + drawers[1]
primes = prime_factors(q)
if penny_goal > q:
return False
#considering [q, 0]
if (drawers[0] == 0 or drawers[1] == 0) and drawers[0] != drawers[1] :
if primes.count(2) == len(primes): #q = 2 ** r
return True
elif primes.count(2) != len(primes) and primes.count(2) > 0:
#q = (2 ** r) * n
if penny_goal == 0 or penny_goal == q:
return True
else:
while primes.count(2) > 0:
primes.remove(2)
multiple = product_list(primes)
return is_multiple(penny_goal, multiple)
#penny_goal is only reached when it is a multiple of n
elif primes.count(2) == 0:
return penny_goal == 0 or penny_goal == q
if drawers[0] % 2 == 0 and drawers[1] % 2 == 0: #considering [e, e]
if drawers[0] != 0 and drawers[1] != 0:
if drawers[0] == drawers[1]:
if primes.count(2) == len(primes):
return 0 < penny_goal < q
elif primes.count(2) != len(primes):
if penny_goal == 0 or penny_goal == q:
return False
while primes.count(2) > 0:
primes.remove(2)
multiple = product_list(primes)
return is_multiple(penny_goal, multiple)
else:
if primes.count(2) == len(primes):
return penny_possible_halving(drawers, penny_goal)
elif primes.count(2) != len(primes):
if penny_goal == 0 or penny_goal == (q/2) or penny_goal == q:
return False
while primes.count(2) > 0:
primes.remove(2)
multiple = product_list(primes)
multicheck_1 = is_multiple(drawers[0], multiple)
multicheck_2 = is_multiple(drawers[1], multiple)
if multicheck_1 and multicheck_2:
return is_multiple(penny_goal, multiple)
else:
return 0 < penny_goal < q
if drawers[0] % 2 == 1 and drawers[1] % 2 == 1: #considering [o, o]
return penny_goal == drawers[0] or penny_goal == drawers[1]
if (drawers[0] % 2 == 0 and drawers[1] % 2 == 1) or (drawers[0] % 2 == 1 and drawers[1] % 2 == 0): #considering [e, o] or [o, e]
if penny_goal == q or penny_goal == 0:
return False
if q == primes[0]: #q is a prime number
return 0 < penny_goal < q
else: #q is not a prime number
if len(primes) == 2: #q = n1 * n2
both_multiples = False
multiple = None
for item in primes:
multicheck_1 = is_multiple(drawers[0], item)
multicheck_2 = is_multiple(drawers[1], item)
if multicheck_1 and multicheck_2:
both_multiples = True
multiple = item
if multiple != None: #both items in list are a multiple of any n
return is_multiple(penny_goal, multiple)
else: #both items are not a multiple of any n
for item in primes:
multiple = item
if is_multiple(penny_goal, multiple):
return False
return 0 < penny_goal < q
else: #len(primes) > 2
both_multiples = False
multiple = None
multiples = primes
prod_of_primes = possible_products(primes)
poss_prod_fixer(prod_of_primes)
multiples.extend(prod_of_primes)
multiples.sort()
conflict = 0
for item in multiples:
multicheck_1 = drawers[0] % item
multicheck_2 = drawers[1] % item
if multicheck_1 == 0 and multicheck_2 == 0:
both_multiples = True
multiple = item
if multiple != None: #both items in list are a multiple of a N/n
iron_multiple = multiples.pop(multiples.index(multiple))
for item in multiples:
multiple = item
if multiple > iron_multiple:
if penny_goal % multiple == 0:
return False
return True
else: #both items are not a multiple of any n/N
for item in multiples:
multiple = item
if penny_goal % multiple == 0:
return False
return 0 < penny_goal < q
No comments:
Post a Comment