Multiplikative Beharlichkeit bestimmen


#1
Hallo,

im Rahmen des Studiums soll ein Programm geschrieben werden welches die kleinsten Zahlen berechnet welche jeweils eine multiplikative Beharlichkeit (Solange das Querprodukt vom Querprodukt bilden bis es einstellig ist) von 2-9 hat (soweit so gut). Der kniff ist dass dies in maximal 5 Sekunden passieren soll (auch soweit so gut).
Zusatzaufgabe ist, dass man es so optimieren/verändern soll dass auch die Zahlen für Beharlichkeit 10 und 11 berechnet werden (in maximal 10 Sekunden!).
Ich habe folgendes Programm, welches etwa 2 Sekunde benötigt um das Problem für 2-10 zu lösen:
(Funktionen habe ich bewusst vermieden, um die Geschwindigkeit zu erhöhen).

Ich will nicht unbedingt ein 1A-Top Programm vorgesetzt bekommen, aber hat vielleicht jemand einen Tipp oder einen Denkanstoß wie man das ganze performanter bekommt? (Das Problem für 11 rödelt nun schon wesentlich länger als 10 Sekunden und hat noch keine Lösung).

Java:
public class Quer
{
   public static void main(String[] args)
   {
           long startTime = System.currentTimeMillis(); // Startzeit bestimmen
       long lastResult = 0; // Ergebnis der letzen Berechnung (als Startwert fuer die neue Berechnung)
       
       int N = Integer.parseInt(args[0]); // Zahl von der Kommandozeile einlesen

        int VB = 1024 * 1024;   // Querprodukte cachen
        long[] S = new long[ VB ];

        for(int i = 0; i < VB; i++) // Beharlichkeiten vorberechnen
        {
            long z = i;
            long s = 0;
            while(z > 9) // Solange Ziffern uebrig sind
            {
                long q = 1; // Querprodukt bestimmen
                while(z > 0)
                {
                    q *= z % 10; // mit jeder Ziffer multiplizieren
                    z /= 10;
                }
                z = q;

                s++; // Schritte zaehlen
            }

            S[i] = s; // Schritte zur Zahl speichern
        }

       for(int n = 2; n <= N; n++) // Fuer jede Schrittanzahl bestimmen
       {
            int found = 0; // Wert gefunden?
           
           long z = lastResult; // Startwert festlegen
           while(found == 0)
           {
               long i = z;         // Wert kopieren

                long t = i % 10;         // Vortests
                long t2 = (i / 10) % 10; //

                if(n > 4 && !(t == 8 || t == 9) && !(t2 == 7 || t2 == 8 || t2 == 9)) // die letzen Stellen der Zahl sind 7, 8 oder 9
                {
                    long t3 = i % 100; // bei allen ueber 8 sind die letzen beiden Stellen 9
                    if(n > 8 && i != 99)
                    {
                        z += 99 - t3 - 1; // alle Werte ueberspringen die definitiv nicht auf 99 enden
                    }
                   
                    z++;

                    continue; // "false" Zahlen garnicht erst berechnen
                }
               
               long s = 0;         // Anzahl Schritte
                                   
               while(i / 10 > 0) // Solange die Quersumme mehr als eine Ziffer hat rechnen
                 {
                    if(i < VB) // gecached?
                    {
                        s += S[(int)i]; // Aus der Vorberechnung nehmen
                        i = 1;
                    }
                    else
                    {
                        long q = 1; // sonst Querprodukt berechnen (vgl. oben)
                        while(i > 0)
                        {
                            q *= i % 10;
                            i /= 10;
                        }
                        i = q;

                        s++;
                    }
               }
               
                 if(s == n) // wurde eine Zahl mit entsprechender Schrittanzahl gefunden, diese Ausgeben
               {
                   System.out.println(Long.toString(n) + " Schritte: " + Long.toString(z));
                   
                    if(n < 4) lastResult = (z * (n - 1)) - 1; // Startwert der naechsten Berechnung anpassen (wegen 25,39 und 77
                    else lastResult = (z * n); // sonst einfach z * n)
                   

                     found = 1; // Wert wurde gefunden!
               }
               
                   z++;   // naechste Zahl probieren
           }
        }

       long endTime = System.currentTimeMillis(); // Endzeit
       long time = endTime - startTime; // Zeitdifferenz in Millisekunden bestimmen
       
       System.out.println(Long.toString(time) + "ms");   
       
   }
}
Danke und Gruß
Lolwis111
 
