Euler Solution 38

From ProgSoc Wiki

Jump to: navigation, search

Solutions for Problem 38

Define the concatenated product of an integer n and a set of integers s to be the concatenation of the results of multiplying n with each element of the set s. E.g. concatenated product of 192 and (1,2,3) is 192x1 ++ 192x2 ++ 192x3 = 192 ++ 384 ++ 576 = 192384576.

What is the largest 9 digit number that is a concatenated product with a set of more than 1 element?

Pen and Paper by SanguineV

Runtime: a few minutes

The steps:

  1. Note that as 918273645 is provided in the question the result must be greater than this.
  2. Thus the integer must begin with 9, this provides 9_18_{27_...}
  3. If the integer is 2 digits then the result cannot be 9 digits: (2 + 3 + 3 + 3 > 9).
  4. If the integer is 3 digits then the result cannot be 9 digits: (3 + 4 + 4 > 9).
  5. The second digit must be less than 5 otherwise the 1 carries and the result has 2 nines: 95?? = 9_190_
  6. Second digit cannot be 4 as this will lead to either another 8 or another 9: 94?? = 9_188_
  7. Assume 93 as first two digits, this yields: 93_186_
  8. Cannot have 5 as the third or fourth digit as it will yield a 0 or another 1.
  9. Cannot have 4 as the third or fourth digit as it will yield another 8 or 9.
  10. Third digit cannot be 7 as this will yield two 7s.
  11. Third digit cannot be 6 after some brief analysis, thus third digit must be 2.
  12. Solve for 4th digit.

Python by Althalus

Runtime: 0.0075

# We know it's not 9, they give us that one.
# And we can rule out any 2 digit 9_ numbers easily.
# Given that we know n=9 gives us 918273645, obviously x*1
# Must be bigger than 918.
# And a first run shows that the answer is bigger than 1000
for x in range(9999,9180,-1):
    string = 
    for n in range(1,9):
        string = string + str(x*n)
        if len(string) > 9: break # More than 9 is no good.
        if len(string) == 9: # Possible candidate
            good = True
            for i in range(1,10):
                if string.count(str(i)) != 1:  
                    good = False # Either we're missing the digit, 
                    break        # or it's there more than once
                if good == False: break
            if good == False: break
            print string
            print time()-start
Personal tools