For the * complete extraction of the factor* $p$ and its powers from a natural number $n$

let’s

$ qquad qquad $

While looking at the question of existences of 2-step-cycles in the generalized Collatz-problem for $mx+1$ I arrived, considering general divisibility conditions, at the question for which odd $b$ the evaluation of $f(b)$

$$ f(b) = {b^2 – {b-1}_2 }_2 overset{?}= 1 tag 2

$$

fully reduces to $1$.

I know, that $b=3$ there is a solution (the famous $(3^2-1)/2^3=1$). Generating a list for sequential $b$ didn’t suggest any useful pattern so far, so this didn’t help me with a clue.

For me it looks suspiciously like the problem might be of wider interest instead only for the Collatz-cycle sub-problem, where it occured.

Q1: Can we find a modular/diophantine argument for the impossibility of more solutions?

Q2: Additionally, can we say something more, if we use some other prime factor

$p ne 2$ for extraction $$ small f_p(b) = {b^2 – {b-1}_p }_p overset{?}= 1 tag 3$$?

*(Remark for Q2: One solution I found was $f_7(19)=1$, another one, but with even $b$, I’ve got $f_5(56)=1$ )*

*remark: I’ve asked this in MSE a couple of days before but except a short observation didn’t get an answer*

MathOverflow Asked by Gottfried Helms on December 30, 2020

