And you thought it was impossible, MD XF...
If it gives the wrong result, just increase the 100 to something larger. I think 10000 will work for 4 but I'll leave my computer running overnight to confirm that; it may take a couple of hours to finish.
And you thought it was impossible, MD XF...
If it gives the wrong result, just increase the 100 to something larger. I think 10000 will work for 4 but I'll leave my computer running overnight to confirm that; it may take a couple of hours to finish.
If it gives the wrong result, just increase the 100 to something larger. I think 10000 will work for 4 but I'll leave my computer running overnight to confirm that; it may take a couple of hours to finish.
97. [Python 3 Python 3 (PyPy)(PyPy)], 1772 bytes, A000236
plist = [] def primes(maximal = -1): # Semi-efficient prime number generator with caching up to a certain maximal, or forevermax. index = plist and plist[-1] or 2 for prime in plist: if prime <= maximal or maximal == -1: yield prime else: break while index <= maximal or maximal == -1: composite = False for prime in plist: if index % prime == 0: composite = True break if not composite: yield index plist.append(index) index += 1 def modinv(num, mod): # Multiplicative inverse with a modulus index = 1 while num * index % mod != 1: index += 1 return index def moddiv(num, dnm, mod): return num * modinv(dnm, mod) % mod def isPowerResidue(num, exp, mod): for base in range(mod): if pow(base, exp, mod) == num: return base return False def compute(power, prime): for num in range(2, prime): if isPowerResidue(moddiv(num - 1, num, prime), power, prime): return num - 1 return -1 # file = open('output.txt', 'w') def output(string): print(string) # file.write(str(string) + '\n') def compPrimes(power, count): maximum = 0 index = 0 for prime in getValidPrimes(power, count): result = compute(power, prime) if result > maximum: maximum = result index += 1 # output('Computed %d / %d = %d%% [result = %d, prime = %d]' % (index, count, (100 * index) // count, result, prime)) return maximum def isValidPrime(power, prime): return (prime - 1) % power == 0 def getValidPrimes(power, count): collected = [] for prime in primes(): if isValidPrime(power, prime): collected.append(prime) if len(collected) >= count: return collected # output('Collected %d / %d = %d%% [%d]' % (len(collected), count, (100 * len(collected)) // count, prime)) power = 3int(input()) + 2 output(compPrimes(power, 100)) # file.close() 97. Python 3 (PyPy), 1772 bytes, A000236
plist = [] def primes(maximal = -1): # Semi-efficient prime number generator with caching up to a certain maximal, or forever index = plist and plist[-1] or 2 for prime in plist: if prime <= maximal or maximal == -1: yield prime else: break while index <= maximal or maximal == -1: composite = False for prime in plist: if index % prime == 0: composite = True break if not composite: yield index plist.append(index) index += 1 def modinv(num, mod): # Multiplicative inverse with a modulus index = 1 while num * index % mod != 1: index += 1 return index def moddiv(num, dnm, mod): return num * modinv(dnm, mod) % mod def isPowerResidue(num, exp, mod): for base in range(mod): if pow(base, exp, mod) == num: return base return False def compute(power, prime): for num in range(2, prime): if isPowerResidue(moddiv(num - 1, num, prime), power, prime): return num - 1 return -1 # file = open('output.txt', 'w') def output(string): print(string) # file.write(str(string) + '\n') def compPrimes(power, count): maximum = 0 index = 0 for prime in getValidPrimes(power, count): result = compute(power, prime) if result > maximum: maximum = result index += 1 # output('Computed %d / %d = %d%% [result = %d, prime = %d]' % (index, count, (100 * index) // count, result, prime)) return maximum def isValidPrime(power, prime): return (prime - 1) % power == 0 def getValidPrimes(power, count): collected = [] for prime in primes(): if isValidPrime(power, prime): collected.append(prime) if len(collected) >= count: return collected # output('Collected %d / %d = %d%% [%d]' % (len(collected), count, (100 * len(collected)) // count, prime)) power = 3 output(compPrimes(power, 100)) # file.close() 97. [Python 3 (PyPy)], 1772 bytes, A000236
plist = [] def primes(maximal = -1): # Semi-efficient prime number generator with caching up to a certain max. index = plist and plist[-1] or 2 for prime in plist: if prime <= maximal or maximal == -1: yield prime else: break while index <= maximal or maximal == -1: composite = False for prime in plist: if index % prime == 0: composite = True break if not composite: yield index plist.append(index) index += 1 def modinv(num, mod): # Multiplicative inverse with a modulus index = 1 while num * index % mod != 1: index += 1 return index def moddiv(num, dnm, mod): return num * modinv(dnm, mod) % mod def isPowerResidue(num, exp, mod): for base in range(mod): if pow(base, exp, mod) == num: return base return False def compute(power, prime): for num in range(2, prime): if isPowerResidue(moddiv(num - 1, num, prime), power, prime): return num - 1 return -1 # file = open('output.txt', 'w') def output(string): print(string) # file.write(str(string) + '\n') def compPrimes(power, count): maximum = 0 index = 0 for prime in getValidPrimes(power, count): result = compute(power, prime) if result > maximum: maximum = result index += 1 # output('Computed %d / %d = %d%% [result = %d, prime = %d]' % (index, count, (100 * index) // count, result, prime)) return maximum def isValidPrime(power, prime): return (prime - 1) % power == 0 def getValidPrimes(power, count): collected = [] for prime in primes(): if isValidPrime(power, prime): collected.append(prime) if len(collected) >= count: return collected # output('Collected %d / %d = %d%% [%d]' % (len(collected), count, (100 * len(collected)) // count, prime)) power = int(input()) + 2 output(compPrimes(power, 100)) # file.close() Loading