Kenny has gone to a lecture by Jenny, a famous mathematician. Kenny tells Lenny that Jenny handed everyone at the lecture 2 cards, one containing a 5-digit prime, and the other containing a 5-digit square. All of the cards held different numbers.
Then she asked everyone to add their 2 numbers, and amazingly they all got the same sum. Kenny says it's lucky that Lenny didn't attend, because then the trick would have been impossible.
What was the sum they all got?
There are 8363 5-digit primes and 217 5-digit squares.
Loop through every possible pair, note the sum and make a dictionary where the keys are the various sums, and each value is a list of the lists of [prime,square] pairs which add to that sum.
Once the dictionary is formed, find which key (which sum) corresponds to the most pairs. This will be the upper limit on the number of lecture attendees.
It turns out that 101888 is the sum that corresponds to the most (prime,square) pairs; there are 69 of them.
There are no sums that share more than 69 such pairs.
There were 69 attendees already, Lenny would have made 70 and it would have been impossible. The attendees' cards all summed to 101888
101888 [[10079, 91809], [11287, 90601], [12487, 89401], [13679, 88209], [17207, 84681], [18367, 83521], [20663, 81225], [21799, 80089], [26263, 75625], [28447, 73441], [29527, 72361], [31663, 70225], [32719, 69169], [33767, 68121], [34807, 67081], [35839, 66049], [37879, 64009], [39887, 62001], [40879, 61009], [41863, 60025], [42839, 59049], [46663, 55225], [47599, 54289], [48527, 53361], [50359, 51529], [51263, 50625], [53047, 48841], [53927, 47961], [54799, 47089], [55663, 46225], [56519, 45369], [57367, 44521], [58207, 43681], [59863, 42025], [60679, 41209], [61487, 40401], [63079, 38809], [63863, 38025], [65407, 36481], [66919, 34969], [68399, 33489], [69127, 32761], [69847, 32041], [71263, 30625], [72647, 29241], [73327, 28561], [73999, 27889], [75967, 25921], [76607, 25281], [77239, 24649], [77863, 24025], [78479, 23409], [79087, 22801], [79687, 22201], [80279, 21609], [80863, 21025], [81439, 20449], [82007, 19881], [82567, 19321], [83663, 18225], [84199, 17689], [85247, 16641], [86263, 15625], [88663, 13225], [89119, 12769], [89567, 12321], [90007, 11881], [90439, 11449], [90863, 11025]]
----------------
def isprime(n):
'''check if integer n is a prime'''
n = abs(int(n))
if n < 2:
return False
if n == 2:
return True
if not n & 1:
return False
for x in range(3, int(n**0.5)+1, 2):
if n % x == 0:
return False
return True
primes = [p for p in range(10001,99999,2) if isprime(p)]
squares = [i**2 for i in range(100,317)]
sumDict = {}
for p in primes:
for s in squares:
x = p+s
if x not in sumDict:
sumDict[x] = [[p,s]]
else:
sumDict[x].append([p,s])
lengths = []
for a in sumDict:
lengths.append(len(sumDict[a]))
longest = max(lengths)
print(longest)
for a in sumDict:
if len(sumDict[a]) == longest:
print(a, sumDict[a])
|
Posted by Larry
on 2023-12-16 10:57:32 |