Größtes Palindrom Produkt aus zwei dreistelligen Zahlen

[MarvinsDepression]

Danke. Das ist doch mal ein Wort. Ist mir schon klar, dass meine Künste nicht weit reichen...
Ein Glück, dass ich mein Geld mit anderem verdiene.😆

 

[KonradN]

Danke. Das ist doch mal ein Wort. Ist mir schon klar, dass meine Künste nicht weit reichen...
Ein Glück, dass ich mein Geld mit anderem verdiene.😆

Wobei jeder klein angefangen hat. Daher würde ich deine Künste nicht so runter machen. Wie heisst es so schön: Es ist noch kein Meister vom Himmel gefallen

 

[Arrive5784]

@MarvinsDepression

Schau dir am besten die Ausgabe in Posting #44 nochmal an:

Benchmark (arg) Mode Cnt Score Error Units PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 2 thrpt 1887737,694 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 3 thrpt 6442,840 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 4 thrpt 13794,175 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 5 thrpt 28,274 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 6 thrpt 90,531 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 7 thrpt 0,097 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findBottomUp 8 thrpt 0,711 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 2 thrpt 3128905,902 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 3 thrpt 37814,461 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 4 thrpt 30451,355 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 5 thrpt 2376,012 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 6 thrpt 244,949 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 7 thrpt 12,071 ops/s PalindromeProduct.BenchmarkPalindromeProduct.findTopDown 8 thrpt 1,924 ops/s

(ich weiß, die Bezeichner sind zu lang) Für arg=3 kann zum Beispiel @httpdigest s Variante 38.000mal pro Sekunde der Algorithmus durchlaufen werden, aber meine Variante hingegen nur 6.500mal pro Sekunde. Das heißt in dem Fall, seine Variante ist fast 6mal so schnell wie meine Variante.

@KonradN

Wie wärs, wenn du dir solche blöden Kommentare einfach sparst? Hier ging es darum, zwei konkrete Algorithmen zu vergleichen, um zu bestimmen, welches Verfahren wann schneller ist. Dazu brauche ich blöde Kommentare à la "Optimierung ist nichts für Anfänger" einfach nicht.

Wenn du dich selber damit meinst, dann ist es ok. Nicht jeder kann gute Algorithmen entwerfen, das stimmt. Also, einfach 5 Minuten vorher nachdenken, bevor wieder ein blöder Kommentar kommt.

 

[KonradN]

Wie wärs, wenn du dir solche blöden Kommentare einfach sparst?

Wie wäre es, wenn Du einfach einmal versuchst, selbst einfache Texte zu verstehen? Ich habe keinerlei dummen Kommentar gebracht sondern klare Informationen:
a) ich habe Links gebracht, damit sich jemand, der Interesse hat, einlesen kann. (Selbst für Dich könnte es interessant sein. Oder habe ich beim Überfliegen das "Warmup" übersehen?)
b) Ich habe eine klare Einordnung gebracht. Und Microbenchmarking ist nun einmal nichts für Anfänger, die gerade dabei sind, die Grundlagen zu verstehen.

Daher finden sich die blöden Kommentare mal wieder schlicht nur bei Dir!

 

[Hansen_07]

@Arrive5784

Wo wir schon bei blöden Kommentaren sind. Wie würdest denn das in #41 von dir Ausgedrückte bezeichnen?

Ich glaub, du hast zu viel Bier getrunken, wenn das bei dir funktionieren soll. =)

Abgesehen davon könnte man ja auch immer im Blick haben, was der TO eigentlich wissen wollte.. garantiert wollte er keine kleinkarierte Benchmark Diskussion.

 

[KonradN]

Wer zu viel säuft, übersieht oft was.

Das ist jetzt die Erklärung dafür, dass du öfters Dinge überliest? Du sprichst also aus Erfahrung bei dieser Aussage?

Naja, meine Vermutung in der Vergangenheit war ja ähnlich: da ging es ja darum, dass ggf nicht eingenommene Medikamente Auslöser für ‚Ticks‘ sein könnten. Aber klar, das kann auch an der Einnahme schädlicher Stoffe liegen.

Aber das ist ja eher kein Thema für den Thread und würde in die Plauderecke gehören.

 

[Hansen_07]

Ich weiß nicht, was daran falsch sein soll. Wer zu viel säuft, übersieht oft was.

