1
$\begingroup$

Update 3 @azerbajdzan 's info in comment on OddQ explains the failure to find solutions, misinterpretation of which lead to the "implausibly plausible" conclusion. However repeated with Mod in place of OddQ, Reduce not produces (after LogicalExpand) 2592 conditions... all of which are manifestly unsatisfiable. I shall not pollute this question further with details of that; a new question will be asked.

Update 1 -- the collatz formula has been corrected in the Sum[] part; the change did not alter the result of Reduce. See also Update 2 below for new doubts.

Original Thanks to @bob-hanlon's answer to How to specify and use indexed variables of undefined quantity?, with the elimination of subscripted variables in favour of indexed variables, I am not able to instantly dismiss the result, despite its implausibility. One reason for doubting the result though is that there is no explicit restriction of n to positive integers, and there are solutions in the negative integers, but maybe something is implicitly limiting the Reduce to +ve integers.

In the question Interpreting Reduce output (in the recreational context of the 3n + 1 problem) I asked for help in interpreting the long and complex results of Reduce; that task is now rather different.

Note: the Collatz, a.k.a. 3 n + 1 problem concerns the iteration of the rules, if n is odd, multiply by three and add one, if n is even divide by two.

Every positive n ever iterated has fallen into the {1, 4, 2} cycle. Whether this is true for all n is unknown. Answering that (Terence Tao recently proved that ~it is almost always true, which was amazing, other results include, n is very large if there are other cycles and any such cycle must be very long) can be split into two: a) are there any other cycles?, or b) might the iterated sequence drift off to infinity.

By applying MMA to a closed form we obtain a specific answer to question a), which is surprising, to say the least. (And Update 2 below addresses question b) )

The questions are now:

1/ Is the following result a) true and b) if so, how could MMA's workings be inspected to confirm this manually?

2/ In the rather more likely event that the result is not true, what is wrong with the setup or MMA's workings, or how might I investigate the latter?

3/ Can anyone adapt the setup so it does identify the solutions n = -1, -5, -17?

Set up.

Format[q[n_]] := Subscript[q, n]
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]

Reduce[collatz[P, n] == n && P >= 2 && OddQ[n], n, Integers, GeneratedParameters ->(Subscript[k, #] &) ]

(* False *)

(Understanding MMA's limitations and how to work with it better are implied goals of the questions above.)

PS Does collatz[P,n] even "Make sense?" (responding to @azerbajdzan)

These make perfect sense to me, and have the correct coefficients

collatz[2, n] == n // TeXForm
collatz[3, n] == n // TeXForm
collatz[4, n] == n // TeXForm

$2^{-q_1-q_2} \left(9 n+2^{q_1}+3\right) = n$

$2^{-q_1-q_2-q_3} \left(27 n+3\ 2^{q_1}+2^{q_1+q_2}+9\right) = n$

$2^{-q_1-q_2-q_3-q_4} \left(81 n+9\ 2^{q_1}+3\ 2^{q_1+q_2}+2^{q_1+q_2+q_3}+27\right)$

and this seems no less valid

collatz[7, -17] == -17 // TeXForm

$2^{-q_1-q_2-q_3-q_4-q_5-q_6-q_7} \left(243\ 2^{q_1}+81\ 2^{q_1+q_2}+27\ 2^{q_1+q_2+q_3}+9\ 2^{q_1+q_2+q_3+q_4}+3\ 2^{q_1+q_2+q_3+q_4+q_5}+2^{q_1+q_2+q_3+q_4+q_5+q_6}-36450\right)=-17$

in which case the question (ultimately) would be, what are the various $q_i$?

Update 2

A new reason for thinking there is something rotten in the state of Denmark is that Reduce[collatz[P, n] (<, >) n && OddQ[n], ...] are also False.

$\endgroup$
9
  • 2
    $\begingroup$ Your code has no sense. What is output of your function collatz[P_, n_] for concrete values of P and n? $\endgroup$ Oct 26, 2022 at 12:12
  • $\begingroup$ "the question (ultimately) would be, what are the various $q_i$?" What prevents you from computing them? - You know the Collatz algorithm and know the starting point -17. Where is the problem? $\endgroup$ Oct 26, 2022 at 15:48
  • $\begingroup$ @azerbajdzan Yes, of course. The question is about Reduce in the symbolic form; I only put that in because you said the code had no sense -- it shows how it makes sense and shows the remaining putative "unknowns". The problem is Reduce, symbolically and the fact that it doesn't find that case. $\endgroup$ Oct 26, 2022 at 15:54
  • $\begingroup$ OddQ gives False for non-numeric expressions. So it means OddQ[n] immediately evaluates to False and that is why Reduce outputs False without even looking at equation collatz[P, n] == n. Correct way of expressing oddity of n is Mod[n, 2] == 1. $\endgroup$ Oct 26, 2022 at 18:01
  • $\begingroup$ @azerbajdzan You are absolutely right about OddQ (and EvenQ...)! They only apply to expressions with Head Integer! It is annoying that the information is hidden in the docs under details, and I can see no reason for such a limitation when it could automatically used Mod or Divisible if the Head is not Integer. That makes an interesting difference - now Reduce gives longer output. Thank you. $\endgroup$ Oct 27, 2022 at 10:12

1 Answer 1

2
$\begingroup$

TL;DR The postulated result of Reduce is not to be believed because the core element of the collatz function has no effect in the presence of OddQ applied to a symbolic argument (for which, see the documentation). Use Mod[] instead. The OP was probably misled by Confirmation Bias re the positive integers (and even more confused by the absence of solutions in negative integers).

Full Form

The application of Reduce

Reduce[collatz[P, n] == n && P >= 2 && OddQ[n], n, Integers, GeneratedParameters ->(Subscript[k, #] &) ]

(* False *)

is independent of the equations collatz[P, n] == n && P >= 2 because, as pointed out by @azerbajdzan, the behaviour of OddQ and its ilk is unusual, especially in the context of symbolic manipulation - as here - where it will always return False.

In order to use oddness or similar in Reduce, one should use Mod[].

As to the operation of OddQ, further clarity is desirable. It says in the documentation for OddQ

gives True if expr is an odd integer, and False otherwise.

However, one should attend to the Detail (which is normally collapsed and so not immediately visible), where it says

OddQ[expr] returns False unless expr is manifestly an odd integer (i.e. has head Integer, and is odd).

The adverb manifestly is important: even though 3.0 == 3 is True, OddQ[3.0] is False, because 3.0 has Head Float.

Commentary

Whilst the functions OddQ, etc. are described accurately, this behaviour may not be expected and therefore its effects hard to spot, and in my opinion it runs counter to the general feature of the language that the application of a function to a type for which it is undefined returns the function expression unevaluated, which does not happen with OddQ.

Since this is noted in the documentation under Possible Issues (where application of FullSimplify is consequently recommended), there is probably some good reason for the way that OddQ etc. work but I have no information on that; any link to an explanation would be welcome

(* MMA returns an expression unevaluated if it is not defined for that type *)
f[x_Integer]:=4 x;
f["1"]
(* f["1"] *) 
(* But OddQ and the like return False instead *)
OddQ["1"]
(* False *)

@domen's link to the TestingExpressions documentation should also be noted; it says there

Functions that "ask a question" have names that end in Q. They return True for an explicit true answer, and False otherwise.

where we see "explicit" used apparently synonymously with "manifestly", neither of which are immediately meaningful IMO, serving only to confirm what one might already know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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