1
$\begingroup$

I'm relatively new to mathematica, and need to make a function which takes a set of whole numbers as input, then iterates through all whole numbers and sorts them into two sets, one for numbers which can be made by adding numbers in the original set, and the other for all other numbers. I already know how to decide whether or not it can be summed, and I know how far it has to go before stopping, I just dont know the syntax required to make the function sort them.

$\endgroup$
  • 2
    $\begingroup$ Have a look at If, Which, Switch, and Piecewise. $\endgroup$ – Henrik Schumacher Jul 11 at 19:41
  • $\begingroup$ What do you mean by "iterates through all whole numbers"? All whole numbers in the input set, or all whole numbers up to the sum of the input set? $\endgroup$ – Josh Bishop Jul 11 at 20:12
1
$\begingroup$

Update: The function f below partitions an input list into two sublists, the first list containing elements that can obtained by positive linear combinations of other elements and the second the complement of the first sublist:

ClearAll[f]
f[x_] := Pick[x, Unitize[Length[IntegerPartitions[#, All, x]] - 1 & /@ x], #] & /@ {1, 0}

f @ data

{{98, 87, 55, 79}, {8, 21, 24, 26, 59, 64}}

Original answer:

The function composite below Selects the "numbers which can be made by adding numbers in the original set".

ClearAll[composite]

composite = Function[x, Select[
   MemberQ[Union[Total /@ Subsets[Complement[x, {#}] ], {1, ∞}], #] &]];

Example:

SeedRandom[777]
data = RandomSample[Range[100], 10]

{24, 64, 26, 8, 98, 87, 55, 79, 59, 21}

{composite[data]@#, Complement[#, composite[data]@#]} &@data

{{98, 87, 55, 79}, {8, 21, 24, 26, 59, 64}}

$\endgroup$
0
$\begingroup$

Short answer

SeedRandom[777]
data = RandomSample[Range[100], 10]

GatherBy[data, Or @@ (FreeQ[#, x_ /; x > 1] && Count[#, 1] > 1 & /@ FrobeniusSolve[data, #]) &]

{{24, 64, 26, 8, 59, 21}, {98, 87, 55, 79}}

Long answer

If we take a look at FrobeniusSolve we get the description

The Frobenius equation is the Diophantine equation $a_1 x_1 + \ldots + a_n x_n = b$ where the $a_i$ are positive integers, $b$ is an integer, and a solution $x_1, \ldots, x_n$ must consist of non-negative integers. For negative $b$ there are no solutions.

Now consider FrobeniusSolve[{a1, a2, ...}, ak] yields a solution $\mathbf{x}$ that consists of only zeros and at least two ones (We do this check on each produced solution with the FreeQ[#, x_ /; x > 1] && Count[#, 1] > 1 & /@). The existence of this solution means that there is a subset $\{a_i\}$, and $i \neq k$ for all $i$ (this is where the "at least two ones" comes in), of the original list that total the number you want.

Then we have a list of Trues and Falses, but we only care if there exists at least one True. Then we use good ol' Or to test this existence since Or

evaluates its arguments in order, giving True immediately if any of them are True, and False if they are all False.

So then we can use this method to assign each number in the list a truth value on whether or not it can be represented as a sum of other numbers in the list, and gather all the Trues and Falses together to get what you want.

Timing comparison

Timing tests show this method is about ten times slower than kglr's method for small lists. If you're working with small lists, then definitely use theirs because it works great. But, after about 16 elements long though, this method actually takes considerably less time.

(*RepeatedTiming data for different list lengths*)
{
 {{3, 0.009}, {4, 0.02}, {5, 0.03}, {6, 0.04}, {7, 0.059}, {8, 0.3}, {9, 0.26}, {10, 0.3}, {11, 0.3}, {12, 0.6}, {13, 0.63}, {14, 1.1}, {15, 2.0}, {16, 1.53}, {17, 2.7}, {18, 1.58}, {19, 10.}, {20, 8.55}},
 {{3, 0.00011}, {4, 0.00018}, {5, 0.0004}, {6, 0.00094}, {7, 0.003}, {8, 0.0044}, {9, 0.01}, {10, 0.03}, {11, 0.067}, {12, 0.16}, {13, 0.31}, {14, 0.62}, {15, 1.3}, {16, 2.6}, {17, 5.7}, {18, 12.}, {19, 23.8}, {20, 52.0}}
}

Method timing comparison for increasing list length

Hopefully I didn't miss anything.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.