Aber ich weiß nicht, warum du dich hier einmischst. 🤷‍♂️ Darfst du überhaupt schon Alkohol trinken?

Das sagt wohl mehr über dich aus, als über andere.

 

[Arrive5784]

Das sagt wohl mehr über dich aus, als über andere.

Jo, wir heulen alle eine Runde rum, weil es Alkoholismus gibt...

Wie alt bist du, 10? Bisher hast du nicht mal kleinste bisschen zum Thema beigetragen, stattdessen nur Müll verbreitet.

Ich behalte mir vor, jeden weiteren Beitrag von dir in diesem Thema wegen Offtopic zu melden. Irgendwann reicht's auch mal.

 

[berndoa]

Spannend wäre - aber das sprengt den Scope der Aufgabe - sich mal mathematisch zu überlegen, ob es da Regeln gibt, wann ein Produkt ein Palindrom ist. Ich mein, die Zahl muss ja ein Form wie diese n=abccba, Sprich es gilt:
n=a + 10*b + 100*c + 1000*c + 10000*b+100000*a = a*100001 + b*10010 + c*1100

Keine Ahnung ob man daraus was bzgl. Teiler & Co ableiten kann.

Um was zum mathematischen zu sagen:
schreiben wir es erstmal als Zehnerpotenzen hin:
n=a+10^1*b+10^2*c + 10^3*c+10^4*b+10^5*a
=a*(10^5+10^0)+b*(10^4+10^1)+c*(10^3+10^2)

wirkt auf den ersten Blick ohne Muster, aber wir müssen im Hinterkopf behalten dass
die Zahl 6 Ziffern hat und daher die Potenzen von min=0 bis max=5 gehen.

gewissermassen haben die je 2 zu einem buchstaben oben vorkommenden Potenzen den gleichen abstand von anfang und ende:
a*(10^(5-0)+10^(0+0))+b*(10^(5-1)+10^(0+1))+c*(10^(5-2)+10^(0+2))

5-0 heißt abstand 0 von der linken grenze, 0+0 heißt 0 abstand von der rechten grenze.
die 5 terme haben beide abstand 1 von den wänden.
die c terme abstand 2.

wäre die gesamtzahl ungerader länge (also bspw. n=5), dann müsste man beim kittelsten term aufpassen dass der nicht doppelt benutzt wird.

aber für jetzt gucken wir uns mal weiter den fall mit n=6, also gerader zahl an.
sei k=n/2=3, also die halbe länge.
reden wir desweiteren nicht mehr von a,b,c,d,e sondern von a0 bis a5, wobei die indizes von rechts nach links gezählt werden
da Polindrom, gilt zwangsläufig
a(5-i)=ai. heißt a5 und a0 sind gleich, a4 und a1 sind gleich, usw.

darauf basierend kommen wir analog zu oben auf den allgemeinen ausdruck
a0*(10^(5-0)+10^0)+a1*(10^(5-1)+10^(0+1))+a2*(10^(5-2)+10^(0+2))

bringt uns das irgendwas für die Aufgabe? Keine Ahnung

Ist nur eine nette Mathemtische Eigenschaft.

Mathematisch lässt sich das dann sogar schön mit einem Summenzeichen schreiben:
Gesamtzahl=Summe von i=0 bis (halbe Ziffernanzahl) von (a0*(10^(5-i)+10^i))


Bringt einem für die Zerlegung in 2 dreistelllige Zahlen nichts, aber wenigstens kann man so recht easy alle Palindrome finden wenn man alle dreistellige Zahlen (a,b,c) beginnend mit 999 abwärts der Reihe nach durchtestet.

Vielleicht wäres es auch sinnvoll, generell bei den Paaren an 3stelligen zahlen, die man so testet, die Grundregeln hinsichtlich gerade und ungerade zu beachten.

Will sagen, hat ein Palindrom bspw. 1,3,5,7,9 als erste und letzte Stelle, ist das palindrom eine Gerade Zahl.
Sollen also zwei 3stellige Zahlen dieses Palindrom ergeben, müssen beide ungerade sein weil sonst deren Produkt nix Ungerades ergeben kann.

 

[MarvinsDepression]

Will sagen, hat ein Palindrom bspw. 1,3,5,7,9 als erste und letzte Stelle, ist das palindrom eine Gerade Zahl.
Sollen also zwei 3stellige Zahlen dieses Palindrom ergeben, müssen beide ungerade sein weil sonst deren Produkt nix Ungerades ergeben kann.