#2
Hi

Eine Zahl mit Beharrlichkeit 11 finden? Wie nett, eine mit 12 zu finden ist bisher weltweit noch ungelöst :D

Funktionen vermeiden dürfte nicht so ausschlaggebend sein, und macht das Ganze nicht grade besser verständlich.

Division und Modulo sind sehr langsam, Arrays mit einer Ziffer pro Eintrag könnten für die Querproduktberechnung schneller sein (allerdings hilft dann der Cache nicht mehr so; kA. obs insgesamt schneller wird).

Als Lehrer würde ich folgende zwei Sachen als Falsch betrachten, solang nicht dabei steht, wie man darauf kommt:
Code:
if(n < 4) lastResult = (z * (n - 1)) - 1;
else lastResult = (z * n);
Wer sagt, dass es zwischen z und dem hier ausgerechneten Wert nichts gibt?
bei allen ueber 8 sind die letzen beiden Stellen 9
Wirklich?

Jedenfalls, einen Denkanstoß hab ich, wie man max 67000 Beharrlichkeiten ausrechnen muss, solange die zu testenden Zahlen nicht länger als 18 Stellen sind (im Gegensatz zu dem Millionen-Cache und Bruteforce danach wohl deutlich besser).
Ist aber etwas viel zu lesen:

Ich ignorier die ersten zwei Ergebnisse (10, 25) einmal komplett (ausrechnen davon sollte ja keine Probleme machen), alles was folgt gilt ab Beharrlichkeits-Grad 3 und aufwärts:

Die Ziffern der gesuchten Zahl müssen der Größe nach geordnet sein, um die Kleinstmögliche zu finden. Zb. Q(1223)=>12=>3, Q(2321)=>12=>3, also haben 1223 und 2321 den selben Grad, aber 1223<2321 (Q=Querprodukt)

Es gibt in der gesuchten Zahl keine 0, weil ein einzelnes Querprodukt sonst sofort 0 wäre und der Grad damit 1.

Es gibt in der gesuchten Zahl keine 1, weil das ganz erste Querprodukt auch ohne 1 aufs selbe Ergebnis kommt (damit der selbe Grad) und die Variante ohne 1 die kleinere Zahl ist. Zb. Q(2222)=>16, Q(121212121)=>16, also selber Grad, aber 2222 ist kleiner.

Wenn man zwei Ziffern a und b in der Zahl hat und a*b noch immer einstellig ist kann man die a und b rausnehmen und die a*b-Ziffer an die hintere der zwei Positionen einfügen (wenn die Ziffern schon geordnet sind sind die beiden Positionen sowieso hintereinander. Bzw. gehört die neue Ziffer verschoben). Zb. 2338 => 298 und wieder geordnet 289, 289<2338 aber selber Grad.
Geht für: 22,23,24,33
Als Folge davon gibt es nie mehr als ein 2, nie mehr als ein 3, nie 2 und 3 zusammen, nie 2 und 4 zusammen

Wenn 2/4/6/8 und 5 zusammen vorkommen ist die erste Q davon ein Vielfaches von 10, hat also 0, und die nächste Q ergibt 0. Grad damit max. 2. Für Grad 2 ist das beste Ergebnis ja schon bekannt, also nie 2 und 5 zusammen, nie 4 und 5 zusammen, nie 8 und 5 zusammen.