4 AnswersThe question is equivalent to finding all squares which are of the form $2^a - 2^b + 1$. This MO answer discusses the related question which squares are of the form $2^a + 2^b + 1$, and presumably the techniques in the paper (which admittedly I haven't read) should be applicable in your case as well.

EDIT: The paper referenced in the MO answer is "The equations 2N ± 2M ± 2L = z2" by László Szalay, which should answer your question as well. Unfortunately, the link there doesn't work for me, but I hope this helps.

Correct answer by Random on December 30, 2020

The article of L. Szalay as mentioned by user Random, gives the solution.

We can reformulate
$$ begin{array} {}
{b^2 - {b-1}_2 }_2 & overset{?}= 1 &&& (1.1)\
b^2 - {b-1}_2 & overset{?}= 2^A & &&(1.2)\
2^B b^2 - (b-1) & overset{?}= 2^B 2^A & &&(1.3)\
4 cdot 2^{2B} b^2 - 4cdot 2^Bb + 1 & overset{?}= 2^{2B+2} 2^A &- 2^{B+2}&+1& (1.4)\
(2cdot 2^Bb - 1)^2 & overset{?}= 2^{A+2B+2} &- 2^{B+2}&+1& (1.5)\ hline
x^2 & = 2^n &- 2^m &+1& (2)\
end{array}$$
Szalay gives the following solutions in theorem 2:

$ displaystyle (n,m, x)in { (2t,t+1,2^t-1) mid t in mathbb N, t ge 2 }$.

Inserting this gives by $x=2^t-1$ that $b=1$, which is of course a trivial solution for $f(b)=1$.$ displaystyle (n,m, x) in {(t,t,1) mid t in mathbb N, t ge 1 }$

Here, to have $x=1$ we must have $2cdot 2^Bb - 1=1$ and $ 2^Bb =1 implies b=1, B=0$ which is again the trivial solution, and$ displaystyle (n,m, x) in {(5,3,5),(7,3,11),(15,3,181) }$

For $x=5$ we get $b=3$ which is the "known" solution, for $x=11$ we get again $b=3$ and finally for $x=181$ we get $b=91$ . By the latter we have in the lhs that $B=0$ but in the rhs we have with $m=3$ that $B=1$, which is in contradiction to the specific form in which my equation realizes Szalay's (with additional restrictions on $x$), so this is not an allowed case.

* Conclusion:* the two cases $b=1$ (trivial) and $b=3$ (known) are the only solutions for the equation in question.

* Underlying problem solved:* For the generalized Collatz-problem $ T(x): x to {mx+1 }_2 $ this means:

there are exactly the following $2$-step-cycles with $b=T(a)$ and $a=T(b)$ when $a=1$ is fixed:

- for $m$ of the form $m=2^k-1$ the trivial 2-step-cycle $a=b=1$ and
- for $m=5$ and $(a,b,m)=(1,3,5)$

*(The known 2-step-cycles for $m=181$ are not counted because their smallest element $a$ is $a ne 1$)*

^{Thanks to user "Random" for the reference to Szalay's article.}

Answered by Gottfried Helms on December 30, 2020

For Q1:

Let $b=2^kt+1$ with odd $t$. Then equality $f(b)=1$ is equivalent to $$(2^kt+1)^2-t=2^m$$ for some $m$ (notice that $m>2k$). This is a quadratic equation in $t$. To have integer solutions, its discriminant must be a square, that is $$2^{2k+2+m}-2^{k+2}+ 1=z^2$$ for some $z>0$.

There are no solutions with even $m$ since $$(2^{k+1+m/2})^2 > 2^{2k+2+m}-2^{k+2}+ 1 > (2^{k+1+m/2}-1)^2.$$ For odd $m$, we have $$2^{k+2} - 1 = 2^{2k+2+m}-z^2 = (2^{k+1+(m-1)/2}sqrt{2}-z)(2^{k+1+(m-1)/2}sqrt{2}+z) > (2^{k+1+(m-1)/2}sqrt{2}-z)2^{k+2+(m-1)/2}(sqrt{2}+1),$$ implying that $$0 < sqrt{2}-frac{z}{2^{k+1+(m-1)/2}} < frac{1}{2^{k+m-1}(sqrt{2}+1)} < frac{1}{(2^{k+1+(m-1)/2})^{3/2}}.$$ That is, $frac{z}{2^{k+1+(m-1)/2}}$ represents an order $3/2$ rational approximation to $sqrt{2}$, which suggests (although this is just a heuristics) that we should look for such fractions among convergents and semiconvergents to $sqrt{2}$. Their denominators are given by Pell numbers (A000129) and sums of consecutive Pell numbers (A001333). The latter are odd, while it is easy to establish that the former contain just two powers of $2$ -- namely, $1$ and $2$.

PS. The known solution gives $z=11$, $k=1$, $m=3$ with the rational approximation $frac{11}{8}$ to $sqrt{2}$ not being a convergent or a semiconvergent. So, above is not a proof but a heuristic argument that such approximations are extremely rare, and cannot be obtained from the known sources (convergents and semiconvergents) for good rational approximations.

Answered by Max Alekseyev on December 30, 2020

For Q2, if $p equiv 1 bmod 3$, then $p$ may be written as $p=x^2+xy+y^2$ for some $x,yinmathbb{Z}$. Additionally if $b^2-b+1=p^m$ for some integer $m>0$, then it may be seen that $b notequiv 1 bmod p$ and hence ${b-1}_p=b-1$. The above gives $(x^2+xy+y^2)^m=b^2-b+1$ or $$ ((x-yomega)(x-yomega^2))^m=(b+omega)(b+omega^2) $$ where $omega=exp(2 pi i/3)$. For example, in your example, $$ 7=2^2+2+1 $$ and $$ 7^3=19^2-19+1 $$ as $(2-omega)^3$ times a unit of $mathbb{Z}[omega]$ is equal to $19+omega$.

Also, for Q1, a partial answer (that can probably be extended further) is:

Let $1leq a_1 < a_2 < dots < a_n$ and let

$$ b=1+sum_{i=1}^n 2^{a_i}. $$

If $a_{n-1} < a_n - 2$, then $b-2^{a_n} < 2^{a_{n-1}+1} leq 2^{a_n-2}$ and $b^2 - 2^{2a_n} < 2^{2a_n}$. Thus if we write $b^2$ as

$$ b^2 = 2^{2a_n} + sum_{i in A}2^i, $$

the largest $i$ in $A$ satisfies $a_n+a_{n-1}+1 leq i < 2a_n$. However, for such $b$, we would have to have

$$ b^2 = 2^{2a_n} + sum_{i=1}^n 2^{a_n-a_1} $$

if ${b^2 - {b-1}_2}_2 = 1$. However, $a_n-a_1 < a_n+a_{n-1}+1$. Hence $b$ with $a_{n-1} < a_n - 2$ cannot satisfy ${b^2 - {b-1}_2}_2 = 1$.

Write

$$ b = 1+sum_{i=1}^n 2^{a_i} = 2^{a_n} + a $$ and assume that $a>0$. Then

$$ b^2 = (2^{a_n} + a)^2 geq 2^{2a_n+1} $$

if and only if

$$ a^2 + 2^{a_n+1}a - 2^{2a_n} geq 0. $$

As $a geq 0$, that means that

$$ b^2 geq 2^{2a_n+1} Leftrightarrow a geq 2^{a_n}(sqrt{2}-1). $$

If ${b^2 - {b-1}_2}_2 =1$, then $$ b^2 = 2^q + sum_{i=1}^{n}2^{a_i-a_1} $$

where $$ q=begin{cases}2a_n+1 mbox{ if } a geq 2^{a_n}(sqrt{2}-1)\2a_nmbox{ otherwise.}end{cases} $$

It is the case that

$$ {b-1}_2 = sum_{i=1}^n 2^{a_i-a_1} < 2^{a_n}. $$

If $a < 2^{a_n}(sqrt{2}-1)$ then $$b^2 - 2^{2a_n} = 2^{a_n+1}a + a^2 > 2^{a_n}.$$ Therefore if $a < 2^{a_n}(sqrt{2}-1)$, we cannot have ${b^2 - {b-1}_2}_2 =1$. Also, if $a geq 2^{a_n-1}$, then

$$ b^2 - 2^{2a_n+1} geq 2^{2a_n-2}. $$

$2^{2a_n-2} > 2^{a_n}$ if $a_n > 2$. Therefore if either $a < 2^{a_n}(sqrt{2}-1)$ or ($a geq 2^{a_n-1}$ and $a_n > 2$), we cannot have ${b^2 - {b-1}_2}_2 =1$.

Using this approach, it is possible to obtain:

Writing $b = 2^{a_n} + a$, with $0 < a < 2^{a_n}$, then ${b^2 - {b-1}_2}_2 = 1$ cannot happen when $a in mathbb{Z}$ and

$$ frac{a}{2^{a_n}} in (0,sqrt{2}-1) cup [sqrt{2+frac{1}{2^{a_n}}}-1,1). $$

The length of the interval $[2^{a_n}(sqrt{2}-1),2^{a_n}(sqrt{2+frac{1}{2^{a_n}}}-1))$ converges to $frac{1}{2sqrt{2}}$ as $a_n rightarrow infty$ and hence can contain at most one integer for each $a_n geq 1$. Hence for each $a_n geq 1$, there is at most one integer $a$ with $0 < a < 2^{a_n}$ such that $b = 2^{a_n} + a$ could possibly satisfy ${b^2 - {b-1}_2}_2 = 1$.

Answered by Tim on December 30, 2020

1 Asked on November 22, 2021 by zorns-llama

gn general topology metric spaces mg metric geometry real analysis

1 Asked on November 20, 2021 by gro-tsen

0 Asked on November 20, 2021 by liding

1 Asked on November 20, 2021

0 Asked on November 18, 2021

cv complex variables fourier analysis fourier transform pr probability real analysis

1 Asked on November 18, 2021 by nutty_wolf

0 Asked on November 18, 2021 by cheng-chiang-tsai

lie algebras nilpotent orbits reductive groups reference request

1 Asked on November 16, 2021

1 Asked on November 16, 2021 by soumya-basu

linear programming oc optimization and control optimal transportation

1 Asked on November 16, 2021 by user502940

entropy ergodic theory group actions measurable functions measure theory

1 Asked on November 16, 2021

cv complex variables eigenvector fa functional analysis linear algebra sp spectral theory

1 Asked on November 16, 2021

additive combinatorics arithmetic progression co combinatorics conjectures

0 Asked on November 16, 2021

ag algebraic geometry algebraic number theory algebraic stacks arithmetic geometry derived categories

0 Asked on November 16, 2021 by david-corwin

algebraic number theory class field theory reference request

1 Asked on November 14, 2021

2 Asked on November 14, 2021

cv complex variables generating functions real analysis taylor series

0 Asked on November 14, 2021 by agno

1 Asked on November 14, 2021 by yaoliding

at algebraic topology homotopy groups of sphere homotopy theory

0 Asked on November 12, 2021 by ghost-in-grothendieck-universe

a infinity algebras higher algebra mp mathematical physics operads

2 Asked on November 12, 2021

Get help from others!

Recent Answers

- Justin Markwell on Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- kjetil b halvorsen on How to test consistency of responses?
- Philipp on How do i draw a ray in unity
- DMGregory on MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- eric_kernfeld on How to test consistency of responses?

Recent Questions

- MouseLook Script “Pops” back to the last value when the script is enabled after being disabled or destroyed
- Unity app crashes when using unmodified custom Android manifest (didn’t find class “UnityPlayerActivity”)
- How do i draw a ray in unity
- How to test consistency of responses?
- How can I understand these variograms?

© 2022 AnswerBun.com. All rights reserved.