Da bin ich dabei 👍
und hab mir gedacht, vielleicht findest du noch mehr. Und siehe da:
Bei Wikipedia ließt man: Aus den Teilbarkeitsregeln ergibt sich außerdem, dass alle Zahlenpalindrome mit gerader Stellenzahl durch 11 teilbar sind.
Damit läßt sich doch was anfangen...

Und bitte nicht wieder streiten, hatte die ganze Nacht kein Auge zu gemacht...
OK, ich hatte Nachtschicht 😁

public class TestOmania {
    
    private enum method {
        variante_A___safe, variante_A_unsafe, variante_B___safe, variante_B_unsafe;
    }
    
    private static long[] callMethod(PrimitiveIntegerSolver instance, method meth, int digits) {
        return switch(meth) {
            case variante_A___safe -> instance.variante_A___safe(digits);
            case variante_A_unsafe -> instance.variante_A_unsafe(digits);
            case variante_B___safe -> instance.variante_B___safe(digits);
            case variante_B_unsafe -> instance.variante_B_unsafe(digits);
        };
    }
    
    public static void main(String[] args) {
        var test = new PrimitiveIntegerSolver();
        
        for (int digits = 2; digits <= 9; digits++) {
            
            final int runs = (int)Math.pow(6, 9 - digits);
            System.out.println(runs +" runs with "+ digits +" digits:");
            
            for (var meth : method.values()) {
                var result = callMethod(test, meth, digits); // warmUp
                
                long time = System.currentTimeMillis();
                for (int i = 0; i < runs; i++) {
                    callMethod(test, meth, digits); // benchRun
                }
                time = System.currentTimeMillis() - time;
                test.printValues(meth.toString(), time, result);
            }
            System.out.println();
        }
    }
}

public class PrimitiveIntegerSolver {
    
    private static final int MAX_DIGITS = 9;

/*****************************************
**  Variante A: factors -> palindromes  **     
*****************************************/
    
    public long[] variante_A___safe(final int digits) {
        if (!checkParam(digits)) return new long[] {0, 0, 0};
        
        final int maxValue = (int)(Math.pow(10, digits) - 1);
        final int minValue = maxValue / 10 + 1;
        
        var result = new long[] {0, 0, 0};
        long product;
        
        for (int x = maxValue; x >= minValue; x--) {
            for(int y = x; y >= minValue; y--) {
                product = (long)x * y;
                
                if (product <= result[0]) break;
                
                if (variante_A_checkSymmetry(product, digits)) {
                    result = new long[] {product, x, y};
                    break;
                }
            }
        }
        return result;
    }
    
    /* DIESER ALGORITHMUS BERUHT TEILWEISE AUF UNSICHEREN ANNAHMEN !!!
       1) jd. ZahlenPalindrom mit gerader DezimalenAnzahl ist durch 11 teilbar (WikiPedia)
       2) Vorausgesetzt, das gesuchte ZahlenPalindrom beginnt/endet mit 9 -> beide Faktoren sind ebenfalls ungerade.
       ergo. gilt hier: x % 11 = 0 und x % 22 = 11
    */
    public long[] variante_A_unsafe(final int digits) {
        if (!checkParam(digits)) return new long[] {0, 0, 0};
        
        final int maxValue = (int)(Math.pow(10, digits) - 1);
        final int minValue = maxValue / 10 + 1;
        
        // start_x : größter ungerader Wert, kleiner/gleich 'maxValue', teilbar durch 11
        final int start_x = maxValue - (digits % 2 == 0 ? 0 : 20);
        
        var result = new long[] {0, 0, 0};
        long product;
        
        for (int x = start_x; x > minValue; x -= 22) {
            for(int y = maxValue; y > minValue; y -= 2) {
                product = (long)x * y;
                
                if (product <= result[0]) break;
                
                if (variante_A_checkSymmetry(product, digits)) {
                    result = new long[] {product, x, y};
                    break;
                }
            }
        }
        return result;
    }
    
/*    private boolean variante_A_checkSymmetry1(long value) {
        char[] number = Long.toString(value).toCharArray();
        
        for (int i = 0; i < number.length / 2; i++) {
            if (number[i] != number[number.length - 1 - i]) return false;
        }
        return true;
    }
    
    private boolean variante_A_checkSymmetry2(final long value) {
        long copy = value;
        long reversedValue = 0;
        
        while(copy > 0) {
            reversedValue *= 10;
            reversedValue += copy % 10;
            copy /= 10;
        }
        return value == reversedValue;
    }
*/
    private boolean variante_A_checkSymmetry(long value, final int digits) {
        int reversedValue = 0;
        for (int i = 0; i < digits; i++) {
            reversedValue *= 10;
            reversedValue += value % 10;
            value /= 10;
        }
        return value == reversedValue;
    }
    
/*****************************************
**  Variante B: palindromes -> factors  **
*****************************************/
    
