5
$\begingroup$

Inspired by the question Is $\lim_{k \to \infty}\left[ \lim_{p \to \infty} \frac{M}{1+3+5+7+\cdots+ [2^{p(k-1)}-2^{p(k-2)}-2^{p(k-3)}-\cdots-1]}\right]=1$? which that, I asked before. I researched the pdf books before asking this question at MSE. When I could not find an answer anywhere, I decided to ask. Even if the question is absurd.

For this function: $$f(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod{2}\\ n+1 & \text{if } n\equiv 1 \pmod 2. \end{cases}$$

We know that for any positive number, there is such a number $\text{“} k \text{''}$, which that $f^k(n)=1$

For function $f(n)$ go "backward" from number $1$ for only odd numbers sequence:

Let step number is $k$ $$[2^{\sum_{z=1}^k m_z}-2^{\sum_{z=2}^k m_z}-2^{\sum_{z=3}^k m_z}-\cdots-1]\stackrel{k\to \infty}{\longleftarrow}\mathbf{\cdots} \stackrel{k=5}{\longleftarrow} \mathbf{[2^{m_4+m_3+m_2+m_1}-2^{m_4+m_3+m_2}-2^{m_4+m_3}-2^{m_4}-1]}\stackrel{k=4}{\longleftarrow} \mathbf{[{2^{m_1+m_3+m_2}-2^{m_2+m_3}-2^{m_3}-1}]}\stackrel{k=3}{\longleftarrow} \mathbf{[{2^{m_1+m_2}-2^{m_2}-1}]}\stackrel{k=2}{\longleftarrow} \mathbf{[{2^{m_1}-1}]}\stackrel{k=1}{\longleftarrow} \mathbf1$$

I used this formula:

$$φ({m_1,m_2,\ldots,m_k})=φ({m_1,m_2,\ldots,m_{k-1}})×2^{m_k}-1$$

and we can find general distrubition function: $φ({m_1,m_2,\ldots,m_k})$

$$φ({m_1,m_2,\ldots,m_{k}})=[2^{\sum_{z=1}^k m_z}-2^{\sum_{z=2}^k m_z} - 2^{\sum_{z=3}^k m_z}-\ldots-1]$$

$$f^k(φ(m_1,m_2,\ldots,m_k))=f^k([2^{\sum_{z=1}^k m_z}-2^{\sum_{z=2}^k m_z} - 2^{\sum_{z=3}^k m_z}-\cdots-1])=1$$

Example:

$$f^2(φ(m_1,m_2))=f^2({2^{m_1+m_2}-2^{m_2}-1})=\frac{\frac{{2^{m_1+m_2}-2^{m_2}-1} + 1}{2^{m_2}}+1}{2^{m_1}}=1$$

Then, look at this function:

$$g(n) = \begin{cases} n/2 &\text{if } n \equiv 0 \pmod 2 \\ 3n+1 & \text{if } n \equiv 1 \pmod 2. \end{cases}$$

For function $g(n)$ go "backward" from number $1$ for only odd numbers sequence, again:

$$ψ(m_1,m_2,\ldots,m_k)\stackrel{k\to \infty}{\longleftarrow}\mathbf{\cdots} \stackrel{k=2}{\longleftarrow} \mathbf{[\frac{4^{m_1}-1}{3}]}\stackrel{k=1}{\longleftarrow} \mathbf1$$

$$ψ(m_1)=\frac{4^{m_1}-1}{3}$$

Because, $g^1(ψ(m_1))=1$

The problem starts here. I found $ψ(m_1)$ for $k=1$. But, I dont know, how can I find $ψ(m_1,m_2)$ or $ψ(m_1,m_2,m_3)$.I can not continue here.

Anyway.My question's "meat" is this: Is it possible to make a general formula by going back from $1$?

How can we find and is it possible $ψ(m_1,m_2),ψ(m_1,m_2,m_3)...ψ(m_1,m_2,\ldots,m_k)$?

If we find, general dispersion $ψ(m_1,m_2),ψ(m_1,m_2,m_3),...,ψ(m_1,m_2,\ldots,m_k)$ can we answer that question: Why, is there such a number $k$ for function $f(n)$ always $f^k(n)=1$ and $g^k(n)=1$ or $g^k(n)≠1$(counterexample)?

The question is open to any editing, because I know, there are flaws in question and formulas.

$\endgroup$
5
  • $\begingroup$ The iterates of the Collatz function $g(2n) = n, g(2n-1) = 3(2n-1)+1$ cannot be put in a strictly decreasing form. Whereas the iterates of $f(2n) = n, f(2n-1) = 2n$ can be put in the form $F(2n)=n,F(2n-1) = n$. $ \qquad \qquad$ $ \qquad \qquad$ $ \qquad \qquad$ Formulas with $\ldots$ are hard to read. Your function $f(n)$ can be replaced by $F(2n-1) = 2n, F(2^k (2n-1)) = 2n-1$ whose iterations go to $1$. The backward sequence is of the form $a_1 = 1, a_{i+1} = 2^{k_i} a_i -1$ so that $a_i = F(a_{i+1})$. Then say $\varphi((k_i)_{i=1}^j )= a_j$. $\endgroup$
    – reuns
    Oct 1 '17 at 22:38
  • $\begingroup$ @reuns ohh, maybe I asked wrong. I look only odd numbers $\endgroup$
    – Zaharyas
    Oct 1 '17 at 22:51
  • $\begingroup$ What do you mean ? And the same idea of backward sequence works for any iterated function with $f^{-1}$ being two-valued (here $f^{-1}(2n+1) \in \{2 (2n+1),2n\}$) $\endgroup$
    – reuns
    Oct 1 '17 at 22:57
  • $\begingroup$ @ruins question was fixed. $\endgroup$
    – Zaharyas
    Oct 1 '17 at 23:07
  • 1
    $\begingroup$ Since $n_{k-1}$ is odd,you can write it mod 9(=1,2,4,5,7,8). Sorry can't comment yet $\endgroup$
    – user489810
    Oct 10 '17 at 12:58
3
+225
$\begingroup$

For $k=3$ it seems a bit more complicated. The third exponent must be something like $2o + (l-n)mod$ 3. I'll try to find out later.

I think this needs a more systematic way.

let's say $n_{(k-1)}=\frac{3n_k+1}{2^{m_k}}$, with $n_0=1$. If you want to climb up the tree, you can't pass through multiple of 3 (the $n_{(k-1)}$ cannot be multiple of 3, this is well known and obvious when you replace in the above formula). Here are the valid $m_k$ for different $n_{(k-1)}$ to avoid multiple of 3:

$n_{(k-1)}\equiv 1 \pmod {18}$ => $m_k$ must be of the form $6x+2$ or $6x+4$

$n_{(k-1)}\equiv 11 \pmod {18}$ => $m_k$ must be of the form $6x+1$ or $6x+3$

$n_{(k-1)}\equiv 13 \pmod {18}$ => $m_k$ must be of the form $6x+2$ or $6x+6$

$n_{(k-1)}\equiv 5 \pmod {18}$ => $m_k$ must be of the form $6x+3$ or $6x+5$

$n_{(k-1)}\equiv 7 \pmod {18}$ => $m_k$ must be of the form $6x+4$ or $6x+6$

$n_{(k-1)}\equiv 17 \pmod {18}$ => $m_k$ must be of the form $6x+1$ or $6x+5$

Perhaps if we use the general formula with the desired $k$ level: $\frac{2^{(m_k+m_{k-1}+...+m_3+m_2+m_1)}}{3^k} - \frac{2^{(m_k+m_{k-1}+...+m_3+m_2)}}{3^k} - \frac{2^{(m_k+m_{k-1}+...+m_3)}}{3^{k-1}} - \frac{2^{(m_k+m_{k-1}+...+m_4)}}{3^{k-2}} - .... - .... - \frac{2^{(m_k+m_{k-1})}}{3^3} - \frac{2^{(m_k)}}{3^2} - \frac{2^0}{3^1}$

and by replacing the $m_k$ by valid forms ($6x+y$ from the modulo list above), like i did in the previous answer, we must be able to construct the formulas.

Note: for the highest $m_k$ you don't need to avoid multiple of 3 (they are valid values), so you can use the $2l$ or $2l+1$ forms instead, like i did in the previous answer too.

I have not much time now, i'll take a look later, but i still think that having a unique formula or working with the $m_k$ alone is almost impossible.

EDIT: Ok, one of the formulas for $k=3$ is

$\frac{2^{m_3+m_2+m_1}}{3^3}-\frac{2^{m_3+m_2}}{3^3}-\frac{2^{m_3}}{3^2}-\frac{1}{3^1}$ with $m_1=18n+2$, $m_2=18l+2$ and $m_3=2o$ which gives

$\frac{16\cdot4^o\cdot262144^{n+l}-4\cdot4^o\cdot262144^l-3\cdot4^o-9}{27}$

I used $18x+2$ instead of $6x+2$ because the patern repeats every 3 times (e.g. the multiple of 3 is in first position for exponent $6\cdot3\cdot x+2$)

So i think you can split to avoid using modulos like i thought. Anyway, this gives a lot of possible formulas to cover $k=3$, and even more for $k=4$... which is not practicable...unless we can find some sort of systematic way to do it.

$\endgroup$
0
2
$\begingroup$

$φ({m_1,m_2,\ldots,m_{k}})=\frac{2^{(m_k+m_{k-1}+...+m_3+m_2+m_1)}}{3^k} - \frac{2^{(m_k+m_{k-1}+...+m_3+m_2)}}{3^k} - \frac{2^{(m_k+m_{k-1}+...+m_3)}}{3^{k-1}} - \frac{2^{(m_k+m_{k-1}+...+m_4)}}{3^{k-2}} - .... - .... - \frac{2^{(m_k+m_{k-1})}}{3^3} - \frac{2^{(m_k)}}{3^2} - \frac{2^0}{3^1}$

If you apply successively the condensed formula $g'(n)=\frac{3n+1}{2^{m_i}}$ to it, you'll reach 1.

k being the "distance" to 1, answering to "why is there such a number k" is answering the conjecture.

EDIT: I used your layout so you can understand better:

For function $g(n)$ go "backward" from number $1$ for only odd numbers sequence:

Note: This is how the Collatz tree is contructed

Let step number is $k$ $$[\frac{2^{\sum_{z=1}^k m_z}}{3^k}-\frac{2^{\sum_{z=2}^k m_z}}{3^k}-\frac{2^{\sum_{z=3}^k m_z}}{3^{k-1}}-\cdots-\frac{1}{3}]\stackrel{k\to \infty}{\longleftarrow}\mathbf{\cdots} \stackrel{k=5}{\longleftarrow} \mathbf{[\frac{2^{m_4+m_3+m_2+m_1}}{3^4}-\frac{2^{m_4+m_3+m_2}}{3^4}-\frac{2^{m_4+m_3}}{3^3}-\frac{2^{m_4}}{3^2}-\frac{1}{3}]}\stackrel{k=4}{\longleftarrow} \mathbf{[{\frac{2^{m_3+m_2+m_1}}{3^3}-\frac{2^{m_3+m_2}}{3^3}-\frac{2^{m_3}}{3^2}-\frac{1}{3^1}}]}\stackrel{k=3}{\longleftarrow} \mathbf{[{\frac{2^{m_2+m_1}}{3^2}-\frac{2^{m_2}}{3^2}-\frac{1}{3}}]}\stackrel{k=2}{\longleftarrow} \mathbf{[{\frac{2^{m_1}}{3^1}-\frac{1}{3^1}}]}\stackrel{k=1}{\longleftarrow} \mathbf1$$

I used this formula:

$$φ({m_1,m_2,\ldots,m_k})=φ({m_1,m_2,\ldots,m_{k-1}})×\frac{2^{m_k}-1}{3}$$ (which is the inverse of the Collatz function $\frac{3n+1}{2^{m_k}}$ since we run backward)

and we can find general distrubition function: $φ({m_1,m_2,\ldots,m_k})$

$$φ({m_1,m_2,\ldots,m_{k}})=[\frac{2^{\sum_{z=1}^k m_z}}{3^k}-\frac{2^{\sum_{z=2}^k m_z}}{3^k} -\frac{2^{\sum_{z=3}^k m_z}}{3^{k-1}}-\ldots-\frac{1}{3}]$$

$$g^k(φ(m_1,m_2,\ldots,m_k))=g^k([\frac{2^{\sum_{z=1}^k m_z}}{3^k}-\frac{2^{\sum_{z=2}^k m_z}}{3^k} -\frac{2^{\sum_{z=3}^k m_z}}{3^{k-1}}-\ldots-\frac{1}{3}])=1$$

Example:

$$g^2(φ(m_1,m_2))=g^2(\frac{2^{m_1+m_2}}{3^2}-\frac{2^{m_2}}{3^2}-\frac{1}{3})=\frac{3(\frac{3(\frac{2^{m_1+m_2}}{3^2}-\frac{2^{m_2}}{3^2}-\frac{1}{3})+1}{2^{m_2}})+1}{2^{m_1}}=1$$

Note that $ψ(m_1)=\frac{4^{m_1}-1}{3}$ is correct, but above, it was written as $\frac{2^{m_1}-1}{3}$ because other exponents $m_x$ are not always even.

Also note that my answer [k being the "distance" to 1, answering to "why is there such a number k" is answering the conjecture] refers to the previously unedited question: "Why,is there such a number $k$ for function $g(n)$ always $g^k(n)=1$" which is the conjecture itself and nobody can answer yet: when you run backward, you have to prove that you reach all naturals from 1.

EDIT2: The $m_k$ are totally dependent of the parent value $φ$, so there is no way to have a unique formula (with $m_k$ being any natural). For $k=2$ you could write these two formulas (they give all naturals that are 2 steps from 1): one with $m_1=6n+4$ and $m_2=2l+1$: $\frac{32\cdot64^n\cdot4^l-2\cdot4^l-3}{3^2}$ and one with $m_1=6n+2$ and $m_2=2l$(preferably with l>0, but i think it works with 0): $\frac{4\cdot64^n\cdot4^l-4^l-3}{3^2}$, but it does not help much (with $k=3$ you multiply the number of formulas...). You can have an infinite succession of $m_k=1$ (e.g. for $2^y-1$ there is $y-1$ successives $m_k=1$, so you can't predict $m_{k+1}$ with other $m_k$'s), or other combinations, but they are dependent of the successive values they produce (you can't just replace $m_4=1$ by $m_4=2$ or $3$, it would completly change the possible values of $m_{5+}$. If it was so simple, Collatz would be proved by now.

$\endgroup$
12
  • $\begingroup$ Ohh, sorry I did not do downvote, but I do not understand you. $\endgroup$
    – Zaharyas
    Oct 4 '17 at 21:04
  • $\begingroup$ İn your solution we dont know what is ${m_2,m_3...}$ $\endgroup$
    – Zaharyas
    Oct 5 '17 at 8:16
  • $\begingroup$ $m_1$ is always even: $0, 2, 4,...$. $m_2$ is dépendent of $m_1$, and any $m_k$ is dépendent of the previous $m_k$'s (more precisely of the previous φ) . In $φ({m_1,m_2,\ldots,m_k})=φ({m_1,m_2,\ldots,m_{k-1}})×\frac{2^{m_k}-1}{3}$, the rule is: if $φ({m_1,m_2,\ldots,m_{k-1}})$ is of the form $6x+1$, $m_k$ is even (including 0), if it is of the form $6x+5$, $m_k$ is odd. E.g. 11 = 6x1+5 -> $m_k$ can be $1, 3, 5, ...$. If you take $m_k=1$, you'll end up on 7. $\endgroup$
    – Collag3n
    Oct 5 '17 at 8:29
  • $\begingroup$ Please, write for $k=2$ direct formula. $\endgroup$
    – Zaharyas
    Oct 5 '17 at 8:35
  • $\begingroup$ what do you mean? this one: $\frac{2^{m_2+m_1}}{3^2}-\frac{2^{m_2}}{3^2}-\frac{1}{3}$? there is no shortcut: if $m_1=4$ ($φ=5$), then $m_2$ can be $1, 3, 5, 7,...$ to give the next φ ($3, 13, 53, ...$). if $m_1=8$ ($φ=85$), then $m_2$ can be $2, 4, 8,...$ to give the next φ ($113, 453, ...$). (sorry i said 0 included for even, but it is 0 excluded) $\endgroup$
    – Collag3n
    Oct 5 '17 at 8:45

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.