Voici un résumé de l'énoncé du problème 4 "Largest palindrome product" du Project Euler (traduction complète en français ici) :

Find the largest palindrome made from the product of two 3-digit numbers.

Compréhension du problème

Reformulons le problème : il s'agit de trouver le plus grand palindrome (nombre qui se lit de la même façon de gauche à droite que de droite à gauche) issu du produit de 2 nombres à 3 chiffres. Nous pouvons donc résoudre ce problème de 2 façons différentes :

• Soit faire le produit de tous les nombres à 3 chiffres et regarder quel est le plus grand palindrome formé
• Soit lister tous les palindromes inférieurs à $$999 \times 999=998001$$ dans l'ordre décroissant et regarder le premier de cette liste qui est égal au produit de 2 nombres à 3 chiffres

Le programme

Voici 2 solutions possibles, en Python, pour résoudre ce problème (1 pour chaque piste) :

• 1ère solution (1ère piste) :

  def is_palindrome(nb):
      if str(nb) == str(nb)[::-1]:
          return True
      return False
  resultat = 0
  for i in range(100, 1000):
      for j in range(i, 1000):
          produit = i*j
          #Test si le produit est un palindrome
          if is_palindrome(produit):
              if produit > resultat:
                  resultat = produit
  print(resultat)

• 2nd solution (2nd piste) plus rapide que la 1ère :

  def has_2factors_3digits(nb):
      for i in range(int(nb**0.5)+1, 99, -1):
          q, r = divmod(nb, i)
          if r == 0:
              if len(str(q)) == 3:
                  return True
              elif len(str(q)) > 3:
                  return False
      return False
  i = 997799
  j = 1
  while i > 10000:
      if has_2factors_3digits(i):
          print(i)
          break
      if j%10 == 8:
          i -= 110
      else:
          i -= 1100
      j += 1

La 1ère solution ne nécessitant pas d'explications particulières (explications de la fonction is_palindrome dans cet article), je ne vais m'attarder que sur la 2nd :

• Si nous listons les palindromes dans l'ordre décroissant, nous pouvons voir que pour passer de l'un à l'autre, il nous faut enlever 1100 pour les 8 premiers, puis 110 pour le 9ème, puis 1100 pour les 8 suivants, puis 110 pour celui d'après etc... jusqu'à 100000
• Pour chaque palindrome, on vérifie s'il est divisible par un nombre à 3 chiffres et si le résultat de cette division est un nombre à 3 chiffres lui aussi, on l'affiche et arrête le programme.

Le résultat

La réponse à ce problème est 906609.