    public long[] variante_B___safe(final int digits) {
        if (!checkParam(digits)) return new long[] {0, 0, 0};
        
        final int maxValue = (int)(Math.pow(10, digits) - 1);
        final int minValue = maxValue / 10 + 1;
        
        for (int i = maxValue - 2; i >= minValue; i--) {
            final long product = variante_B_buildPalindrome(i);
            
            for (int x = maxValue; x >= minValue; x--) { // x -= 2
                long y = product / x;
                
                if (y > x) break;
                
                if (y >= minValue && x * y == product)
                    return new long[] {product, x, y};
            }
        }
        return new long[] {0, 0, 0};
    }
    
    /* DIESER ALGORITHMUS BERUHT TEILWEISE AUF UNSICHEREN ANNAHMEN !!!
    ** 1) jd. ZahlenPalindrom mit gerader DezimalenAnzahl ist durch 11 teilbar (WikiPedia)
    ** 2) Vorausgesetzt, das gesuchte ZahlenPalindrom beginnt/endet mit 9 -> beide Faktoren sind ebenfalls ungerade.
    **   ergo. gilt hier: x % 11 = 0 und x % 22 = 11
    */
    public long[] variante_B_unsafe(final int digits) {
        if (!checkParam(digits)) return new long[] {0, 0, 0};
        
        final int maxValue = (int)(Math.pow(10, digits) - 1);
        final int minValue = (int)(Math.pow(10, digits - 1) * 9);
        
        // start_x : größter ungerader Wert, kleiner/gleich 'maxValue', teilbar durch 11
        final int start_x = maxValue - (digits % 2 == 0 ? 0 : 20);
        
        for (int i = maxValue - 2; i >= minValue; i--) {
            final long product = variante_B_buildPalindrome(i);
            
            for (int x = start_x; x > minValue; x -= 22) {
                int y = (int)(product / x);
                
                if (y > maxValue) break;
                
                if ((long)x * y == product) {
                    if (x < y) return new long[] {product, y, x};
                    return new long[] {product, x, y};
                }
            }
        }
        return new long[] {0, 0, 0};
    }
    
    private long variante_B_buildPalindrome(int leftPart) {
        long palindrome = (long)leftPart;
        
        while (leftPart > 0) {
            palindrome *= 10;
            palindrome += leftPart % 10;
            leftPart /= 10;
        }
        return palindrome;
    }
    
    private boolean checkParam(int digits) {
        return 2 <= digits && digits <= MAX_DIGITS;
    }
    
    public void printValues(String name, final long time, final long[] values) {
        if (values.length != 3) {
            System.out.println("ERROR ! corrupt data");
            return;
        }
        System.out.println("    "
                + name +" needs "
                + time +" ms : "
                + values[1] + " * "
                + values[2] + " = "
                + values[0]);
    }
}

279936 runs with 2 digits:
    variante_A___safe needs 122 ms : 99 * 91 = 9009
    variante_A_unsafe needs 24 ms : 99 * 91 = 9009
    variante_B___safe needs 99 ms : 99 * 91 = 9009
    variante_B_unsafe needs 48 ms : 99 * 91 = 9009

46656 runs with 3 digits:
    variante_A___safe needs 2921 ms : 993 * 913 = 906609
    variante_A_unsafe needs 265 ms : 913 * 993 = 906609
    variante_B___safe needs 1076 ms : 993 * 913 = 906609
    variante_B_unsafe needs 159 ms : 993 * 913 = 906609

7776 runs with 4 digits:
    variante_A___safe needs 391 ms : 9999 * 9901 = 99000099
    variante_A_unsafe needs 20 ms : 9999 * 9901 = 99000099
    variante_B___safe needs 202 ms : 9999 * 9901 = 99000099
    variante_B_unsafe needs 39 ms : 9999 * 9901 = 99000099

