This week’s Riddler Express is about finding small factors of large numbers. The goal is to find the missing digit of the number below with factors all less than 100.

530,131,801,762,787,739,802,889,792,754,109,70_,139,358,547,710,066,257,652,050,346, …294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000

It turns out that Python is well equipped to handle a problem like this. The solution follows.

The missing digit is 6.

To solve the problem, I used the following Python program.

# The text from the website, with the commas removed. # Note: Python will use big integers when the normal integer size is exceeded. Nice! unknown = '530,131,801,762,787,739,802,889,792,754,109,70_,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000'.replace(',','') # Loop through the possible digits for i in range(10): prefactor = int(unknown.replace('_',str(i))) # Replace the missing digit keep_trying = True # Tells if we should keep going through the trial divisions # Keep going through trial divisions while the number is greater than 99 while prefactor > 99 and keep_trying: # Try to find the largest factor (not necessarily prime) less than 100. for j in range(99, 0, -1): # If we make it down to 1, then the factors must be larger than 99. if j == 1: print("Digit {0} must give prime factors greater than 100.".format(i)) keep_trying = False # At this point, we can give up. else: remainder = prefactor % j # find the remainder when divided by the potential factor # If the remainder is 0, then we have found a factor! if remainder == 0: prefactor //= j # Divide out by the factor we just found. # Note: Do not use '/' for division. That returns a float. break # Break out of the for j loop to start over again. # end if # end if-else # end for j # end while # end for i (Curly braces have a purpose. Why did we have to get rid of them in Python?)

For fun, I factored the number with 6 in the place of the missing digit. I got

To do the factoring, I wrote a second Python program to perform trial division.

# Texted copied from the website, with commas removed unknown = '530,131,801,762,787,739,802,889,792,754,109,70_,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000'.replace(',','') # A list of primes primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] # A dictionary object to contain the exponents for each prime in the factored form of the number. exponents = dict() # Put 6 in for the missing digit prefactor = int(unknown.replace('_','6')) # Trial divisions by all primes less than 100. while prefactor > 1: for j in primes: remainder = prefactor % j if remainder == 0: print("{0} is a prime factor.".format(j)) if j in exponents: exponents[j] += 1 else: exponents[j] = 1 # end if-else prefactor //= j break #end if # end for j # end while # Print out the prime factorization in exponential form. latex_string = "" for i in primes: if i in exponents: latex_string += "{0}^{1} ".format(i, exponents[i]) print(latex_string)

You can download the source files at my OneDrive.