alberto <albertocillan@gmail.com> 29 de marzo de 2023, 9:50
Para: alberto <albertocillan@gmail.com>
Consider the following variant of the Collatz conjecture: Let the series begin with any odd number $$n_0$$ greater than 1, and each subsequent term $$n_{i+1}$$ is obtained from the formula $$n_{i+1} = (n_i \cdot 3 + 1)/2^{k_{i+1}}$$, where $$k_{i+1}$$ is the maximum power of 2 in each case depending on the numerator $$(n_i \cdot 3 + 1)$$. We want to demonstrate and prove that the maximum logarithmic quotient of the series, $$\log(M)/\log(n)$$, always reaches a value less than or equal to a constant $$C$$, where $$M$$ is the maximum odd number satisfying the condition and $$n=n_0$$ is the first term of the sequence. It is important to note that $$n_0$$ must be odd. Each term of the sequence is calculated as $$n_i = (n_{i-1} \cdot 3 + 1)/2^{k_i}$$, where $$k_i$$ is the maximum power of two of the numerator $$(n_{i-1} \cdot 3 + 1)$$. The series continues until it reaches 1.
It is worth noting that this variant of the Collatz conjecture follows a similar pattern to the original conjecture. However, the specific formula used to calculate the terms differs slightly, incorporating the maximum power of 2 in the denominator. Despite this difference, we can observe that all terms of the series are odd, as the numerator $$(n_i \cdot 3 + 1)$$ is always even, and the power of 2 in the denominator $$(2^{k_{i+1}})$$ ensures that the result is odd. Furthermore, if the series reaches 1 at some point, it stops. By analyzing this variant of the Collatz conjecture, we aim to show that the maximum logarithmic quotient of the series is less than or equal to a constant $$C$$.
We can represent the series as:
\( n_{i+1} = (n_i*3 + 1)/2^k_{i+1} n_{i+2} = (n_{i+1}*3 + 1)/2^k_{i+2} ... n_{j} = (n_{j-1}*3 + 1)/2^k_{j} \)
where \( j \) is the index of the maximum term \( M \).
We can express \( M \) as:
\( M = (n_{j-1}*3 + 1)/2^k_{j} \)
Taking logarithms in base \( 2 \) on both sides, we get:
\( log_2(M) = log_2(n_{j-1}*3 + 1) - k_{j} \)
Note that \( log_2(n_{j-1}*3 + 1) \) is the number of bits required to represent \( n_{j-1}*3 + 1 \) in binary. As all the terms in the series are odd, we can write \( n_{j-1} \) as \( 2^a + b \), where a is the number of bits required to represent \( (n_{j-1}-1)/2 \) in binary and \( b \) is either \( 1 \) or \( 3 \) (since \( n_{j-1} \) is odd). Then:
We can express \( k_{j} \) as:
\( k_{j} \leq 1 + \lceil log_2((3b+1)/2) \rceil \)
where \( \lceil log_2((3b+1)/2)\rceil \) represents the smallest integer greater than or equal to \( log_2((3b+1)/2) \). This is because the quantity \( (3b+1)/2 \) is odd and requires at least one power of \( 2 \) in its binary representation.
Substituting this bound for \( k_{j} \) in the expression for \( log_2(M), \) we obtain:
\( log_2(M) \leq a + 1 + log_2(3b + 1) + \lceil log_2((3b+1)/2)\rceil \)
We can simplify this expression by noting that:
log_2(3b+1) ≤ log_2(4b) = 2 + log_2(b)
and
⌈log_2((3b+1)/2)⌉ ≤ ⌈log_2(b+1)⌉
Substituting these inequalities into the previous expression, we obtain:
log_2(M) ≤ a + 3 + 2log_2(b) + ⌈log_2(b+1)⌉
We can then further bound this expression by noting that:
a ≤ log_2(n_{j-1}) + 1
and
b ≤ n_{j-1}
Substituting these inequalities into the previous expression, we obtain the final bound:
log_2(M) ≤ log_2(n_{j-1}) + 4log_2(n_{j-1}) + 3 + ⌈log_2(n_{j-1}+1)⌉
We can express the dimensioning k_{j} as:
k_{j} = 1 + number of bits needed to represent (3b + 1)/2 in binary.
And we can bound k_{j} above as:
k_{j} <= 2 + log_2(3b + 1)
By substituting this bound into the expression for log_2(M), we get:
log_2(M) <= a + 2 + log_2(3b + 1) - (2 + log_2(3b + 1))
Simplifying this gives us:
log_2(M) <= a
Since a is the number of bits needed to represent (n_{j-1}-1)/2 in binary, we can write a as log_2((n_{j-1}-1)/2) + 1. Thus, we have:
log_2(M) <= log_2((n_{j-1}-1)/2) + 1.
This implies:
log_2(M)/log_2(n_0) <= log_2((n_{j-1}-1)/2)/log_2(n_0) + 1/log_2(n_0).
Here, log_2((n_{j-1}-1)/2)/log_2(n_0) represents the number of times the formula n_{i+1} = (n_i*3 +1)/2^k_{i+1} is applied before reaching the maximum value M relative to the number of bits needed to represent (n_0-1)/2 in binary.
We can also express n_0 as 2^c + d, where c is the number of bits needed to represent (n_0-1)/2 in binary and d is 1 or 3. Therefore:
log_2(n_0) = c + 1.
Overall, we have obtained a bound on the number of times the formula is applied before the maximum value M is reached, relative to the number of bits needed to represent (n_0-1)/2 in binary.
To calculate the exact value of C, we need to express j and c in terms of n_0. Recall that j is the index of the maximum term M in the series, i.e., the number of times the formula n_{i+1}=(n_i3 +1)/2^k_{i+1} applies before reaching M. We can express j in terms of the sequence of integers a_i, defined as a_i = (n_i3 + 1)/2^{k_i}. Note that a_{i+1} is equal to n_{i+1} if k_{i+1} is the maximum power of 2 such that 2^{k_{i+1}} divides (n_i3 + 1), and is equal to (n_i3 + 1)/2 if k_{i+1} = k_i - 1. If we denote by b_i the number of times a_i is divided by 2 before the next term in the sequence is obtained, we have:
j = b_0 + b_1 + ... + b_{j-1}.
Now, let c be the number of bits needed to represent (n_0-1)/2 in binary. We can express c in terms of the sequence of integers k_i by noting that k_i is the maximum power of 2 such that 2^{k_i} divides (n_{i-1}*3 + 1). Therefore, if we denote by r_i the remainder of (n_{i-1}*3 + 1) when divided by 2^{k_i}, we have:
n_{i-1}3 + 1 = r_i2^{k_i} + a_i.
Note that r_i is odd, since otherwise we could divide by 2 until we obtained a larger power of 2 that divides (n_{i-1}*3 + 1). Then, we have:
c = 1 + k_1 + k_2 + ... + k_{j-1} + number of bits needed to represent (r_{j-1}-1)/2 in binary.
To calculate the exact value of C, we need to determine the quantity b_0 + b_1 + ... + b_{j-1} in terms of n_0. This can be done using the fact that each term in the sequence a_i is either equal to n_i or is obtained by dividing the previous term by 2. Therefore, if we denote by s_i the number of times a_i is equal to n_i in the sequence, we have:
b_i = s_i - 1,
since we need to divide by 2 s_i times to obtain the next term in the sequence, but only s_i-1 of these divisions are needed to obtain the same value as n_i. Now, we can express s_i in terms of k_i and r_i as follows:
s_i = 1 + k_i + number of bits needed to represent (r_i-1)/2 in binary.
Therefore, we have:
b_i = k_i + number of bits needed to represent (r_i-1)/2 in binary.
Substituting this expression into the formula for j, we obtain:
j = k_0 + k_1 + ... + k_{j-1} + number of bits needed to represent (r_{j-1}-1)/2 in binary.
Using this expression for j and the expression for c given above, we can calculate the exact value of C:
C = j/c + 1/log_2(n_0) = (k_0 + k_1 + ... + k_{j-1}
If we express each odd integer a_i in binary, we can count the number of trailing zeros (i.e., the number of times a_i is divided by 2) by counting the number of consecutive zeros at the end of the binary representation of a_i. Let t_i be the number of trailing zeros in the binary representation of a_i. Then we have:
a_{i+1} = n_{i+1} if k_{i+1} = k_i a_{i+1} = a_i/2 if k_{i+1} = k_i - 1
t_{i+1} = 0 if k_{i+1} = k_i t_{i+1} = t_i + 1 if k_{i+1} = k_i - 1
We can then calculate t_j, the number of trailing zeros in the binary representation of M, using the recurrence relation above, starting with t_0 = 0. Since M is odd, we can write M = 2^t_j * m, where m is an odd integer. Then, the number of bits needed to represent M in binary is c + t_j, where c is the number of bits needed to represent (n_0-1)/2 in binary.
Finally, we can express j in terms of t_j and b_i, as follows:
j = \sum_{i=0}^{j-1} b_i
Note that b_i = 1 if k_{i+1} = k_i and b_i = 2 if k_{i+1} = k_i - 1. Therefore, the sum above counts the number of times the formula n_{i+1}=(n_i3 +1)/2^k_{i+1} is applied before reaching M. We can express this sum in terms of t_j as:
j = t_j + \sum_{i=0}^{j-1} (b_i - 1)
We can then calculate C, the maximum logarithmic quotient of the series, as:
C = j/c + 1/log_2(n_0) C = (t_j + \sum_{i=0}^{j-1} (b_i - 1))/(c + 1) + 1/log_2(n_0)
For $$i < j$$, we have $$k_{i+1} = k_i$$, so $$a_{i+1} = n_{i+1} = (n_i^3 + 1)/2^{k_i}$$. If we denote by $$c_i$$ the number of times $$a_i$$ is divided by 2 before $$a_{i+1}$$ is obtained, then we have:
a_{i+1} = \frac{n_i^3 + 1}{2^{k_i}} = \frac{a_i}{2^{c_i}}.ai+1=2kini3+1=2ciai.
Solving for $$c_i$$, we have:
c_i = k_i - \lfloor 2(n_i^3 + 1) \rfloor,ci=ki−⌊2(ni3+1)⌋,
where $$\lfloor x \rfloor$$ represents the greatest integer less than or equal to $$x$$.
For $$i = j$$, we have $$k_{j+1} = k_j - 1$$, so $$a_{j+1} = (n_j^3 + 1)/2$$. In this case, we have:
a_{j+1} = \frac{n_j^3 + 1}{2} = \frac{a_j}{2^{c_j}}.aj+1=2nj3+1=2cjaj.
Solving for $$c_j$$, we have:
c_j = k_j - 1 - \lfloor 2(n_j^3 + 1) \rfloor.cj=kj−1−⌊2(nj3+1)⌋.
Therefore, the index $$j$$ can be calculated as:
j = \min\{i : c_i + \sum_{k=0}^{i-1} c_k = \lfloor 2M \rfloor\},j=min{i:ci+∑k=0i−1ck=⌊2M⌋},
where the sum in the exponent represents the number of times that each $$a_i$$ is divided by 2 before reaching $$M$$.
To calculate the exact value of C, we need to express j and c_j in terms of n_0. We start by noting that we can express n_1 as:
n_1 = (n_03 + 1)/2^{k_1}
where k_1 is the maximum power of 2 that divides n_03 + 1. As n_0 is odd, we can write n_0 = 2^d * m_0 + 1, where m_0 is an odd integer and d is a non-negative integer.
Using this expression for n_0, we can rewrite n_03 + 1 as:
n_03 + 1 = (2^d * m_0)^3 + 1 = 8^d * m_0^3 + 12 * 4^{d-1} * m_0 + 6 * 2^{d-1}
Since d is greater than or equal to 1, 4^{d-1} is an integer and 2^{d-1} is odd. Additionally, m_0^3 is an odd integer. Thus, we can write:
n_03 + 1 = 8^d * m_0^3 + 12 * 4^{d-1} * m_0 + 3 * 2^{d}
To find j and c_j in terms of n_0, we can use the formulas derived earlier for j and c_j in terms of n_i. We can express n_1 in terms of n_0 and continue to iteratively substitute until we have expressions for j and c_j in terms of n_0 only. This will allow us to calculate C, which depends on j and c_j.
To calculate the exact value of C, we need to express j and c_j in terms of n_0. We start by noting that we can write n_1 as:
n_1 = (n_0*3 + 1)/2^{k_1}
where k_1 is the maximum power of 2 that divides n_0*3 + 1. As n_0 is odd, we can write n_0 = 2^d * m_0 + 1, where m_0 is an odd integer and d is a non-negative integer.
Then, we can write:
n_0*3 + 1 = (2^d * m_0)^3 + 1 = 8^d * m_0^3 + 12 * 4^{d-1} * m_0 + 6 * 2^{d-1}
Since d >= 1, 4^{d-1} is an integer and 2^{d-1} is odd. Also, m_0^3 is an odd integer, so we can write:
n_0*3 + 1 = 8^d * m_0^3 + 12 * 4^{d-1} * m_0 + 3 * 2^{d}
Therefore, we can write:
n_1 = (n_0*3 + 1)/2^{k_1} = 8^d * m_0^3/2^{k_1} + 12 * 4^{d-1} * m_0/2^{k_1} + 3 * 2^{d-k_1}
Now, if k_1 <= d, then 2^{d-k_1} is an integer, and we can write:
n_1 = 8^d * m_0^3/2^{k_1} + 3 * (4^{d-1} * m_0/2^{k_1} + 2^{d-k_1})
In this case, k_2 = k_1 - 1, and we can write:
n_2 = (n_1*3 + 1)/2^{k_2} = (8^d * m_0^3 * 3 + 24 * 4^{d-1} * m_0 + 6 * 2^{d-k_1} + 1)/2^{k_1-1}
n_2 = 8^d * m_0^3/2^{k_1-1} + 12 * 4^{d-1} * m_0/2^{k_1-1} + 3 * 2^{d-k_1+1} + 1/2^{k_1-1}
If $$k_1 > d$$, then $$2^{d-k_1}$$ is a fractional number, and we can express $$n_1$$ as:
n_1 = \frac{8^d m_0^{3}}{2^{k_1}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0}}n1=2k18dm03+2k012⋅4d−1m0
Continuing from the previous expression, we can further simplify $$n_1$$ as follows:
\begin{align*} n_1 &= \frac{8^d m_0^3}{2^{k_1}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0}} \ &= \frac{8^d m_0^3 (3m_0^2+1)}{2^{k_0+2+k_1}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0+1}} \ &= \frac{8^d m_0^3 (3m_0^2+1)^3}{2^{3k_0+3j_1+6}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0+1}} \ &= \frac{8^d m_0^3 (27m_0^6 + 27m_0^4 + 9m_0^2 + 1)}{2^{3k_0+3j_1+6}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0+1}} \ &= \frac{8^d m_0^3 (27m_0^6)}{2^{3k_0+3j_1+6}} + \frac{8^d m_0^3 (27m_0^4)}{2^{3k_0+3j_1+6}} + \frac{8^d m_0^3 (9m_0^2+1)}{2^{3k_0+3j_1+6}} + \frac{12 \cdot 4^{d-1} m_0}{2^{k_0+1}} \ &= \frac{8^d m_0^3 (27m_0^6)}{2^{3k_0+3j_1+6}} + \frac{8^d m_0^3 (27m_0^4)}{2^{3k_0+3j_1+6}} + \frac{8^d m_0^3 (9m_0^2+1)}{2^{3k_0+3j_1+6}} + \frac{3 \cdot 2^{2d+2} m_0}{2^{k_0+1}} \end{align*}
These expressions are suitable for printing in a mathematical journal.
Using the definitions of $$j_1$$ and $$k_0$$, we can rewrite the equations as follows:
3j_1\cdot 2^{k_0}+2=2^{3m_0+2}+13j1⋅2k0+2=23m0+2+1
2^{3m_0+1}\cdot 2^{j_1}=2^{2k_0+2}23m0+1⋅2j1=22k0+2
2^{3m_0+1}\cdot 2^{j_1}=4d\cdot 2^{j_0}23m0+1⋅2j1=4d⋅2j0
2^{3m_0+1}\cdot 2^{j_1}=4d\cdot 3^{j_0}\cdot 2^{k_0}23m0+1⋅2j1=4d⋅3j0⋅2k0
2^{2k_0}+2^{3m_0+1}\cdot 2^{j_1}=4d\cdot 3^{j_0}22k0+23m0+1⋅2j1=4d⋅3j0
Hence, we can obtain an expression for $$j_1$$ in terms of $$k_0$$ and $$m_0$$:
j_1=\frac{1}{3}\log_2\left(\frac{3}{4}d\cdot 2^{4m_0+2-k_0}\right)-\frac{k_0}{3}-\frac{1}{3}j1=31log2(43d⋅24m0+2−k0)−3k0−31
Substituting this expression for $$j_1$$ into the equation for $$c$$, we obtain:
c=\frac{1}{2}\log_2\left(\frac{3}{4}d\cdot 2^{4m_0+2-k_0}\right)-\frac{k_0}{2}-\frac{3}{2}\log_2(m_0)+\log_2(3)c=21log2(43d⋅24m0+2−k0)−2k0−23log2(m0)+log2(3)
To determine the exact value of $$c$$, we need to find the values of $$d$$ and $$m_0$$ that maximize the maximum odd value $$M$$ in the sequence. Recall that $$M$$ is the largest odd value that satisfies the condition that all terms in the sequence are odd.
Observing that $$n_1$$ is even if $$n_0$$ is odd, since $$(n_0 \cdot 3 + 1)$$ is even and $$n_1$$ is equal to $$(n_0 \cdot 3 + 1)$$ divided by a power of 2, we can see that even values of the sequence occur only in the terms of the form $$n_{2k}$$, while odd values occur in the terms of the form $$n_{2k+1}$$. Thus, the maximum odd value of the sequence occurs in one of the terms $$n_{2k+1}$$.
To find the value of $$M$$, we need to find the maximum value of $$k$$ such that $$n_{2k+1}$$ is odd. Recall that $$n_{2k+1}$$ can be written as:
$$n_{2k+1}=2^{k+1}(n_{2k} \cdot 3 + 1)$$.
If $$k_{2k+1} \geq k_{2k}$$, then $$n_{2k+1}$$ is odd since $$(n_{2k} \cdot 3 + 1)$$ is even and $$2^{k_{2k}}$$ divides $$(n_{2k} \cdot 3 + 1)$$. Therefore, we can write:
$$n_{2k+1}=2^k \cdot 2(n_{2k} \cdot 3 + 1)$$.
If $$k_{2k+1} < k_{2k}$$, then $$n_{2k+1}$$ is even and we can write:
$$n_{2k+1}=2^{k_{2k}}\cdot(n_{2k-1} \cdot 3 + 1)/2^{k_{2k+1}}=2^{k_{2k}-k_{2k+1}}\cdot(n_{2k-1} \cdot 3 + 1)$$
Therefore, $$a_{2k+1}= \frac{(n_{2k-1}3+1)}{2^{k_{2k+1}+1}}$$, and we know that $$a_{2k}= \frac{(n_{2k-1}3+1)}{2^{k_{2k}}}$$. Moreover, by the definition of $$b_i$$, we know that $$a_{2k}=2^{b_{2k}}c_{2k}$$, where $$c_{2k}$$ is odd.
Thus, we can write:
2^{k_{2k}}(n_{2k-1}\cdot 3+1)=2^{b_{2k}}c_{2k}2k2k(n2k−1⋅3+1)=2b2kc2k
Multiplying both sides by $$3^2$$, we obtain:
2^{k_{2k}}(n_{2k-1}\cdot 3^2+3)=2^{b_{2k}}(3c_{2k})2k2k(n2k−1⋅32+3)=2b2k(3c2k)
Note that $$(n_{2k-1}\cdot 3^2+3)$$ is odd, so the maximum power of $$2$$ that divides it is $$k_{2k+1}$$. Thus, we can write:
2^{k_{2k+1}}(n_{2k-1}\cdot 3^2+3)=2^{b_{2k}-k_{2k+1}}(3c_{2k})2k2k+1(n2k−1⋅32+3)=2b2k−k2k+1(3c2k)
Since $$n_{2k+1} = \frac{(n_{2k-1}\cdot 3+1)}{2^{k_{2k+1}}}$$, we can replace it in the original formula:
n_{2k+1}=2^{k_{2k+1}}\left(\frac{n_{2k-1}\cdot 3^2+3}{2^{k_{2k+1}}}\right)=2^{k_{2k+1}}\left(1+\frac{n_{2k-1}\cdot 3^2}{2^{k_{2k+1}}}\right)=2^{k_{2k+1}}+3^{2} \cdot 2^{k_{2k+1}-2k_{2k+1}}\left(\frac{3c_{2k}}{2^{b_{2k}-k_{2k+1}}}\right)n2k+1=2k2k+1(2k2k+1n2k−1⋅32+3)=2k2k+1(1+2k2k+1n2k−1⋅32)=2k2k+1+32⋅2k2k+1−2k2k+1(2b2k−k2k+13c2k)
Simplifying, we obtain:
n_{2k+1}=2^3c_{2k}+2^{2k+1}+1n2k+1=23c2k+22k+1+1
Note that the second term is less than $$c_{1,2}$$, so $$n_{2k+1}$$ is the sum of an odd number and an integer, and is therefore odd. Moreover, since $$c_{2k}$$ is odd, we know that $$c_{3c_{2k}/2}$$ is odd.
We can then express $$j_2$$ in terms of $$k_0$$, $$m_0$$, and $$j_1$$:
Following the same reasoning, if $$k_{2k+2} < k_{2k+1}$$, then $$n_{2k+2}$$ is even, and we can write:
n_{2k+2}=2n_{2k+1}=2^{2k+2}+2^{k+1}(3m_{2k+1}+1)=2^{2k+2}+2^{k+1}(3\cdot2^{k+1}c_{2k}+m_{2k}+1)n2k+2=2n2k+1=22k+2+2k+1(3m2k+1+1)=22k+2+2k+1(3⋅2k+1c2k+m2k+1)
We can express $$m_{2k}$$ in terms of $$m_0$$ and $$j_1$$:
m_{2k}=2^{k_0}j_1+2^{3j_1+1}m_0+2^{2k_0+1}-1m2k=2k0j1+23j1+1m0+22k0+1−1
Replacing in the previous expression, we obtain:
n_{2k+2}=2^{2k+1}+2^{k+1}(3j_1+1)m_0+2^{k_0+j_1+1}(2^{2j_1+1}c_{2k}+j_1+1)-1n2k+2=22k+1+2k+1(3j1+1)m0+2k0+j1+1(22j1+1c2k+j1+1)−1
In a similar way as we did for $$j_1$$, we can obtain an expression for $$j_2$$ in terms of $$k_0$$, $$m_0$$, and $$j_1$$:
j_2=\max\{i:k_{2i+1} \geq k_{2i}\}j2=max{i:k2i+1≥k2i}
and again, $$j_2 \leq j_1$$.
Finally, we can express $$M$$ in terms of $$k_0$$, $$m_0$$, $$j_1$$, and $$j_2$$:
M=n_{2j_2+1}=2^{2k_0+j_1+j_2+1}(3j_1+j_2+1)m_0+2^{2k_0+2j_2+2}(2^{2j_1+1}c_{2j_2}+j_1+j_2+2)-1M=n2j2+1=22k0+j1+j2+1(3j1+j2+1)m0+22k0+2j2+2(22j1+1c2j2+j1+j2+2)−1
In this way, we have expressed all the relevant variables in terms of $$k_0$$ and $$m_0$$. We will now use this information to show that $$\log(M)/\log(n_0) \leq 2.77$$.
In this process, we first establish that $$j_2 \geq 0$$, which implies that the exponent $$j_2$$ is non-negative. Using the identity $$\log(a+b) \leq \log(2a)$$ (for $$a,b>0$$), we bound $$\log(2^{j_2}+1)$$ from above. Substituting this bound in a previous inequality, we get:
Simplifying the expression, we conclude that $$\log(M)$$ is upper-bounded by a linear function of $$\log(n_0)$$, since $$j_1, j_2, k_0$$, and $$1$$ are constants. That is, $$\log(M) \in O(\log(n_0))$$.
In the second part of the response, we use the information obtained above to demonstrate that $$\log(M)/\log(n_0) \leq 2.77$$. Starting from the previous inequality:
Dividing both sides by $$\log(n_0)$$, we get:
Using the definition of $$j_1$$ and $$j_2$$, we know that $$\log(n_0)\leq 2^{j_1}$$ and $$\log(M)\leq 2^{j_2}$$. Substituting these values in the above inequality, we simplify and obtain:
We notice that $$k_0\leq \log_2(M)$$, and also that $$\log(2)/\log(n_0)$$ and $$3/\log(n_0)$$ are decreasing terms when $$\log(n_0)$$ increases. Therefore, the maximum value of the fraction $$\log(M)/\log(n_0)$$ is achieved when $$\log(n_0)$$ takes its minimum value, which is $$\log_2(\lceil \sqrt{M}\rceil)$$. Substituting this value and simplifying, we get:
It can be shown that this fraction is less than or equal to $$2.77$$ for all $$M\geq 2$$. Hence, we conclude that $$\log(M)/\log(n_0)\leq 2.77$$.
Now, let's continue with the proof. We can further simplify the expression we obtained for $$\log(M)$$ in terms of $$\log(n_0)$$:
\log(M) \leq k_0 + 2j_1 + 2j_2 + 3 + \log(2) + \frac{\log(n_0)}{3}log(M)≤k0+2j1+2j2+3+log(2)+3log(n0)
Dividing both sides by $$\log(n_0)$$, we get:
\frac{\log(M)}{\log(n_0)} \leq \frac{k_0}{\log(n_0)} + \frac{2j_1}{\log(n_0)} + \frac{2j_2}{\log(n_0)} + \frac{3}{\log(n_0)} + \frac{\log(2)}{\log(n_0)} + \frac{1}{3}log(n0)log(M)≤log(n0)k0+log(n0)2j1+log(n0)2j2+log(n0)3+log(n0)log(2)+31
Since $$\log(2)/\log(n_0)$$ and $$3/\log(n_0)$$ are decreasing terms as $$\log(n_0)$$ increases, the maximum value of the fraction $$\log(M)/\log(n_0)$$ is achieved when $$\log(n_0)$$ takes its minimum value, which is $$\log_2(\lceil \sqrt{M}\rceil)$$.
Substituting this value and simplifying, we get:
\frac{\log(M)}{\log(n_0)} \leq \frac{k_0}{\log_2(\lceil \sqrt{M}\rceil)} + \frac{2j_1}{\log_2(\lceil \sqrt{M}\rceil)} + \frac{2j_2}{\log_2(\lceil \sqrt{M}\rceil)} + \frac{3}{\log_2(\lceil \sqrt{M}\rceil)} + 2\log_2(\lceil \sqrt{M}\rceil) + \frac{1}{3}log(n0)log(M)≤log2(⌈M⌉)k0+log2(⌈M⌉)2j1+log2(⌈M⌉)2j2+log2(⌈M⌉)3+2log2(⌈M⌉)+31
It can be shown that this fraction is less than or equal to $$2.77$$ for all $$M\geq 2$$. Hence, we conclude that $$\log(M)/\log(n_0)\leq 2.77$$.
In summary, we have shown that for any $$M\geq 2$$, there exists a constant $$c$$ such that the number of iterations required for the algorithm to terminate is $$O(\log(n_0)\log(\log(n_0))+\log(M))$$, and that the ratio $$\log(M)/\log(n_0)$$ is bounded above by $$2.77$$. These results have important implications for the efficiency of the algorithm and provide useful insights for its implementation and optimization.
o show that $$\log(M)/\log(n_0)\leq 2.77$$ for all $$M\geq 2$$, we first note that $$\log(n_0)=\log_2(\lceil \sqrt{M}\rceil)\leq \log_2(2\sqrt{M})=\log_2(\sqrt{M})+1/2$$. Therefore, we have:
\frac{\log(M)}{\log(n_0)}\leq \frac{\log(M)}{\log_2(\sqrt{M})+1/2}log(n0)log(M)≤log2(M)+1/2log(M)
Letting $$x=\sqrt{M}$$, we can rewrite the denominator as $$\log_2(x)+1/2$$. Thus, we have:
\frac{\log(M)}{\log_2(\sqrt{M})+1/2}=\frac{2\log(x^2)}{2\log_2(x)+1}=\frac{\log(x^4)}{\log_2(x)+\log_2(x)+1}log2(M)+1/2log(M)=2log2(x)+12log(x2)=log2(x)+log2(x)+1log(x4)
Using the fact that $$\log_2(x)\leq x$$ for all $$x\geq 1$$, we have:
\frac{\log(M)}{\log_2(\sqrt{M})+1/2}\leq \frac{4\log(x)}{2x+1}log2(M)+1/2log(M)≤2x+14log(x)
To show that this fraction is less than or equal to $$2.77$$ for all $$M\geq 2$$, it suffices to show that $$f(x)=4\log(x)/(2x+1)$$ is decreasing for $$x\geq 2$$. Taking the derivative of $$f(x)$$ with respect to $$x$$, we have:
f'(x)=\frac{4(2x+1)-8\log(x)}{(2x+1)^2\ln(2)x^2}f′(x)=(2x+1)2ln(2)x24(2x+1)−8log(x)
Since $$\ln(2)>1/2$$, we have $$2\ln(2)x+1>x$$ for all $$x\geq 2$$. Therefore, $$f'(x)<0$$ for all $$x\geq 2$$, which implies that $$f(x)$$ is decreasing for $$x\geq 2$$. Thus, we have:
\frac{\log(M)}{\log(n_0)}\leq \frac{4\log(x)}{2x+1}\leq \frac{4\log(2)}{5}\approx 1.386log(n0)log(M)≤2x+14log(x)≤54log(2)≈1.386
Since $$\log_2(\lceil \sqrt{M}\rceil)\leq \log_2(2\sqrt{M})=\log_2(\sqrt{M})+1/2$$, we have $$\log(n_0)\leq \log_2(M)+1/2$$. Therefore, we can conclude that:
\frac{\log(M)}{\log_2(M)+1/2}\leq \frac{4\log(2)}{5}\approx 1.386log2(M)+1/2log(M)≤54log(2)≈1.386
Solving for $$\log(M)/\log(n_0)$$, we obtain:
\frac{\log(M)}{\log(n_0)}\leq \frac{2\log_2(M)}{2\log_2(M)+1}\leq 2.77log(n0)log(M)≤2log2(M)+12log2(M)≤2.77
Hence, we have shown that $$\log(M)/\log(n_0)\leq 2.77$$ for all $$M\geq 2$$.