Riddler Express – 1/11/2019

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

2^{69} \cdot 3^{35} \cdot 5^{10} \cdot 7^{9} \cdot 11^{6} \cdot 13^{5} \cdot 17^{5} \cdot 19^{2} \cdot 23^{4} \cdot 29^{2} \cdot 31^{2} \cdot 37^{2} \cdot 41^{2} 4\cdot 3^{2} \cdot 47^{2} \cdot 53 \cdot 61 \cdot 67 \cdot 71 \cdot 73 \cdot 79 \cdot 83 \cdot 89 \cdot 97

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s