[Date Index] [Thread Index] [Author Index]

Re: How to check whether an infinite set is closed under addition?

• To: mathgroup at smc.vnet.net
• Subject: [mg124279] Re: How to check whether an infinite set is closed under addition?
• From: "Dr. Wolfgang Hintze" <weh at snafu.de>
• Date: Mon, 16 Jan 2012 17:02:22 -0500 (EST)
• Delivered-to: l-mathgroup@mail-archive0.wolfram.com
• References: <jeu7ma$j85$1@smc.vnet.net>

"Rex" <aoirex at gmail.com> schrieb im Newsbeitrag 
news:jeu7ma$j85$1 at smc.vnet.net...
> Given k positive numbers a_1<a_2<a_3<...<a_k, and all integers 
> greater
> than a_k, we want to check whether this set {a_1, a_2, a_3,...a_k, 
> a_k
> + 1, a_k+2, ......} is closed under addition.
>
> Is there any easy way to do this? any functions that we could use in
> Mathematica?
>
> Your help will be greatly appreciated.
>
>

You could proceed as follows:

(* create some sample data for the set *)
m = Union[Array[Random[Integer, {1, 5}] & , 5]]
Out[44]=
{1, 2, 3, 4, 5}

(* Form all subsets with mor than 1 element *)
ms = Subsets[m, {2, Length[m]}]
Out[45]=
{{1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 3}, {2, 4},
{2, 5}, {3, 4}, {3, 5}, {4, 5}, {1, 2, 3},
{1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5},
{1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5},
{3, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5},
{1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5},
{1, 2, 3, 4, 5}}

(* compute all sums *)
mp = (Plus @@ #1 & ) /@ ms
Out[46]=
{3, 4, 5, 6, 5, 6, 7, 7, 8, 9, 6, 7, 8, 8, 9, 10, 9,
10, 11, 12, 10, 11, 12, 13, 14, 15}

(* find maximum of m in order to discard elements > maximum of m *)
mx = Max[m]
Out[47]=
5

(* find all elements of m, the set of all sums, less than mx *)
mp1 = Select[mp, #1 < mx & ]
Out[48]=
{3, 4}

(* the intersection shows if the set m is closed under addition *)
Intersection[mp1, m]
Out[56]=
{3, 4}

(* as a result, thwe logical variable clsd indicates the closedness of 
the set *)
clsd = mp1 == Intersection[mp1, m]
Out[55]=
True

Regards,
Wolfgang