Trouver le plus grand palindrome fait le produit de deux nombres de 3 chiffres

Nous supposons que le plus grand palindrome aura six chiffres plutôt que cinq, parce que 143*777 = 111111 est un palindrome.

Comme indiqué ailleurs, à 6 chiffres en base 10 palindrome abccba est un multiple de 11. C'est vrai, car une*100001 + b*010010 + c*001100 est égal à 11*un*9091 + 11*b*910 + 11*c*100. Donc, à l'intérieur de notre boucle, nous pouvons diminuer n par étapes de 11 si m n'est pas un multiple de 11.

Nous essayons de trouver le plus grand palindrome de moins d'un million, qui est un produit de deux nombres de 3 chiffres. Pour trouver une grande suite, nous essayons de grands diviseurs premiers:

• Nous l'étape m vers le bas à partir de 999, par 1;
• Exécuter n vers le bas à partir de 999 de 1 (si 11 divise m, soit 9% du temps) ou à partir de 990 par 11 (si 11 ne divise pas m, soit 91% du temps).

Nous garder une trace de la plus grande palindrome trouvé jusqu'à présent dans la variable q. Supposons que q = r·s avec r <= s. Habituellement, nous avons m < r <= s. Nous avons besoin de m·n > n >= q/m. En tant que plus grand palindromes sont trouvés, la gamme de n devient de plus en plus restreint, pour deux raisons: q devient plus grand, m devient plus petit.

La boucle interne d'attaché programme s'exécute uniquement 506 fois, vs le ~ 810000 fois le naïf programme utilisé.

#include <stdlib.h>
#include <stdio.h>
int main(void) {
  enum { A=100000, B=10000, C=1000, c=100, b=10, a=1, T=10 };
  int m, n, p, q=111111, r=143, s=777;
  int nDel, nLo, nHi, inner=0, n11=(999/11)*11;

  for (m=999; m>99; --m) {
    nHi = n11;  nDel = 11;
    if (m%11==0) {
      nHi = 999;  nDel = 1;
    }
    nLo = q/m-1;
    if (nLo < m) nLo = m-1;

    for (n=nHi; n>nLo; n -= nDel) {
      ++inner;
      //Check if p = product is a palindrome
      p = m * n;
      if (p%T==p/A && (p/B)%T==(p/b)%T && (p/C)%T==(p/c)%T) {
        q=p; r=m; s=n;
        printf ("%d at %d * %d\n", q, r, s);
        break;      //We're done with this value of m
      }
    }
  }
  printf ("Final result:  %d at %d * %d   inner=%d\n", q, r, s, inner);
  return 0;
}

Note, le programme est en C, mais même les techniques de travail en Java.

OriginalL'auteur James Waldby - jwpat7

Nous pouvons traduire la tâche dans la langue des mathématiques.

Pour un court laps de commencer, nous allons utiliser des caractères que les chiffres:

abc * xyz = n 
abc is  a 3-digit number, and we deconstruct it as 100*a+10*b+c
xyz is  a 3-digit number, and we deconstruct it as 100*x+10*y+z

Maintenant, nous avons deux expressions mathématiques, et peut définir les a,b,c,x,y,z € de {0..9}.

Il est plus précis pour définir une et x de l'élément de {1..9}, pas {0..9}, parce que 097 n'est pas vraiment un nombre à 3 chiffres, est-il?

Ok.

Si l'on veut produire un grand nombre, nous devrions essayer de parvenir à un 9......-Nombre, et depuis il est palindromique, il doit être du modèle 9....9. Si le dernier chiffre est un 9, puis à partir de

(100*a + 10*b + c) * (100*x + 10*y + z) 

ensuit que z*c a mener à un certain nombre, se terminant par le chiffre 9 - tous les autres calculs ne pas infecter le dernier chiffre.

Donc, c et z de (1,3,7,9) parce que (1*9=9, 9*1=9, 3*3=9, 7*7=49).

