Pirate Game in Mathe - Lösen Sie es mit C#

Question

Ich versuche, das folgende Problem zu lösen:

Einige Piraten haben eine Truhe voller Schätze (Goldmünzen)

Es ist spät am Abend, so dass sie sich entscheiden, es zu spalten am Morgen

Aber einer der Piraten wacht in der Mitte der Nacht besorgt darüber, dass die anderen Piraten werden seinen Anteil stehlen und so beschließt er zu gehen teilt den Schatz selbst.

Er teilt es in gleiche Anteile (eine für jeden Piraten). Es ist eine Münze übrig, die er über Bord wirft. Er nimmt seinen Anteil, legt die anderen Anteile zurück in die Truhe, und kehrt in seine Kabine zurück.

Ein anderer Pirat wacht auf und macht dasselbe. Ja, es gibt noch eine zusätzliche Münze. Ja, er wirft diese Münze über Bord.

... Jeder Pirat tut dies einmal während der Nacht (ja, es ist ein zusätzliche Münze und sie werfen sie jedes Mal über Bord) und dem nächsten Morgen sie aufwachen und teilen sich den Schatz in gleichen Teilen. Dort ist eine übrig, über die sie über Bord werfen. Sie nehmen ihre Aktie und leben glücklich bis ans Ende.

Angesichts der Anzahl der Piraten, was ist die kleinste Anzahl von Münzen, die ursprünglich in der Schatzkiste hätte sein können?

Ich habe versucht, die folgenden, aber jede Zahl, die größer als 8 bringt sie in die Knie:

class Program 
    { 
     static long _input; 
     static long _timesDivided; 
     static string _output; 

     static void Main() 
     { 
      Console.WriteLine("Enter the number of Pirates: "); 

      var isValidInput = long.TryParse(Console.ReadLine(), out _input); 

      if (!isValidInput) 
      { 
       Console.WriteLine("Please enter a valid number"); 
       Console.ReadKey(); 
       return; 
      } 

      Console.WriteLine("Caculating minimum treasure...\r\n \r\n"); 

      _timesDivided = _input + 1; 

      var answer = CalculateTreasure(); 

      if (answer > 0) 
       _output = string.Format("The minimum treasure is {0}", answer); 
      else 
       _output = "There was an error, please try another number"; 

      Console.WriteLine(_output); 
      Console.ReadKey(); 
     } 

     private static long CalculateTreasure() 
     { 
      long result = 0; 

      try 
      { 
       while (true) 
       { 
        result++; 

        while (true) 
        { 
         if (result % _input == 1) 
         { 
          break; 
         } 
         else 
         { 
          result++; 
         } 
        } 

        long treasure = result; 

        for (long i = 0; i < _timesDivided; i++) 
        { 
         var remainder = treasure % _input; 

         if (remainder != 1) 
         { 
          break; 
         } 

         var share = (treasure - remainder)/_input; 

         if (i == (_timesDivided - 1)) 
         { 
          treasure = (treasure - (share * _input)); 

          if (treasure == 1) 
           return result; 
         } 
         else 
         { 
          treasure = (treasure - share) - 1; 
         } 
        } 
       } 
      } 
      catch (Exception ex) 
      { 
       //log exception here 
       return 0; 
      } 
     } 
    } 

Ich bin ziemlich sicher, dass jede Zahl eine Primzahl sein muss, so habe ich auch versucht, die oben in diesem Sinne. Ich bin jedoch nicht in der Lage, eine effiziente Formel zur Lösung dieses Problems zu finden. Meine Mathe ist einfach zu schwach

EDIT

Dank das Video Fr3d erwähnt, ich habe das jetzt für meine CalculateTreasure Methode:

private static long CalculateTreasure() 
     { 
      try 
      { 
       long result = (long)Math.Pow((double)_input, (double)_timesDivided); 

       while (true) 
       { 
        result--; 

        while (true) 
        { 
         if (result % _input == 1) 
         { 
          break; 
         } 
         else 
         { 
          result--; 
         } 
        } 

        long treasure = result; 

        for (long i = 0; i < _timesDivided; i++) 
        { 
         var remainder = treasure % _input; 

         if (remainder != 1) 
         { 
          break; 
         } 

         var share = (treasure - remainder)/_input; 

         if (i == (_timesDivided - 1)) 
         { 
          treasure = (treasure - (share * _input)); 

          if (treasure == 1) 
           return result; 
         } 
         else 
         { 
          treasure = (treasure - share) - 1; 
         } 
        } 
       } 
      } 
      catch (Exception ex) 
      { 
       //log exception here 
       return 0; 
      } 
     } 

es viel verbessert, aber immer noch nicht zu 100% optimal

Answer 1

ich glaube, ich die richtige Formel gefunden:

using System; 
using System.Numerics; 

namespace PirateCoins 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      int n = int.Parse(Console.ReadLine()); 
      Console.WriteLine(GetTreasure(n)); 
     } 
     static BigInteger GetTreasure(int n) 
     { 
      BigInteger result = BigInteger.Pow(n, n + 1) - (n - 1); 
      return result; 
     } 
    } 
} 

Diese basiert auf einer Sequenz, die gegeben wurde 2 -> 7, 3 -> 79, 4 -> 1021, 5 -> 15621.