123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160 |
- """
- The Schur number S(k) is the largest integer n for which the interval [1,n]
- can be partitioned into k sum-free sets.(https://mathworld.wolfram.com/SchurNumber.html)
- """
- import math
- from sympy.core import S
- from sympy.core.basic import Basic
- from sympy.core.function import Function
- from sympy.core.numbers import Integer
- class SchurNumber(Function):
- r"""
- This function creates a SchurNumber object
- which is evaluated for `k \le 5` otherwise only
- the lower bound information can be retrieved.
- Examples
- ========
- >>> from sympy.combinatorics.schur_number import SchurNumber
- Since S(3) = 13, hence the output is a number
- >>> SchurNumber(3)
- 13
- We do not know the Schur number for values greater than 5, hence
- only the object is returned
- >>> SchurNumber(6)
- SchurNumber(6)
- Now, the lower bound information can be retrieved using lower_bound()
- method
- >>> SchurNumber(6).lower_bound()
- 536
- """
- @classmethod
- def eval(cls, k):
- if k.is_Number:
- if k is S.Infinity:
- return S.Infinity
- if k.is_zero:
- return S.Zero
- if not k.is_integer or k.is_negative:
- raise ValueError("k should be a positive integer")
- first_known_schur_numbers = {1: 1, 2: 4, 3: 13, 4: 44, 5: 160}
- if k <= 5:
- return Integer(first_known_schur_numbers[k])
- def lower_bound(self):
- f_ = self.args[0]
- # Improved lower bounds known for S(6) and S(7)
- if f_ == 6:
- return Integer(536)
- if f_ == 7:
- return Integer(1680)
- # For other cases, use general expression
- if f_.is_Integer:
- return 3*self.func(f_ - 1).lower_bound() - 1
- return (3**f_ - 1)/2
- def _schur_subsets_number(n):
- if n is S.Infinity:
- raise ValueError("Input must be finite")
- if n <= 0:
- raise ValueError("n must be a non-zero positive integer.")
- elif n <= 3:
- min_k = 1
- else:
- min_k = math.ceil(math.log(2*n + 1, 3))
- return Integer(min_k)
- def schur_partition(n):
- """
- This function returns the partition in the minimum number of sum-free subsets
- according to the lower bound given by the Schur Number.
- Parameters
- ==========
- n: a number
- n is the upper limit of the range [1, n] for which we need to find and
- return the minimum number of free subsets according to the lower bound
- of schur number
- Returns
- =======
- List of lists
- List of the minimum number of sum-free subsets
- Notes
- =====
- It is possible for some n to make the partition into less
- subsets since the only known Schur numbers are:
- S(1) = 1, S(2) = 4, S(3) = 13, S(4) = 44.
- e.g for n = 44 the lower bound from the function above is 5 subsets but it has been proven
- that can be done with 4 subsets.
- Examples
- ========
- For n = 1, 2, 3 the answer is the set itself
- >>> from sympy.combinatorics.schur_number import schur_partition
- >>> schur_partition(2)
- [[1, 2]]
- For n > 3, the answer is the minimum number of sum-free subsets:
- >>> schur_partition(5)
- [[3, 2], [5], [1, 4]]
- >>> schur_partition(8)
- [[3, 2], [6, 5, 8], [1, 4, 7]]
- """
- if isinstance(n, Basic) and not n.is_Number:
- raise ValueError("Input value must be a number")
- number_of_subsets = _schur_subsets_number(n)
- if n == 1:
- sum_free_subsets = [[1]]
- elif n == 2:
- sum_free_subsets = [[1, 2]]
- elif n == 3:
- sum_free_subsets = [[1, 2, 3]]
- else:
- sum_free_subsets = [[1, 4], [2, 3]]
- while len(sum_free_subsets) < number_of_subsets:
- sum_free_subsets = _generate_next_list(sum_free_subsets, n)
- missed_elements = [3*k + 1 for k in range(len(sum_free_subsets), (n-1)//3 + 1)]
- sum_free_subsets[-1] += missed_elements
- return sum_free_subsets
- def _generate_next_list(current_list, n):
- new_list = []
- for item in current_list:
- temp_1 = [number*3 for number in item if number*3 <= n]
- temp_2 = [number*3 - 1 for number in item if number*3 - 1 <= n]
- new_item = temp_1 + temp_2
- new_list.append(new_item)
- last_list = [3*k + 1 for k in range(len(current_list)+1) if 3*k + 1 <= n]
- new_list.append(last_list)
- current_list = new_list
- return current_list
|