Pirate Math Game - Solve it with C #

Question

I am trying to solve the following problem:

Some pirates have a chest full of treasures (gold coins)

Late in the evening, so they decided to break it in the morning

But one of the pirates wakes up in the middle of the night, worried that the other pirates will steal his share, so he decides to share the treasure himself.

He divides it into equal shares (one for each pirate). There is one remaining coin that he throws overboard. He takes his share, puts other stocks back in the chest, and returns to his cabin.

Another pirate wakes up and does the same. Yes, there is another additional coin. Yes, he throws this coin overboard.

... Each pirate does this once during the night (yes, there is an additional coin, and they throw it overboard every time), and the next morning they wake up and divide the treasures into equal shares. There is one left over which they throw overboard. Each of them share and live happily ever after.

Given the number of pirates, what is the smallest number of coins that could have been in a treasure chest initially?

I tried the following, but any number greater than 8 puts it on its knees:

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

I am sure that each number should be a prime number, so I also tried to do this with this in mind. However, I could not find an effective formula to solve this problem. My math is too weak.

EDIT

Thanks to the mentioned Fr3d video, now I have this for my CalculateTreasure method:

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

It is significantly improved, but still not 100% optimal.

Answer 1

I think I found the correct formula:

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

This is based on the sequence given 2 → 7, 3 → 79, 4 → 1021, 5 → 15621.