Как проверить, закрыто ли бесконечное множество при сложении с компьютерным кодом?

Question

Дано k целых положительных чисел a ₁ 2 3 <... <a <sub>k, и все целые числа больше, чем _k , мы хотим проверить, является ли множество A = {a _i : i ∈ [1, k]} ∪ {n: n> a _k , n ∈ ℕ} = {a ₁ , a ₂ , a ₃ , ..., a _k , a _k + 1, a _k + 2, ...} закрыто при добавлении.Это означает, что:

∑ _{1 ≤ i ≤ k} a _i * b _i ∈ A, для любых неотрицательных целых чисел b _i .

Например, {2,4,6,7,8, ....} закрывается при добавлении.

Есть ли простой способ сделатьэтот?Какие-нибудь функции, которые мы могли бы использовать в Mathematica или Matlab?

Answer 1

Если прерывистая часть менее чем k наборов невелика, я полагаю, вы можете подойти к ней прямо так:

a = {2, 4, 6};
Tr /@ Subsets[a, {2}];
TakeWhile[%, # < Last@a &];
Complement[%, a] === {}

Answer 2

Банальное наблюдение: любая сумма, имеющая операнд >= a_k, является членом A, поэтому вам нужно иметь дело только с суммами, в которых оба операнда взяты из набора B = {a_1 .. a_(k-1)}.Наивное решение в псевдокоде:

for i from k-1 down to 1
  for j from i down to 1
    if (a_i + a_j < a_k) and (a_i + a_j is not in B) then
      return false
return true

Answer 3

Ваша недавняя модификация вопроса делает его смешным. Отмечу, что:

• a_1 - a_k - все строго положительные целые числа
• остальные члены набора строго больше, чем a_k, следовательно, также строго положительные целые числа

Следовательно, все члены набора являются строго положительными целыми числами .

Но ∑a_i*n_i ∈ A явно не выполняется для всех неотрицательных целых чисел n_i.

В частности, оно не выполняется для n_i = 0, поскольку сумма равна нулю, а ноль не является строго положительным целым числом, следовательно, не является членом множества.

Это очень странное определение «закрытого множества», а не общепринятое использование. Но по вашему определению, набор НЕ закрыт, для любого k > 0.