Пиратская игра в математике - решить с помощью C#

Question

Я пытаюсь решить следующую проблему:

У некоторых пиратов есть сундук с сокровищами (золотые монеты)

Это поздно вечером, поэтому они решили разделить его утром

Но один из пиратов просыпается среди ночи, обеспокоенный тем, что другие пираты украдут его долю, поэтому он решает сам разделить сокровище.

Он делит его на равные доли (по одному на каждого пирата). Осталась одна монета, которую он выбрасывает за борт. Он берет свою долю, кладет остальные акции обратно в сундук и возвращается в свою каюту.

Другой пират просыпается и делает то же самое. Да, есть еще одна дополнительная монета. Да, он выбрасывает эту монету за борт.

... Каждый пират делает это один раз в течение ночи (да, есть дополнительная монета, и они каждый раз выбрасывают ее за борт), а на следующее утро они просыпаются и делят сокровища на равные доли. Остался один, которого они выбрасывают за борт. Каждый из них берет свою долю и живет долго и счастливо.

Учитывая количество пиратов, какое наименьшее количество монет могло быть изначально в сундуке с сокровищами?

Я попробовал следующее, но любое число больше 8 ставит его на колени:

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

Я совершенно уверен, что каждое число должно быть простым числом, поэтому я также попытался сделать это с учетом этого. Однако я не смог найти эффективную формулу для решения этой проблемы. Моя математика просто слишком слаба

РЕДАКТИРОВАТЬ

Благодаря видео, упомянутому Fr3d, теперь у меня есть это для моего метода 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;
            }
        }

Это намного улучшено, но все еще не на 100% оптимально

Answer 1

Я думаю, что нашел правильную формулу:

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

Это основано на последовательности, которая была задана 2 -> 7, 3 -> 79, 4 -> 1021, 5 -> 15621 .