Maintenant un peu de code (Scala):

val n = (0 to 9)
val m = n.tail //1 to 9
val niners = Seq (1, 3, 7, 9)
val highs = for (a <- m;
b <- n;
c <- niners; 
x <- m;
y <- n;
z <- niners) yield ((100*a + 10*b + c) * (100*x + 10*y + z))

Alors je voudrais de les trier par taille, et en commençant par le plus grand, les tester pour être palindromique. Je voudrais donc omettre de tester un petit nombre pour être palindromique, parce que cela pourrait ne pas être si bon marché.

Pour des raisons esthétiques, je ne voudrais pas prendre un (toString.inverse == toString), mais un appel récursif à diviser et modulo solution, mais sur les machines d'aujourd'hui, il ne fait pas beaucoup de différence, n'est ce pas?

//Make a list of digits from a number: 
def digitize (z: Int, nums : List[Int] = Nil) : List[Int] =
if (z == 0) nums else digitize (z/10, z%10 :: nums)
/* for 342243, test 3...==...3 and then 4224. 
Fails early for 123329 */
def palindromic (nums : List[Int]) : Boolean = nums match {
case Nil           => true 
case x :: Nil      => true 
case x :: y :: Nil => x == y 
case x :: xs       => x == xs.last && palindromic (xs.init) }
def palindrom (z: Int) = palindromic (digitize (z))

Pour des performances sérieuses considérations, je voudrais la tester contre un toString/inverse/égale approche. Peut-être que c'est de pire en pire. Il n'début, mais la division et le modulo ne sont pas connus pour être le plus rapide des opérations, et je les utiliser pour faire une Liste à partir de l'Int. Il serait travailler pour BigInt ou de Long avec quelques redeclarations, et travaille à nice avec Java; pourrait être mise en œuvre en Java, mais un aspect différent.

D'accord, de mettre les choses ensemble:

highs.filter (_ > 900000) .sortWith (_ > _) find (palindrom) 
res45: Option[Int] = Some(906609)

Là où 835 tous les numéros de téléphone > 900000, et il retourne assez vite, mais je pense que même plus de force brute n'est pas beaucoup plus lent.

Peut-être qu'il est beaucoup plus habile façon de construire la plus haute palindrom, au lieu de chercher pour elle.

Un problème est: je ne l'ai pas su avant, qu'il existe une solution > 900000.

---

Une approche très différente, et pour produire de grandes palindromes, et de déconstruire leurs facteurs.

OriginalL'auteur user unknown

 package ex;
public class Main {
public static void main(String[] args) {
int i = 0, j = 0, k = 0, l = 0, m = 0, n = 0, flag = 0;
for (i = 999; i >= 100; i--) {
for (j = i; j >= 100; j--) {
k = i * j;
//System.out.println(k);
m = 0;
n = k;
while (n > 0) {
l = n % 10;
m = m * 10 + l;
n = n / 10;
}
if (m == k) {
System.out.println("pal " + k + " of " + i + " and" + j);
flag = 1;
break;
}
}
if (flag == 1) {
//System.out.println(k);
break;
}
}
}
}   

OriginalL'auteur Tobin Joy

Vous pouvez utiliser le fait que 11 est un multiple de le palindrome de réduire l'espace de recherche. On peut y arriver, car nous pouvons supposer que le palindrome de 6 chiffres et >= 111111.

par exemple ( à partir de projecteuler 😉 )

P= xyzzyx = 100000x + 10000y + 1000z + 100z + 10y +x
P=100001x+10010y+1100z
P=11(9091x+910y+100z)

Vérifier si je mod 11 != 0, alors la boucle j peut être soustraite par 11 (à partir de 990) depuis au moins un des deux doit être divisible par 11.

OriginalL'auteur scott

