Сумма чисел, делающих последовательность

Question

Во время просмотра регби вчера вечером мне было интересно, если бы какие-либо оценки были невозможны, вы можете только забить очки во многие 3, 5 или 7. Не долгое время отработало, что любой номер превышает 4. 5 = 5, 6 = 3 + 3, 7 = 7, 8 = 3 + 5, 9 = 3 + 3 + 3, 10 = 5 + 5 и так далее.

Расширение этой идеи на 5, 7 и 9 дает следующие возможные оценки:

5,7,9,10,12,14 // and now all numbers are possible.  

На 7, 9 и 11:

7,9,11,14,16,18,20,22,23,25,27 // all possible from here

Я сделал это в моей голове, может кто-нибудь предложить хороший алгоритм, который определил бы самый низкий возможный балл, выше, который все оценки достижимы, учитывая набор баллов.

Я смоделировал это так:

forall a < 10:
   forall b < 10:
      forall c < 10:
          list.add(3a + 5b + 7c);
list.sort_smallest_first();

Затем проверьте список для последовательности дольше 3 (возможна наименьшая оценка). Кажется довольно непрактичным и медленным для чего-либо за пределами тривиального случая.

Answer 1

Существует только одно недостижимое число, выше которое все оценки достижимы.

Это называется номер Фробениуса. Видеть: http://en.wikipedia.org/wiki/frobenius_number.

Страница Wiki должна иметь ссылки на алгоритмы для ее решения, например: http://www.combinatorics.org/volume_12/pdf/v12i1r27.pdf.

Для 2 чисел A, B точная формула (AB-AB) известна (что вы могли бы использовать для вырезания вашего поискового пространства), а для 3 чисел A, B, CA Sharp нижняя оценка (SQRT (3ABC) -ABC) и Довольно быстрые алгоритмы известны.

Если числа в арифметической прогрессии, то точная формула известна (см. Вики). Я упоминаю это, потому что в ваших примерах все номера в арифметической прогрессии.

Итак, чтобы ответить на ваш вопрос, найдите номер Фробениуса и добавьте 1 к нему.

Надеюсь, это поможет.