p346.py 2.44 KB
Newer Older
1 2
# 
# Solution to Project Euler problem 346
3
# Copyright (c) Project Nayuki. All rights reserved.
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


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.
33 34 35
def compute():
	LIMIT = 10**12
	
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)
40
	for length in range(3, LIMIT.bit_length() + 1):
41 42
		
		# For each base to evaluate the repunit in, until the value exceeds the limit
43
		for base in itertools.count(2):
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:
49
				break
50
			strongrepunits.add(value)
51
	
52
	# Sum all the numbers generated
53 54 55 56 57 58
	ans = sum(strongrepunits)
	return str(ans)


if __name__ == "__main__":
	print(compute())