i did this my way , but m not sure if this is the most efficient way of doing this .
package problems;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class P_4 {
/**
* @param args
* @throws IOException 
*/
static int[] arry = new int[6];
static int[] arry2 = new int[6];
public static boolean chk()
{
for(int a=0;a<arry.length;a++)
if(arry[a]!=arry2[a])
return false;
return true;
}
public static void main(String[] args) throws IOException {
//TODO Auto-generated method stub
InputStreamReader ir = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(ir);
int temp,z,i;
for(int x=999;x>100;x--)
for(int y=999;y>100;y--)
{
i=0;
z=x*y;
while(z>0)
{
temp=z%10;
z=z/10;
arry[i]=temp;
i++;
}
for(int k = arry.length;k>0;k--)
arry2[arry.length- k]=arry[k-1];
if(chk())
{
System.out.print("pelindrome = ");
for(int l=0;l<arry2.length;l++)
System.out.print(arry2[l]);
System.out.println(x);
System.out.println(y);
}
}
}
}

OriginalL'auteur Ratan Kumar

Vous pouvez réellement le faire avec Python, c'est facile il suffit de prendre un coup d'oeil:

actualProduct = 0
highestPalindrome = 0
# Setting the numbers. In case it's two digit 10 and 99, in case is three digit 100 and 999, etc.
num1 = 100
num2 = 999
def isPalindrome(number):
number = str(number)
reversed = number[::-1]
if number==reversed:
return True
else:
return False
a = 0
b = 0
for i in range(num1,num2+1):
for j in range(num1,num2+1):
actualProduct = i * j
if (isPalindrome(actualProduct) and (highestPalindrome < actualProduct)):
highestPalindrome = actualProduct
a = i
b = j
print "Largest palindrome made from the product of two %d-digit numbers is [ %d ] made of %d * %d" % (len(str(num1)), highestPalindrome, a, b)

OriginalL'auteur Andres

J'ai essayé la solution par Tobin, de la joie et de vickyhacks et deux d'entre eux produire le résultat 580085 qui est le problème ici, c'est ma solution, bien que très maladroit:

import java.util.*;
class ProjEu4
{
public static void main(String [] args) throws Exception
{
int n=997;
ArrayList<Integer> al=new ArrayList<Integer>();
outerloop:
while(n>100){
int k=reverse(n);
int fin=n*1000+k;
al=findfactors(fin);
if(al.size()>=2)
{
for(int i=0;i<al.size();i++)
{
if(al.contains(fin/al.get(i))){
System.out.println(fin+" factors are:"+al.get(i)+","+fin/al.get(i));
break outerloop;}
}
}
n--;
}
}
private static ArrayList<Integer> findfactors(int fin)
{
ArrayList<Integer> al=new ArrayList<Integer>();
for(int i=100;i<=999;i++)
{
if(fin%i==0)
al.add(i);
}
return al;
}
private static int reverse(int number)
{
int reverse = 0;
while(number != 0){
reverse = (reverse*10)+(number%10);
number = number/10;
}
return reverse;
}
}

OriginalL'auteur user2419305

Ce sujet : en python

>>> for i in range((999*999),(100*100), -1):
...     if str(i) == str(i)[::-1]:
...         print i
...         break
...
997799
>>>

OriginalL'auteur James Sapam

public class ProjectEuler4 {
public static void main(String[] args) {
int x = 999; //largest 3-digit number
int largestProduct = 0;
for(int y=x; y>99; y--){
int product = x*y;
if(isPalindormic(x*y)){
if(product>largestProduct){
largestProduct = product;
System.out.println("3-digit numbers product palindormic number : " + x + " * " + y + " : " + product);
}
}
if(y==100 || product < largestProduct){y=x;x--;}
}
}
public static boolean isPalindormic(int n){
int palindormic = n;
int reverse = 0;
while(n>9){
reverse = (reverse*10) + n%10;
n=n/10;
}
reverse = (reverse*10) + n;     
return (reverse == palindormic);
}
}

OriginalL'auteur Tanzeel