# How to use Fold on Select with a list of conditions to progressively eliminate from a list?

The application of Reduce (over the integers) to an equation produces, after the application of LogicalExpand, a list of 1296 And'ed logical conditions (in 9 generated parameters, 5 of which are asserted to be $$\in$$ Integers. Within each condition are individual terms like 6k == 3^P and other similarly unsatisfiable.

I have a list of such unsatisfiable patterns and would like to eliminate the conditions that contain them. This can be done pattern by pattern, but I think it should be possible by using Fold on Select with the list of patterns, so that each successive pattern to exclude is applied to the results of the previous selection.

(I have done this manually.. ultimately all conditions are eliminated; this means either the setup is defective or Reduce is not working as I expected because there are solutions for n in the negative integers. I am interested here in the use of Fold and Select but include the ancillary detail for other potential points of discussion.)

Question How can Fold be used with Select on a list of such conditions and a list of patterns to progressively eliminate conditions, by retaining only those that do not match?

Status Quo

Q[n_] := 2^Sum[q[j], {j, 1, n}]
collatz[P_, n_] := (n (3^P ) +  3^(P - 1) + Sum[Q[i] 3^(P - i - 1), {i, 1, (P - 2)}] +
Q[P - 1])/Q[P]


Applying Reduce to the equation collatz[P_, n_] == n produces the strange condition $$2^{-\sum _{j=1}^P q_j}\in \mathbb{Z}$$, and since I don't know why and it doesn't make sense to me, I recast the equation in a more general form where the Q[n] is no longer explicitly a power of two but a general indexed variable c[], thus

collatzLike[P_, n_] := (3^P n + 3^(-1 + P) + Sum[3^(-1 - i + P) c[i], {i, 1, P - 2}] + c[P - 1])/c[P];


This does not deliver, via Reduce, any such bizarre constraint on the denominator of collatzLike.

Reduce and expand via

