p346.py 2.44 KB
 Nayuki committed Dec 25, 2016 1 2 ``````# # Solution to Project Euler problem 346 `````` Nayuki committed Dec 27, 2016 3 ``````# Copyright (c) Project Nayuki. All rights reserved. `````` Nayuki committed Dec 25, 2016 4 5 6 7 8 9 10 11 ``````# # https://www.nayuki.io/page/project-euler-solutions # https://github.com/nayuki/Project-Euler-solutions # import itertools `````` Nayuki committed Dec 25, 2016 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 ``````# 1 is a strong repunit because in every base b >= 2, its representation is "1", which is a repunit. # 2 is not a strong repunit because in base 2 it is "10", but in every base b >= 3 it is "2". # # As for other numbers, first assume that n is an arbitrary integer at least 3. # It is trivially a repunit in base b = n - 1 (which is at least 2), where its representation is "11". # For this n to be a strong repunit, it needs to be a repunit in at least one other base. # Obviously it can't be "11" in another base. So it must be {"111", # "1111", "11111", or some longer string} in some base smaller than b. # # Phrased differently, if an integer n >= 3 has the representation {"111", "1111", or some longer string} # in some base b >= 2, then it is automatically a strong repunit because firstly, its value is # at least 7 ("111" in base 2), and secondly it is equal to "11" in some base b' >= 2. # # Hence all we need to do is for each repunit length 3, 4, 5, etc., we generate the string (e.g. "111"), # then evaluate its value at base 2, 3, etc. as long as the value stays within the limit, # and add these values to the set of known strong repunits (to catch possible duplicates). # # Note that the longest repunit length we need to test is at most the bit length of the limit. # For example, because the limit is 10^12 = 1110100011010100101001010001000000000000 (base 2), # any repunit longer than "1111111111111111111111111111111111111111" is guaranteed # to exceed the limit in every base. `````` Nayuki committed Dec 25, 2016 33 34 35 ``````def compute(): LIMIT = 10**12 `````` Nayuki committed Dec 25, 2016 36 37 38 39 `````` # Collect all generated numbers to eliminate duplicates strongrepunits = {1} # Special case # For each possible length of strong repunits (ignoring the trivial length of 2) `````` Nayuki committed Dec 25, 2016 40 `````` for length in range(3, LIMIT.bit_length() + 1): `````` Nayuki committed Dec 25, 2016 41 42 `````` # For each base to evaluate the repunit in, until the value exceeds the limit `````` Nayuki committed Dec 25, 2016 43 `````` for base in itertools.count(2): `````` Nayuki committed Dec 25, 2016 44 45 46 47 48 `````` # Evaluate value = base^(length-1) + base^(length-2) + ... + base^1 + base^0 # Due to the geometric series, value = (base^length - 1) / (base - 1) value = (base**length - 1) // (base - 1) if value >= LIMIT: `````` Nayuki committed Dec 25, 2016 49 `````` break `````` Nayuki committed Dec 25, 2016 50 `````` strongrepunits.add(value) `````` Nayuki committed Dec 25, 2016 51 `````` `````` Nayuki committed Dec 25, 2016 52 `````` # Sum all the numbers generated `````` Nayuki committed Dec 25, 2016 53 54 55 56 57 58 `````` ans = sum(strongrepunits) return str(ans) if __name__ == "__main__": print(compute())``````