10
$\begingroup$

Question: I am wondering if an expression exists for the highest power of 2 that divides $3^a\left(2b-1\right)-1$, in terms of $a$ and $b$, or perhaps a more general expression for the highest power of 2 dividing some even $n$?

EDIT: This is equivalent to finding an expression for the highest power of 2 dividing some even $n$, however finding it in terms of $a$ and $b$ may make it more useful for what I have described below.


Motivation For Asking:


The reason for this particular question is because, having had a look at the Collatz conjecture, I have found that positive odd integers $n$ of the form $2^a\cdot\left(2b-1\right)-1$ will iterate to the even value of $3^a\cdot\left(2b-1\right)-1$ after $a$ iterations of $\frac{3n-1}{2}$, then being divided by the highest power of 2 dividing it. Since I have also found that numbers of the form ${\left(\frac{2}{3}\right)}^c\cdot\left(2^{3^{c-1}\cdot(2d-1)}+1\right)-1$ become powers of 2 after $c$ iterations, I am hoping to find an expression for the number of iterations for $n$ to become a power of 2, and hence reach the 4-2-1 loop.


Updates:


EDIT 1: I have found a post on mathoverflow at https://mathoverflow.net/questions/29828/greatest-power-of-two-dividing-an-integer giving a rather long expression for the highest power of 2 dividing any odd positive integer $n$ which may be useful.


EDIT 2: Here is an image displaying patterns I find quite interesting. It is from a program I wrote which displays the exponent of the highest power of 2 dividing each value of $3^a\left(2b-1\right)-1$, represented by lighter pixels for higher values and darker pixels for lower values. It is plotted on a 2d grid such that each pixel on the x-axis represents the $b$ value, starting from one, and the same for $a$ on the y-axis:

enter image description here

This seems to suggest that if $a$ and $b$ are both either odd or even, the highest power of 2 dividing $3^a\left(2b-1\right)-1$ is 2 (I am currently having a look at this further).


EDIT 3: Defining $2^{b_s}$ as the highest power of 2 dividing $1.5^{a_s}(n_{s}+1)-1$, I know that any odd $n_s=2^{a_s}(2x_s-1)-1$ will reach:

$$n_{s+1}=2^{a_{s+1}}(2x_{s+1}-1)-1=\frac{3^{a_s}(2x_s-1)-1}{2^{b_s}}=\frac{1.5^{a_s}(n_{s}+1)-1}{2^{b_s}}$$

This has led me to find an expression for the $z$th iteration, $T_z(n_1)$, starting from some odd $n_1$, of:

$$T(n_s)=\frac{1.5^{a_s}\left(n_s+1\right)-1}{2^{b_s}}=n_{s+1}$$

The expression I found is as follows:

$$T_z(n_1)=\frac{1.5^{\sum_{c=2}^{z}a_c}\left(1.5^{a_1}\left(n_1+1\right)-1\right)}{2^{\sum_{d=1}^{z}b_d}}+\frac{1.5^{a_z}-1}{2^{b_z}}+\sum_{e=2}^{z-1}\frac{1.5^{\sum_{f=e+1}^{z}a_f}\left(1.5^{a_e}-1\right)}{2^{\sum_{g=e}^{z}b_g}}$$

Hence, for the Collatz conjecture to be true:

$$T_z(n_1)=\frac{1.5^{\sum_{c=2}^{z}a_c}\left(1.5^{a_1}\left(n_1+1\right)-1\right)}{2^{\sum_{d=1}^{z}b_d}}+\frac{1.5^{a_z}-1}{2^{b_z}}+\sum_{e=2}^{z-1}\frac{1.5^{\sum_{f=e+1}^{z}a_f}\left(1.5^{a_e}-1\right)}{2^{\sum_{g=e}^{z}b_g}}=1$$

must have a unique solution for any odd $n_1$ such that $\left\{z,a_{1...z},b_{1...z}\in\mathbb{N^+}\right\}$

This raises a separate question - namely what can be said of $a_{s+1}$ and $b_{s+1}$ from the values of $a_{s}$ and $b_{s}$? If there turns out to be some connection, the values of $\sum_{i=1}^{z}a_{i}$ and $\sum_{i=1}^{z}b_{i}$ may be expressed simply in terms of $a_1$ and $b_1$, hence turning the problem into a (diophantine equation? I have not yet studied Mathematics beyond secondary school, so I am unsure of correct Mathematical terminology or notation - please feel free to correct me).


EDIT 4: As suggested by Gottfried Helms, when $3^a\left(2b-1\right)-1$ is written as $3^ab-\left(3^a+1\right)$, factoring out the highest power of 2 shows that for $a \equiv b \pmod 2$, the highest power of 2 dividing $3^a\left(2b-1\right)-1$ is 2, and for $a \equiv 1 \pmod 2$ where $b \equiv 0 \pmod 4$, or $a \equiv 0 \pmod 2$ where $b \equiv 3 \pmod 4$ it must be 4. In other cases it seems to be no longer dependant on $a$ or $b$ and becomes pseudo-random. This helps to explain the patterns found above, but not all of them.


