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?)
Select? Wouldn't a single call with something likeSelect[list, FreeQ[Alternatives[...]]]also work, or am I missing something? $\endgroup$(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? $\endgroup$eliminationsis a list ofHoldPattern[FreeQ[#, ...]]s. Those should be functionsFreeQ[#, ...]&instead. $\endgroup$