Spaces:
Sleeping
Sleeping
File size: 4,437 Bytes
6a86ad5 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
"""
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
|