Zusammenfassung bis jetzt, wenn Grad >= 3:
Zffern müssen der Größe nach geordnet sein
0, 1, 2 mit 2/3/4/5, 3 mit 3, 4 mit 5, und 5 mit 8 kommt nicht vor

Wenn man zwei Ziffern a und b in der Zahl hat, und wenn a*b "nicht" einstellig ist, kann man sie zwar nicht so einer Ziffer zusammenfassen, aber trotzdem etwas "umschichten": zB. Ziffer 3 und 4 ersetzt mit 2 und 6 geht, weil beide in der ersten Q 12 ergeben, und 2...6 kleiner ist als 3...4. Zahlen mit 3 und 4 zusammen können also auch nicht das gesuchte Ergebnis sein.
(Hinweis: 12 nach der ersten Q wäre eigentlich ein Problem, weil entgegen der bisherigen Regeln 1 drin ist und man deswegen nicht mehr die kleinste Zahl hat. Aber 2 und 6 sind ja nicht unbedingt die einzigen Ziffern, mit den anderen dazu wirds größer als 12).
Ähnlich dazu können ignoriert werden:
3 mit 4 (eben ersetzbar mit 26), 3 mit 6 (29), 4 mit 4 (28), 4 mit 6 (38), 6 mit 6 (49)

Zusammenfassung bis jetzt:
Zffern müssen der Größe nach geordnet sein
Kein 0, kein 1
Kein 2 mit 2/3/4/5
Kein 3 mit 2/3/4/6
Kein 4 mit 2/3/4/5/6
Kein 5 mit 2/4/6/8
Kein 6 mit 3/4/5/6
Kein 8 mit 5

Oder anders:
Zffern müssen der Größe nach geordnet sein
Kein 0, kein 1
Kein 5 mit 2/4/6/8
Kein 2/3/4/6 zusammen mit 2/3/4/6 außer evt. 26

Die Zahl könnte nur aus 7,8,9 (beliebig oft) bestehen. Wenn nicht muss der Rest wegen der Größenordnung ganz vorne hin. Aufgrund der oberen Regeln, was womit zusammen sein darf, kann es nur eins von Folgenden sein: 2, 26, 4, 6, ein oder mehr 5, ein 3 und dann null oder mehr 5, (oder eben nichts davon, nur 789. Könnte man in "Null oder mehr 5" statt "ein oder mehr 5" integrieren)

Und mit den bisherigen Infos gibts gar nicht mehr so viel Möglichkeiten: Der 789-Teil hat nur zwei Variablen: Welche Stelle ist der Übergang von 7 zu 8, und welche (sicher rechts davon) von 8 zu 9. Im Fall von 5* oder 35* vorne gibts auch noch einen dritten Übergang für 5 zu 7. Und dann eines der folgenden fixen Präfixe dazu: Nichts, 2, 26, 3, 4, 6.
Wenn man annimmt (hofft?), dass das gesuchte Ergebnis für Grad 11 weniger als 18 Stellen hat (darüber bekommt man Javas long Probleme), gibt es sicher weniger als Sum[i=1...18](i^2*(4+i*2)) Möglichkeiten, das ist 66918.
Nur für den Cache rechnest du ja schon die Grade für eine Million Zahlen aus; 66918 erzeugen und prüfen sollte zeitlich kein Problem sein.

Lustig, jetzt die OEIS-Folge zu sehen und darin einen sicheren Fehler zu finden :D
 
Zuletzt bearbeitet:
#3
Hi,
also die Idee das am Ende Permutationen von 7,8,9 sind hatte ich ja auch schon, nur war ich dann irgendwie zu doof das umzusetzen...
Aber danke schon mal dafür! Das klingt auf jeden Fall sinnvoll, und 66918 ist schonmal eine Ansage gegenüber 2^64-1 haha
Ich werde mich mal sehen ob ich da was schnelles zusammenbekomme...