Skip to main content
Rollback to Revision 1
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.


PS. From the above analysis it also follows that the test fails any prime $k$ with composite $2k^2-1$, since in that case $B_{2k}>6k$. If a counterexample passing the test exists, it must be composite.

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.


PS. From the above analysis it also follows that the test fails any prime $k$ with composite $2k^2-1$, since in that case $B_{2k}>6k$. If a counterexample passing the test exists, it must be composite.

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.

added 143 characters in body; added 67 characters in body
Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.


PS. From the above analysis it also follows that the test fails any prime $k$ with composite $2k^2-1$, since in that case $B_{2k}>6k$. If a counterexample passing the test exists, it must be composite.

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.


PS. From the above analysis it also follows that the test fails any prime $k$ with composite $2k^2-1$, since in that case $B_{2k}>6k$. If a counterexample passing the test exists, it must be composite.

Source Link
Max Alekseyev
  • 34.3k
  • 5
  • 74
  • 152

Below I will prove that the proposed test is necessary, that is, if $k\in\text{A106483}$ then $b(2k+1)=6k$.

Following the simplification proposed by Will Sawin in the comments, the test for a given odd $k$ consists in setting $B_0 := 1$ and then iteratively computing for $i=1,2,\dots,2k$ $$B_i = B_{i-1} + \gcd((2i-1)(2k+1)+1,B_{i-1}),$$ and eventually testing whether $B_{2k} = 6k$.

Let $k$ be an odd prime such that $2k^2-1$ is also prime.

Trivially we have $B_1 = 2$, $B_2 = 4$, $B_3=8$. Since $(2i-1)(2k+1)+1$ is even, we observe that $B_i$ is even for all $i\geq 1$, implying that $2\mid \gcd((2i-1)(2k+1)+1,B_{i-1})$ for all $i\geq 2$.

Let $t>3$ be the smallest integer such that $\gcd((2t-1)(2k+1)+1,B_{t-1}) > 2$. Then $B_{t-1} = B_3 + 2(t-4) = 2t$ and thus $$2 < \gcd((2t-1)(2k+1)+1,B_{t-1}) = 2\gcd(k,t),$$ implying that $t=k$.

Now, we can derive by induction on $i$ that $$B_i = \begin{cases} 2(i+1), & \text{if } 3\leq i < k;\\ 2(i+k), & \text{if } k\leq i \leq 2k. \end{cases} $$ The base case $i\leq k$ is already proved above. For $i>k$, by induction we have \begin{split} B_i & = 2(i-1+k) + \gcd((2i-1)(2k+1)+1,2(i-1+k)) \\ &= 2(i-1+k) + 2\gcd(2k^2-1,i-1+k) \\ &= 2(i+k), \end{split} where we used the fact that $2k^2-1$ is prime.

It remains to note that $B_{2k}=6k$ as expected.