Zahlenfolge 1 versus 89

1. Aufgabe

Wir bilden eine Zahlenfolge auf folgende Weise: Ausgehend von einer beliebigen Startzahl bilden wir den Nachfolger dadurch, in dem alle Ziffern der aktuellen Zahl zuerst quadriert und anschließend zusammengezählt werden. Also zum Beispiel

44 → 32 → 13 → 10 → 1 → 1
      

oder

85 → 89 → 145 → 42 → 20 → 4 → 16 → 37 → 58 → 89
      

Wenn Sie die beiden Beispiele sorgfältig betrachten, werden Sie beobachten, dass jede Zahlenfolge bei Erreichen einer 1 oder 89 in eine Endlosschleife gerät. Weitaus interessanter ist jedoch die Aussage, dass jede Startzahl zu irgendeinem Zeitpunkt zu dem Folgenglied 1 oder 89 führt! Wie viele Zahlenfolgen mit einer Startzahl unter 10 Millionen erreichen den Wert 89?

Hinweis: Die gesuchte Aufgabenstellung ist auf einfache Weise parallelisierbar. Erkennen Sie den Ansatz?

2. Lösung

In Listing 1 stellen wir eine Klasse NumberSequence_1_89 vor, deren Methode SolveSequential das gestellte Problem in klassischer, sequentieller Manier löst:

01: class NumberSequence_1_89
02: {
03:     private const int Max = 10000000;
04:     private enum SequenceType { Sequence_1, Sequence_89 };
05: 
06:     private int oneSequences;
07:     private int eightyNineSequences;
08: 
09:     public NumberSequence_1_89()
10:     {
11:         this.oneSequences = 0;
12:         this.eightyNineSequences = 0;
13:     }
14: 
15:     private int SumOfSquares(int n)
16:     {
17:         int sum = 0;
18: 
19:         while (n != 0)
20:         {
21:             int digit = n % 10;
22:             n = n / 10;
23: 
24:             sum += digit * digit;
25:         }
26: 
27:         return sum;
28:     }
29: 
30:     private SequenceType ComputeSequence(int start)
31:     {
32:         for (;;)
33:         {
34:             start = SumOfSquares(start);
35: 
36:             if (start == 1)
37:                 return SequenceType.Sequence_1;
38:             else if (start == 89)
39:                 return SequenceType.Sequence_89;
40:         }
41:     }
42: 
43:     public void SolveSequential()
44:     {
45:         for (int i = 1; i < Max; i++)
46:         {
47:             SequenceType type = ComputeSequence(i);
48: 
49:             if (type == SequenceType.Sequence_1)
50:                 this.oneSequences++;
51:             else if (type == SequenceType.Sequence_89)
52:                 this.eightyNineSequences++; 
53:         }
54:     }
55: 
56:     // overrides
57:     public override string ToString()
58:     {
59:         String s = "";
60:         s += String.Format ("Sequences arriving at  1: {0}",
61:             this.oneSequences);
62:         s += Environment.NewLine;
63:         s += String.Format ("Sequences arriving at 89: {0}",
64:             this.eightyNineSequences);
65:         return s;
66:     }
67: }

Beispiel 1. Klasse NumberSequence_1_89.


Testrahmen:

private static void TestSequential()
{
    Stopwatch clock = new Stopwatch();
    clock.Start();
    NumberSequence_1_89 calculator = new NumberSequence_1_89();
    calculator.SolveSequential();
    Console.WriteLine(calculator);
    clock.Stop();
    Console.WriteLine("[{0} msecs.]", clock.ElapsedMilliseconds);
}

Ausgabe:

Sequences arriving at  1: 1418853
Sequences arriving at 89: 8581146
[5959 msecs.]

Da wir es mit einer Zahlenfolge zu tun haben, deren einzelne Folgenglieder sich völlig unabhängig voneinander berechnen lassen, bietet sich in idealerweise das Parallelisierungskonstrukt Parallel.For an. Das Aufsummieren der gefundenen Zahlenfolge bzgl. des Endwerts 1 bzw. 89 muss dann allerdings thread-sicher erfolgen: andernfalls werden Sie falsche Endresultate beobachten:

01: public void SolveParallel()
02: {
03:     Parallel.For(1, Max, (i) =>
04:     {
05:         SequenceType type = ComputeSequence(i);
06: 
07:         if (type == SequenceType.Sequence_1)
08:             Interlocked.Increment(ref this.oneSequences);
09:         else if (type == SequenceType.Sequence_89)
10:             Interlocked.Increment(ref this.eightyNineSequences);
11:     });
12: }

Beispiel 2. Paralleler Lösungsansatz mit Methode SolveParallel.


Testrahmen:

private static void TestParallel()
{
    Stopwatch clock = new Stopwatch();
    clock.Start();
    NumberSequence_1_89 calculator = new NumberSequence_1_89();
    calculator.SolveParallel();
    Console.WriteLine(calculator);
    clock.Stop();
    Console.WriteLine("[{0} msecs.]", clock.ElapsedMilliseconds);
}

Ausgabe:

Sequences arriving at  1: 1418853
Sequences arriving at 89: 8581146
[3825 msecs.]

Wenn Sie die Ausführungszeiten der beiden Testrahmen vergleichen, werden Sie einen beträchtlichen Laufzeitvorteil bei der parallelen Variante beobachten.