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

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

На вики-странице должны быть ссылки на алгоритмы для ее решения, например: http://www.combinatorics.org/Volume_12/PDF/v12i1r27.pdf

Для 2 чисел a,b известна точная формула (ab-ab) (которую можно использовать для сокращения пространства поиска), а для 3 чисел a,b,c a - резкая нижняя граница (sqrt(3abc)-abc) и довольно быстрые алгоритмы известны.

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

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

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