Answer: I found 3 pairs of factorials which can be removed from the product list in order to achieve a perfect square:
(2, 11), (3, 12), (4, 12)
The specific prime factors of the product of the factorials 1 to 22:
[2, 3, 5, 7, 11, 13, 17, 19]
Those which occur an odd number of times:
[2, 7, 11]
Whatever factors are removed, we must remove an odd number of 2s 7s and 11s but an even number of the others.
For each n, make a list of the power for each prime factor for all the primes less than 22.
[2, 3, 5, 7,11,13 17,19]
{2: [1, 0, 0, 0, 0, 0, 0, 0],
3: [1, 1, 0, 0, 0, 0, 0, 0],
4: [3, 1, 0, 0, 0, 0, 0, 0],
5: [3, 1, 1, 0, 0, 0, 0, 0],
6: [4, 2, 1, 0, 0, 0, 0, 0],
7: [4, 2, 1, 1, 0, 0, 0, 0],
8: [7, 2, 1, 1, 0, 0, 0, 0],
9: [7, 4, 1, 1, 0, 0, 0, 0],
10: [8, 4, 2, 1, 0, 0, 0, 0],
11: [8, 4, 2, 1, 1, 0, 0, 0],
12: [10, 5, 2, 1, 1, 0, 0, 0],
13: [10, 5, 2, 1, 1, 1, 0, 0],
14: [11, 5, 2, 2, 1, 1, 0, 0],
15: [11, 6, 3, 2, 1, 1, 0, 0],
16: [15, 6, 3, 2, 1, 1, 0, 0],
17: [15, 6, 3, 2, 1, 1, 1, 0],
18: [16, 8, 3, 2, 1, 1, 1, 0],
19: [16, 8, 3, 2, 1, 1, 1, 1],
20: [18, 8, 4, 2, 1, 1, 1, 1],
21: [18, 9, 4, 3, 1, 1, 1, 1],
22: [19, 9, 4, 3, 2, 1, 1, 1]}
Convert this list to 1s and 0s for odds and evens
[2, 3, 5, 7,11,13 17,19]
{2: [1, 0, 0, 0, 0, 0, 0, 0],
3: [1, 1, 0, 0, 0, 0, 0, 0],
4: [1, 1, 0, 0, 0, 0, 0, 0],
5: [1, 1, 1, 0, 0, 0, 0, 0],
6: [0, 0, 1, 0, 0, 0, 0, 0],
7: [0, 0, 1, 1, 0, 0, 0, 0],
8: [1, 0, 1, 1, 0, 0, 0, 0],
9: [1, 0, 1, 1, 0, 0, 0, 0],
10: [0, 0, 0, 1, 0, 0, 0, 0],
11: [0, 0, 0, 1, 1, 0, 0, 0],
12: [0, 1, 0, 1, 1, 0, 0, 0],
13: [0, 1, 0, 1, 1, 1, 0, 0],
14: [1, 1, 0, 0, 1, 1, 0, 0],
15: [1, 0, 1, 0, 1, 1, 0, 0],
16: [1, 0, 1, 0, 1, 1, 0, 0],
17: [1, 0, 1, 0, 1, 1, 1, 0],
18: [0, 0, 1, 0, 1, 1, 1, 0],
19: [0, 0, 1, 0, 1, 1, 1, 1],
20: [0, 0, 0, 0, 1, 1, 1, 1],
21: [0, 1, 0, 1, 1, 1, 1, 1],
22: [1, 1, 0, 1, 0, 1, 1, 1]}
All that remains is to pick 2 rows which have exactly one 1 in the columns corresponding to 2, 7, 11 and either zero or two 0s in all the other columns.
For easier visualization: convert this to an 8-digit binary number, then convert that to a base 10 integer.
We want to find the pattern 10011000, which is 152 in decimal.
The program finds:
(2, 11)
[1, 0, 0, 1, 1, 0, 0, 0] 10011000 152
(3, 12)
[1, 0, 0, 1, 1, 0, 0, 0] 10011000 152
(4, 12)
[1, 0, 0, 1, 1, 0, 0, 0] 10011000 152
Double checking the actual numbers:
(2, 11)
916721622784419739131357336529936768408751192109880195772466
620882348353365612008120414919885047316860625465068202354889
325141770453672729389343703040000000000000000000000000000000
000000000^.5
=
302774110977874021257792042064146360242430404326554712030491
48084015385804800000000000000000000
(3, 12)
254644895217894371980932593480537991224653108919411165492351
839133985653712670002255670811079179810239062629185611765247
034761602903797980385928806400000000000000000000000000000000
00000000^.5
=
504623518296456702096320070106910600404050673877591186717485
8014002564300800000000000000000000
(4, 12)
636612238044735929952331483701344978061632772298527913730879
597834964134281675005639177027697949525597656572964029413117
586904007259494950964822016000000000000000000000000000000000
0000000^.5
252311759148228351048160035053455300202025336938795593358742
9007001282150400000000000000000000
------------
def prodfacs(alist):
""" compute the produce of factorials of a list of integers"""
ans = 1
for n in alist:
ans *= fac(n)
return ans
factorlist = []
for n in range(1,23):
factorlist += prime_factor(fac(n))
factorlist = sorted(factorlist)
oddcountfacs = []
listOfTheSet = list(set(factorlist))
for afac in listOfTheSet:
if factorlist.count(afac)%2 == 0:
continue
oddcountfacs.append(afac)
prime_powers = {}
for n in range(2,23):
myfacs = prime_factor(fac(n))
prime_powers[n] = []
for pr in [2, 3, 5, 7, 11, 13, 17, 19]:
prime_powers[n].append(myfacs.count(pr))
prime_powers_bin = {}
for k,v in prime_powers.items():
v_bin = [n%2 for n in v]
prime_powers_bin[k] = v_bin
from itertools import combinations
for comb in combinations([n for n in range(2,23)] , 2):
parity_list = []
for k in range(8):
parity_list.append((
prime_powers_bin[comb[0]][k] +
prime_powers_bin[comb[1]][k])%2)
binary_num = ''.join([str(digit) for digit in parity_list])
decimal_num = base2base(binary_num, 2, 10)
if decimal_num == 152:
print(comb)
print(parity_list,binary_num, decimal_num)
|
|
Posted by Larry
on 2024-11-29 12:37:52 |
Solution