1296 runs with 5 digits:
    variante_A___safe needs 17011 ms : 99979 * 99681 = 9966006699
    variante_A_unsafe needs 34 ms : 99979 * 99681 = 9966006699
    variante_B___safe needs 365 ms : 99979 * 99681 = 9966006699
    variante_B_unsafe needs 43 ms : 99979 * 99681 = 9966006699

216 runs with 6 digits:
    variante_A___safe needs 1305 ms : 999999 * 999001 = 999000000999
    variante_A_unsafe needs 57 ms : 999999 * 999001 = 999000000999
    variante_B___safe needs 501 ms : 999999 * 999001 = 999000000999
    variante_B_unsafe needs 66 ms : 999999 * 999001 = 999000000999

36 runs with 7 digits:
    variante_A___safe needs 135063 ms : 9998017 * 9997647 = 99956644665999
    variante_A_unsafe needs 1824 ms : 9997647 * 9998017 = 99956644665999
    variante_B___safe needs 1589 ms : 9998017 * 9997647 = 99956644665999
    variante_B_unsafe needs 160 ms : 9998017 * 9997647 = 99956644665999

6 runs with 8 digits:
    variante_A___safe needs 4362 ms : 99999999 * 99990001 = 9999000000009999
    variante_A_unsafe needs 189 ms : 99999999 * 99990001 = 9999000000009999
    variante_B___safe needs 1406 ms : 99999999 * 99990001 = 9999000000009999
    variante_B_unsafe needs 139 ms : 99999999 * 99990001 = 9999000000009999

1 runs with 9 digits:
    variante_A___safe needs 381006 ms : 999980347 * 999920317 = 999900665566009999
    variante_A_unsafe needs 13922 ms : 999920317 * 999980347 = 999900665566009999
    variante_B___safe needs 22498 ms : 999980347 * 999920317 = 999900665566009999
    variante_B_unsafe needs 2251 ms : 999980347 * 999920317 = 999900665566009999

Klar, dass das kein echter Bechmark ist, aber ein bischen was kann man dann hoffentlich doch mit den Zahlen anfangen.
... wenn einen überhaupt noch interessiert. 😞

 

[berndoa]

Da bin ich dabei 👍
und hab mir gedacht, vielleicht findest du noch mehr. Und siehe da:
Bei Wikipedia ließt man: Aus den Teilbarkeitsregeln ergibt sich außerdem, dass alle Zahlenpalindrome mit gerader Stellenzahl durch 11 teilbar sind.
Damit läßt sich doch was anfangen...

bzgl. Teilbarkeit bzgl 11 Folgendes:
Ebenso auf Wikipedia steht:
Eine Zahl ist genau dann durch 11 teilbar, wenn ihre nichtalternierende 2er-Quersumme durch 11 teilbar ist.


diese komische Quersumme geht so:
gegebenen zahl abcdef, dann ist diese Quersumme ef+cd+ab
ef und co. sind hier als 2stellige zahlen zu verstehen.

Ab jetzt nenne ich die "nichtalternierende 2er-Quersumme" einfach nur P-Quersumme, weil nerviger Name.

Dann gilt in unserem Fall, ich betrachte wieder nur Sachen mit gerader Länge:
palindrom=a5 a4 a3 a2 a1 a0
dann ist die P-Quersumme gleich
(a5a4+a1a0)+a3a2

will sagen, die 2stellige zahl ganz links und die ganz rechts addiert, sowie die mittelste 2er zahl
wäre die zahl länger, gäbe es weitere 2erzahlen links und rechts, die man passend addiert.
halt von aussen nach innen gehen und immer links und rechts ein 2er paar nehmen.

Weil Palindrom, um bei obigem beispiel zu bleiben, gilt
(a5a4+a1a0)+a3a2
=(a0a1+a1a0)+a2a2

nun ergibt a0a1+a1a0=(a0*10+a1*1)+(a1*10+a0*1)
=..=(a1+a0)*(10+1)=(a1+a0)*11

gleichermassen ist a2a2=a2*11
also alles durch 11 teilbar

Für den Fall wo wir ein Palindrom ungerader Länge haben, wird der Beweis vermutlich hässlich und weiß ich auf Anhieb nicht.

Ansonsten basiert dieser Beweis auch wiederum auf der Wikipedia Aussage vom Anfang, die man glauben kann oder auch nicht


Edit: Und dass ausschließlich ungerade mal ungerade ungerade ergibt, lässt sich leicht direkt beweisen; also safe