Pirate gioco in matematica - Risolvere con C#

Question

che sto cercando di risolvere il seguente problema:

Alcuni pirati hanno un baule pieno di tesori (monete d'oro)

è tardi la sera, così decidono di dividerlo la mattina

Ma, uno dei pirati si sveglia nel cuore della notte in questione che gli altri pirati rubare la sua parte così decide di andare a dividere il tesoro se stesso.

Lo divide in parti uguali (uno per ogni pirata). C'è una moneta rimasta, che getta in mare. Prende la sua parte, rimette le altre azioni nella cassa, e torna nella sua cabina.

Un altro pirata si sveglia e fa la stessa cosa. Sì, c'è ancora una moneta in più. Sì, lancia quella moneta in mare.

... Ogni pirata fa questo una volta durante la notte (sì, c'è una moneta in più e lo gettano a mare ogni volta), e la prossima mattina si svegliano e si dividono il tesoro in parti uguali. Lì lo è uno di quelli che gettano fuori bordo. Entrambi prendono la loro quota e vivono felici e contenti.

Dato il numero di pirati, qual è il più piccolo numero di monete che avrebbe potuto essere nello scrigno originale?

Ho provato quanto segue, ma qualsiasi numero maggiore di 8 porta in ginocchio:

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; 
      } 
     } 
    } 

Sono abbastanza certo che ogni numero deve essere un numero primo, così ho anche tentato di cui sopra con quello in mente. Tuttavia, non sono stato in grado di trovare una formula efficace per risolvere questo problema. I miei matematica è semplicemente troppo debole

EDIT

Grazie al video Fr3d detto, ora ho questo per il mio metodo CalculateTreasure:

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; 
      } 
     } 

Si è molto migliorata, ma ancora non ottimale al 100%

Answer 1

credo di aver trovato la formula giusta:

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; 
     } 
    } 
} 

Questo è basato su una sequenza che è stata data 2 -> 7, 3 -> 79, 4 -> 1021, 5 -> 15621.