$\endgroup$
  • 1
    $\begingroup$ Just by observation, it seems that for $b=4k$ the number of $2$s $=2-(a\%2)$ - i.e. $2$ if a is even and $1$ if a is odd. And for $b=4k+3$ the number of $2$s is $1+(a\%2)$. The patterns for $b=4k+1,2$ are more complicated but seem to share the same structure. $\endgroup$ – Christian Woll Jul 27 '17 at 8:15
  • 1
    $\begingroup$ I'd better write $3^a2b - (3^a+1)$ Then for $(3^a+1)$ there is a well known formula for the exponent of its primefactor $2$ depending on $a$. Then it is depending on the factors of $2$ in $b$ $\endgroup$ – Gottfried Helms Jul 29 '17 at 13:39
  • 1
    $\begingroup$ @GottfriedHelms thanks for your insight, just by observation does that formula happen to be $0.5(-1)^{a+1}+1.5$? $\endgroup$ – Daniel Castle Jul 29 '17 at 13:52
  • 1
    $\begingroup$ Hmm, I'm only now aware, that $(2b-1)$ might easily be itself of the form $3^c$ . In such cases $ 3^a(2b-1)-1 = 3^{a+c}-1 $ and this has any multiplicitiness of primefactor $2$ due to $ \{3^{a+c}-1, 2 \}=1+[a+c:2]+\{a+c,2\} $ $\endgroup$ – Gottfried Helms Jul 29 '17 at 18:25
  • 1
    $\begingroup$ @GottfriedHelms So in cases of $2^a(2b-1)$ such that $b=\frac{3^c+1}{2}$ and $a\equiv b\pmod 2$, $[a+c:2] + \{a+c, 2\}=0$, therefore $a+c$ must be odd, so when $c$ is odd, $a$ is even, and when $c$ is even, $a$ is odd $\endgroup$ – Daniel Castle Jul 29 '17 at 18:53
2
+25
$\begingroup$

This is only a reply to Daniel's comment but too long for the box

Legend: In the following I mean

  • $ \{expression,p \} $ the exponent to which primefactor $p$ occurs in $expression$
  • $[ m : a ]$ equals $1$ if $a$ divides $m$ otherwise it equals $0$


By analysis of cyclicitiness due to "little Fermat" of exponents of primefactor $2$ :

  • (1) given $\qquad \displaystyle \{3^n-1,2\} = 1 + [n:2] + \{n,2\} $

Then in general

  • (2) because $ \qquad \displaystyle 3^n+1 = { 3^{2n}-1 \over 3^n-1} $

it follows

  • (3) $ \displaystyle \qquad \qquad \{3^n+1,2\} = \{3^{2n}-1,2\} - \{3^{n}-1,2\} $

Algebraical reformulation of (3) using (1) and (2):

$ \displaystyle \qquad \{3^n+1,2\} \;= \left(1 + [2n:2] + \{2n,2\}\right) - \left(1 + [n:2] + \{n,2\}\right) \\ \qquad \qquad \qquad \quad = \left([2n:2] + \{2n,2\} \right) - \left([n:2] + \{n,2\} \right) \\ \qquad \qquad \qquad \quad = \left(1 + 1+\{n,2\}\right) - \left([n:2] + \{n,2\}\right) \\ \qquad \qquad \qquad \quad = 2 - [n:2] $

Result:

  • (4) $ \displaystyle \qquad \implies \{3^n+1 ,2 \} = 2 - [n:2] $

which agrees with your formulation in your comment.

$\endgroup$
2
$\begingroup$

After substituting different integers for $a$ and $b$, I came across a pattern I recognized from my personal research into the Collatz Conjecture. While I cannot guarantee or prove this pattern is consistent, this pattern may point the way to a better explanation or answer some of your questions.

The patterns I came across reference this sequence: 0,1,0,2,0,1,0,3,0,1,0,2,.... or $A007814$ in the OEIS. This pattern was found by recording the number of times you can divide each integer in the set of natural numbers by 2. This pattern pops up in the Hailstone sequences for 3x+1 as a result of the "if n is even, divide n by 2" rule.

I used an informal "brute force" method and collected some data for a few combinations for $a$ and $b$ into the formula $3^a(2b-1)-1$ and then recorded how many times 2 can be divided into the result. I recorded my results on this Google Doc.

The patterns reveal why using an odd $b$ and an odd $a$ (or an even $a$ and $b$) produce a result only divisible by 2 once: the values line up since the chance of a number being divisible by 2 is roughly 50% and for every value of $a$ the values seem to alternate, according to my results. As for the first question, this pattern builds on itself infinitely, so supposedly there are an infinite number of possible variable combinations to get the maximum value for $n$. As for simplifying this into an expression of some-sort, I don't know how to do that or where to start. While the patterns do seem to have somewhat of a regularity, the variables can vary the patterns quite a bit, so much a seemingly random $2^9$ can be thrown in for seemingly no reason.

Unfortunately, I am not a mathematician and do not have the proper training to know if I stated the obvious or not, or if I am of any use to answering your other questions. I am sorry if this response is not helpful, this is what I found and what I understand.

When I posted this, I only went up to $a = 4$, I will add more data to increase the sample size if needed.

$\endgroup$
  • $\begingroup$ Thanks for highlighting this sequence and your data, I will definitely take a look and investigate further :) $\endgroup$ – Daniel Castle Jul 29 '17 at 19:08

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.