List@@LogicalExpand@Reduce[collatzLike[P, n] == n && Mod[c[P], 2] == 0 && c[P] > 4 &&
Mod[n, 2] == 1, {n}, Integers, GeneratedParameters -> (Subscript[k, #] &) ]


delivers a list ("expandedReducedList") of 1296 elements, each like this

$$3^{P-1}\in \mathbb{Z}\land k_1\in \mathbb{Z}\land k_2\in \mathbb{Z}\land k_3\in \mathbb{Z}\land k_4\in \mathbb{Z}\land k_5\in \mathbb{Z}\land 6 k_1=3^P\land 6 k_2=3^{P+1}\land 6 k_3=c(P-1)\land 6 k_4=c(P)\land 6 k_5+1=n\land \sum _{i=1}^{P-2} c(i) 3^{-i+P-1}=\frac{2}{3} \left(-k_6-6 k_5 k_7-k_7-3 k_8+18 k_5 k_9+3 k_9\right)\land k_4\geq 1$$

With the rules (note, these are produced by another function that scans for common assertions)

integralReplacementRules = {Subscript[k, 1] \[Element] Integers -> True, Subscript[k, 2] \[Element] Integers -> True, Subscript[k, 3] \[Element] Integers -> True, Subscript[k, 4] \[Element] Integers -> True, Subscript[k, 5] \[Element] Integers -> True, 3^(-1 + P) \[Element] Integers -> True}


we use

eliminatedExpandedReducedList = Fold[ReplaceAll, expandedReducedList, integralReplacementRules]


to obtain our target set of simpler conditions, such as

$$6 k_1=3^P\land 6 k_2=3^{P+1}\land 6 k_3=c(P-1)\land 6 k_4=c(P)\land 6 k_5=n\land \sum _{i=1}^{P-2} c(i) 3^{-i+P-1}=\frac{2}{3} \left(-k_6-6 k_5 k_7-3 k_8+18 k_5 k_9\right)\land k_4\geq 1$$

Using Select, I then eliminate the conditions with unsatisfiable terms. One by one like this:

Select[eliminatedExpandedReducedList,FreeQ[#, 6 Subscript[k, 1] == 3^P, -1] &]


Eventually, I obtained this putative list of patterns to apply.

eliminations = {
HoldPattern@FreeQ[#, 6 Subscript[k, 1]==3^P, -1],
HoldPattern@FreeQ[#, Times[2 ,_]==Power[3,_], -1],
HoldPattern@FreeQ[#, Times[6 ,_]==c[_], -1],
HoldPattern@(FreeQ[#, 1+6 Subscript[k, _]==3^_, -1] &&  FreeQ[#, 1+6 Subscript[k, _]==3^_,-1]),
HoldPattern@(FreeQ[#, 1+2 (1+3 Subscript[k, _])==3^P, -1] &&  FreeQ[#, 6 Subscript[k, _]==3^(1+P), -1]),
HoldPattern@FreeQ[#, 1+6 Subscript[k, _]==c[-1+P], -1],
HoldPattern@FreeQ[#, 1+2 (1+3 Subscript[k, _])==c[-1+P], -1],
HoldPattern@FreeQ[#, 1+2 (2+3 Subscript[k, 3])==c[-1+P], -1],
HoldPattern@FreeQ[#, 2 (_+3 Subscript[k, _])==n, -1],
HoldPattern@FreeQ[#, 1+2 (2+3 Subscript[k, _])==c[-1+P], -1]
}


What I would like to do is... something like Fold[Select, eliminatedExpandedReducedList , eliminations ] but the correct form of this has stumped me.

How should I proceed? (with MMA 11.0.1.0) Specifically, how can Fold be used with select etc., and perhaps more generally, is there a better way to remove unsatisfiable items from the list.

Last, and definitely least, why do we terms like $$6 k_1=3^P$$ appear at all given that $$P$$ is a specified variable for Reduce over the Integers and $$k_1$$ is asserted to be $$\in$$ Integers (The question Reduce over integers - why does MMA not give ~impossible? is related, but apart from a comment that "The methods available to FindInstance are insufficient..." for similar equations the issue remains unexplained, it's just "Because" Is there some way that the capabilities of Reduce etc. could be enhanced to deal with such simply multiplicative comparisons?)

• Why do you insist on doing it with successive calls to Select? Wouldn't a single call with something like Select[list, FreeQ[Alternatives[...]]] also work, or am I missing something? Commented Oct 31, 2022 at 9:44
• @LukasLang Thanks! (I'm insisting only to the extent that I want to understand MMA better w.r.t Fold, etc. - I did say it was a generic question about them, albeit with specific reference; I do have the result, clumsily obtained though it might have been). Then: a) didn't think of it, and now (I just had a go) b) given some And'ed terms such as (FreeQ[#, 1+6 Subscript[k, _]==3^_, -1] && FreeQ[#, 1+6 Subscript[k, _]==3^_,-1]) I don't know how to construct that. Could you provide a working example? Commented Oct 31, 2022 at 9:58
• The elimination conditions should be functions.
– att
Commented Oct 31, 2022 at 19:57
• @att Example please. Commented Oct 31, 2022 at 22:45
• Your eliminations is a list of HoldPattern[FreeQ[#, ...]]s. Those should be functions FreeQ[#, ...]& instead.
– att
Commented Nov 1, 2022 at 0:12

The elimination conditions should be functions, thus:

eliminations = HoldPattern@{
FreeQ[#, 6 Subscript[k, 1] == 3^P, -1] &,
FreeQ[#, Times[2 , _] == Power[3, _], -1] &,
FreeQ[#, Times[6 , _] == c[_], -1] &,
(FreeQ[#, 1 + 6 Subscript[k, _] == 3^_, -1] && FreeQ[#, 1 + 6 Subscript[k, _] == 3^_, -1]) &,
(FreeQ[#, 1 + 2 (1 + 3 Subscript[k, _]) == 3^P, -1] && FreeQ[#, 6 Subscript[k, _] == 3^(1 + P), -1]) &,
FreeQ[#, 1 + 6 Subscript[k, _] == c[-1 + P], -1] &,
FreeQ[#, 1 + 2 (1 + 3 Subscript[k, _]) == c[-1 + P], -1] &,
FreeQ[#, 1 + 2 (2 + 3 Subscript[k, 3]) == c[-1 + P], -1] &,
FreeQ[#, 2 (_ + 3 Subscript[k, _]) == n, -1] &,
FreeQ[#, 1 + 2 (2 + 3 Subscript[k, _]) == c[-1 + P], -1] &
};


Then the desired form of Fold is

Fold[Select, eliminatedExpandedReducedList, ReleaseHold@eliminations]


Which, for the equations given in the OP and these particular conditions, leaves 4 (one more pair of unsatisfiable conditions to eliminate being then apparent).

Other incidental questions remain unanswered, but this was the man thrust of the OP.

Note that the use of subscripted variables is not recommended; they should be replaced by indexed variables and the patterns amended accordingly.