Project Euler 38

problem

Let's multiply 192 by 1, 2, 3.

   192 × 1 = 192
   192 × 2 = 384
   192 × 3 = 576

Concatenating the products yields the Pandigital number 192384576 from 1 to 9. 192384576 is called the concatenated product of 192 and (1,2,3).

In the same way, multiplying 9 by 1,2,3,4,5 and concatenating gives the Pandigital number 918273645. This is the concatenated product of 9 and (1,2,3,4,5). is there.

What is the largest 9-digit Pandigital number obtained as the concatenated product of an integer and (1,2, ..., n) (n> 1)? http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2038

Answer

First, I made a generator that generates a specified number of Pandigital numbers (character strings) from a specified set of numbers.

import copy
def pandigital(digit,seq1,seq2=[]):
  iter1 = map(str,seq1)
  if seq2:
    iter2 = map(str,seq2)
  else:
    iter2 = copy.deepcopy(iter1)
  for d in range(digit-1):
    iter1 = (x+y for x in iter1 for y in iter2 if not (y in x))
  return iter1

To generate a generator with a 10-digit Pandigital number that does not include 0 at the beginning, specify as follows. If seq2 is omitted, seq1 is copied to seq2.

 pandigital(digit=10,seq1=range(1,10),seq2=range(0,10))

I think that this generator returns values in ascending order if you pass range (1,10), and returns values in descending order if you pass range (10,1, -1).

In answering this question, we first create a set of 9-digit Pandigital numbers, PAND_SET, using the above function. Later, in order to refer to whether other numbers are included in this set of Pandigital numbers, set () is used here to make it a set type object in consideration of reference speed.

Then loop i from 2 to 10,000 and do the following calculation until s is (a string of) 9 digits. s = str (i) + str (i * 2) + str (i * 3) ・ ・ ・

Confirm that the s calculated in this way is larger than the answer candidate ans and that s is included in PAND_SET. If both are true, replace ans with s.

import pandigital
def main():
  SEARCH_MAX = 10**4
  PAND_SET = set(pandigital.pandigital(9,range(1,10)))
  ans = 0

  for i in range(2,SEARCH_MAX):
    s = str(i)
    j = 2
    while len(s)<9:
      s += str(i*j)
      j+=1
    if len(s)>=10:
      continue
    if int(s) > ans and s in PAND_SET:
      ans = int(s)
  print ans
main()

Recommended Posts

Project Euler 37
Project Euler 7
Project Euler 47
Project Euler 31
Project Euler 4
Project Euler 38
Project Euler 17
Project Euler 26
Project Euler 8
Project Euler 23
Project Euler 22
Project Euler 19
Project Euler 50
Project Euler 42
Project Euler 33
Project Euler 32
Project Euler 43
Project Euler 35
Project Euler 36
Project Euler 24
Project Euler 46
Project Euler 48
Project Euler 45
Project Euler 6
Project Euler 44
Project Euler 39
Project Euler 40
Project Euler 49
Project Euler 29
Project Euler 27
Project Euler 41
Project Euler 18
Project Euler 13
Project Euler 30
Project Euler 16
Project Euler 14
Project Euler 34
Project Euler 25
[Project Euler] problem1
Project Euler15 "Lattice Path"
Project Euler 2 Acceleration 2.21 Save microseconds.
Project Euler Original Method Group 1
What is Project Euler 3 Acceleration?
Functional programming in Python Project Euler 1
Project Euler 10 "Sum of Prime Numbers"
[Note] Project Euler in Python (Problem 1-22)
Functional programming in Python Project Euler 3
Project Euler # 5 "Minimum Multiples" in Python
Project Euler 4 Attempt to speed up
Functional programming in Python Project Euler 2
Project Euler 11 "Maximum product in grid"
Project Euler # 15 "Lattice Path" in Python
Project Euler # 4 "Maximum Palindrome" in Python
Project Euler 9 Retention of calculation results
Project Euler # 3 "Maximum Prime Factors" in Python
Project Euler # 11 "Maximum Product in Grid" in Python
Project Euler # 7 "1000 1st prime number" in Python
Project Euler # 16 "Sum of Powers" in Python
Project Euler # 9 "Special Pythagorean Triple" in Python
Project Euler # 14 "Longest Collatz Sequence" in Python
I wrote Project Euler 1 in one liner.