Mixing
Highest power of $2$ that divides $3n+1$ [on hold]
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Added: I give a reference to this thread for more details on the type of function that we need for retrieving the $c$ value. We use the capital pi notation such that when we reach the states: $00$, $10$ or $11$ we add by zero.
The highest power of $2$ that divides some natural number $n$ can also be stated as as the number of trailing zeros $m$ that $n$ got in base 2. So these zeros are removed when $n$ is divided by $2^m$.
For the Reduced Collatz Function: $R(n)=frac3n+12^m$, we need a function to find $m$, such that $R^0(n)$, $R^1(n)$, $R^2(n)$ ...and so on, always produces odd results.
$c$ is defined to be the bit-length of $3n+1$ divided by $2$, because we check consequtive bit-pairs, but I am wondering if $c$ should be defined differently, since the summation should exit (stop) when $S(n)$ reaches one of these values: $nequiv 0pmod4$, $nequiv 2pmod4$ or $nequiv 3pmod4$ ? Se the definitions of the functions below.
Studying the potential bit-patterns that $3n+1$ generates, gives us four basic cases:
$$beginarray hline
n & (3n+1) & ntz \ hline
111100101 &..0110000 &4 \ hline
111101101 &..1001000 &3 \ hline
111011101 &..0011000 &3 \ hline
100010101 &..1000000 &6 \ hline
100001001 &..0011100 &2 \ hline
... & ... &.. \ hline
endarray$$
It is only the first few bits that is important, except in the case where there's a pair of repeating $01$'s. From the table above we get (from pseudocode):
loop:
if 00 stop
if 01 add 2 and continue
if 10 stop
if 11 add 1 and stop
repeat loop
Studying the bit-pattern for each bitpair of $3n+1$ can make us create a specialized function to find the highest exponent that divides $3n+1$. (I guess other people have done this before?).
We now define the function $S(n)$ where $ninmathbbN$:
$S(n)=begincases
0 & nequiv 0pmod4 \
2 & nequiv 1pmod4\
0 & nequiv 2pmod4\
1 & nequiv 3pmod4endcases $
To check each bitpair, we may have to make the length of the bitstring an even number. (we can do that by minus or pluss $n pmod 2$).
Define $c$ to be the bitlength of $n$ divided by $2$:
$$c=fraclceil log_2(n)rceil-(n mod 2)2$$
changed from $+$ to $-(n mod 2)$ because $i=0$ in $Z(n)$. We could also do $c-1$ in sigma.
Define the function $Z$ to be the number of trailing zeros of (or highest power of $2$ dividing) $3n+1$:
$$Z(n)=sum_i=0^c fracS(3n+1)4^i$$
elementary-number-theory functions collatz
asked Aug 3 at 15:26
Natural Number Guy
366315
put on hold as unclear what you're asking by Servaes, amWhy, Adrian Keister, Clayton, José Carlos Santos 11 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
 |Â
show 1 more comment
up vote
1
down vote
favorite
Added: I give a reference to this thread for more details on the type of function that we need for retrieving the $c$ value. We use the capital pi notation such that when we reach the states: $00$, $10$ or $11$ we add by zero.
The highest power of $2$ that divides some natural number $n$ can also be stated as as the number of trailing zeros $m$ that $n$ got in base 2. So these zeros are removed when $n$ is divided by $2^m$.
For the Reduced Collatz Function: $R(n)=frac3n+12^m$, we need a function to find $m$, such that $R^0(n)$, $R^1(n)$, $R^2(n)$ ...and so on, always produces odd results.
$c$ is defined to be the bit-length of $3n+1$ divided by $2$, because we check consequtive bit-pairs, but I am wondering if $c$ should be defined differently, since the summation should exit (stop) when $S(n)$ reaches one of these values: $nequiv 0pmod4$, $nequiv 2pmod4$ or $nequiv 3pmod4$ ? Se the definitions of the functions below.
Studying the potential bit-patterns that $3n+1$ generates, gives us four basic cases:
$$beginarray hline
n & (3n+1) & ntz \ hline
111100101 &..0110000 &4 \ hline
111101101 &..1001000 &3 \ hline
111011101 &..0011000 &3 \ hline
100010101 &..1000000 &6 \ hline
100001001 &..0011100 &2 \ hline
... & ... &.. \ hline
endarray$$
It is only the first few bits that is important, except in the case where there's a pair of repeating $01$'s. From the table above we get (from pseudocode):
loop:
if 00 stop
if 01 add 2 and continue
if 10 stop
if 11 add 1 and stop
repeat loop
Studying the bit-pattern for each bitpair of $3n+1$ can make us create a specialized function to find the highest exponent that divides $3n+1$. (I guess other people have done this before?).
We now define the function $S(n)$ where $ninmathbbN$:
$S(n)=begincases
0 & nequiv 0pmod4 \
2 & nequiv 1pmod4\
0 & nequiv 2pmod4\
1 & nequiv 3pmod4endcases $
To check each bitpair, we may have to make the length of the bitstring an even number. (we can do that by minus or pluss $n pmod 2$).
Define $c$ to be the bitlength of $n$ divided by $2$:
$$c=fraclceil log_2(n)rceil-(n mod 2)2$$
changed from $+$ to $-(n mod 2)$ because $i=0$ in $Z(n)$. We could also do $c-1$ in sigma.
Define the function $Z$ to be the number of trailing zeros of (or highest power of $2$ dividing) $3n+1$:
$$Z(n)=sum_i=0^c fracS(3n+1)4^i$$
elementary-number-theory functions collatz
asked Aug 3 at 15:26
Natural Number Guy
366315
put on hold as unclear what you're asking by Servaes, amWhy, Adrian Keister, Clayton, José Carlos Santos 11 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
2
What is your question?
– gammatester
Aug 3 at 15:48
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43
 |Â
show 1 more comment
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Added: I give a reference to this thread for more details on the type of function that we need for retrieving the $c$ value. We use the capital pi notation such that when we reach the states: $00$, $10$ or $11$ we add by zero.
The highest power of $2$ that divides some natural number $n$ can also be stated as as the number of trailing zeros $m$ that $n$ got in base 2. So these zeros are removed when $n$ is divided by $2^m$.
For the Reduced Collatz Function: $R(n)=frac3n+12^m$, we need a function to find $m$, such that $R^0(n)$, $R^1(n)$, $R^2(n)$ ...and so on, always produces odd results.
$c$ is defined to be the bit-length of $3n+1$ divided by $2$, because we check consequtive bit-pairs, but I am wondering if $c$ should be defined differently, since the summation should exit (stop) when $S(n)$ reaches one of these values: $nequiv 0pmod4$, $nequiv 2pmod4$ or $nequiv 3pmod4$ ? Se the definitions of the functions below.
Studying the potential bit-patterns that $3n+1$ generates, gives us four basic cases:
$$beginarray hline
n & (3n+1) & ntz \ hline
111100101 &..0110000 &4 \ hline
111101101 &..1001000 &3 \ hline
111011101 &..0011000 &3 \ hline
100010101 &..1000000 &6 \ hline
100001001 &..0011100 &2 \ hline
... & ... &.. \ hline
endarray$$
It is only the first few bits that is important, except in the case where there's a pair of repeating $01$'s. From the table above we get (from pseudocode):
loop:
if 00 stop
if 01 add 2 and continue
if 10 stop
if 11 add 1 and stop
repeat loop
Studying the bit-pattern for each bitpair of $3n+1$ can make us create a specialized function to find the highest exponent that divides $3n+1$. (I guess other people have done this before?).
We now define the function $S(n)$ where $ninmathbbN$:
$S(n)=begincases
0 & nequiv 0pmod4 \
2 & nequiv 1pmod4\
0 & nequiv 2pmod4\
1 & nequiv 3pmod4endcases $
To check each bitpair, we may have to make the length of the bitstring an even number. (we can do that by minus or pluss $n pmod 2$).
Define $c$ to be the bitlength of $n$ divided by $2$:
$$c=fraclceil log_2(n)rceil-(n mod 2)2$$
changed from $+$ to $-(n mod 2)$ because $i=0$ in $Z(n)$. We could also do $c-1$ in sigma.
Define the function $Z$ to be the number of trailing zeros of (or highest power of $2$ dividing) $3n+1$:
$$Z(n)=sum_i=0^c fracS(3n+1)4^i$$
elementary-number-theory functions collatz
asked Aug 3 at 15:26
Natural Number Guy
366315
Added: I give a reference to this thread for more details on the type of function that we need for retrieving the $c$ value. We use the capital pi notation such that when we reach the states: $00$, $10$ or $11$ we add by zero.
The highest power of $2$ that divides some natural number $n$ can also be stated as as the number of trailing zeros $m$ that $n$ got in base 2. So these zeros are removed when $n$ is divided by $2^m$.
For the Reduced Collatz Function: $R(n)=frac3n+12^m$, we need a function to find $m$, such that $R^0(n)$, $R^1(n)$, $R^2(n)$ ...and so on, always produces odd results.
$c$ is defined to be the bit-length of $3n+1$ divided by $2$, because we check consequtive bit-pairs, but I am wondering if $c$ should be defined differently, since the summation should exit (stop) when $S(n)$ reaches one of these values: $nequiv 0pmod4$, $nequiv 2pmod4$ or $nequiv 3pmod4$ ? Se the definitions of the functions below.
Studying the potential bit-patterns that $3n+1$ generates, gives us four basic cases:
$$beginarray hline
n & (3n+1) & ntz \ hline
111100101 &..0110000 &4 \ hline
111101101 &..1001000 &3 \ hline
111011101 &..0011000 &3 \ hline
100010101 &..1000000 &6 \ hline
100001001 &..0011100 &2 \ hline
... & ... &.. \ hline
endarray$$
It is only the first few bits that is important, except in the case where there's a pair of repeating $01$'s. From the table above we get (from pseudocode):
loop:
if 00 stop
if 01 add 2 and continue
if 10 stop
if 11 add 1 and stop
repeat loop
Studying the bit-pattern for each bitpair of $3n+1$ can make us create a specialized function to find the highest exponent that divides $3n+1$. (I guess other people have done this before?).
We now define the function $S(n)$ where $ninmathbbN$:
$S(n)=begincases
0 & nequiv 0pmod4 \
2 & nequiv 1pmod4\
0 & nequiv 2pmod4\
1 & nequiv 3pmod4endcases $
To check each bitpair, we may have to make the length of the bitstring an even number. (we can do that by minus or pluss $n pmod 2$).
Define $c$ to be the bitlength of $n$ divided by $2$:
$$c=fraclceil log_2(n)rceil-(n mod 2)2$$
changed from $+$ to $-(n mod 2)$ because $i=0$ in $Z(n)$. We could also do $c-1$ in sigma.
Define the function $Z$ to be the number of trailing zeros of (or highest power of $2$ dividing) $3n+1$:
$$Z(n)=sum_i=0^c fracS(3n+1)4^i$$
elementary-number-theory functions collatz
asked Aug 3 at 15:26
Natural Number Guy
366315
edited yesterday
asked Aug 3 at 15:26
Natural Number Guy
366315
asked Aug 3 at 15:26
Natural Number Guy
366315
asked Aug 3 at 15:26
Natural Number Guy
366315
366315
put on hold as unclear what you're asking by Servaes, amWhy, Adrian Keister, Clayton, José Carlos Santos 11 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
put on hold as unclear what you're asking by Servaes, amWhy, Adrian Keister, Clayton, José Carlos Santos 11 hours ago
Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
2
What is your question?
– gammatester
Aug 3 at 15:48
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43
 |Â
show 1 more comment
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
2
What is your question?
– gammatester
Aug 3 at 15:48
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
2
2
What is your question?
– gammatester
Aug 3 at 15:48
What is your question?
– gammatester
Aug 3 at 15:48
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43
 |Â
show 1 more comment
2 Answers
2
active
oldest
votes
up vote
0
down vote
This is a collection of comments, not an answer.
This doesn't make sense; you have
$$Z(n)
=sum_i=0^c fracS(3n+1)4^i
=S(3n+1)sum_i=0^c frac14^i
< S(3n+1)sum_i=0^inftyfrac14^i
= S(3n+1)frac43leq2cdotfrac43<3,$$
which is obviously false.
Also, the first and third number in your table are not if the form $3n+1$. Where do these numbers come from? What is the second column supposed to show?
To determine the number of trailing zeroes in binary, why not simply divide by $2$ and check if the result is an integer, repeatedly, if you're programming?
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
add a comment |Â
up vote
0
down vote
If $3n+1 equiv 0 mod 2^k$ then it's clear that $3(n + 2^k) equiv 0 mod 2^k$ and for any $j < 2^k$ that $3(n+j) + 1not equiv 2^k$.
$n=1 implies 3n+1 equiv 0 mod 2^2$ so $3(1 + 2m) + 1 equiv 0 mod 2$.
$n=5implies 3n+1 equiv 0mod 2^4, 2^3$ so $3(5 + 8m) + 1 equiv 0 mod 8$ and $3(5+16m) + 1 equiv 0 mod 16$.
$n=5+16=21 implies 3n+1 = 64equiv 0mod 2^5, 2^6$.
Proposition: If $n = sum_j=0^k 4^k= frac 4^k+1 -13$ then
$3n+1 equiv 0 mod 2^m; m le 2k + 2$.
Pf: Is obvious: $3(frac 4^k+1 -13)+ 1 = 4^k+1$.
So to find and an $n$ so that $3n+1 equiv 0 mod 2^k$, Say $k = 10$ let $n = frac 4^lceil frac k2rceil - 13$, say $n = frac 2^10-13 = frac 1024 - 13 = 1+4+16 + 64+ 256 = 341$ so $3n + 1 =1024$.
=====
Oh, you want so say given $n = 569$ what is the highest power of $2$ that divides it.
So $n = 1 + 568$ and $568$ is divisible by $4$ so $4|3n+1$
$= 1 + 4 + 564$ if $8,16|564$ then $8,16|3n+1$ but they dont't so $4$ is the highest power of $2$ that divides $3n+1$.
A better example $341 + 5*512 = 2901$
$2901 = 1 + 2900=$
$1 + 4 + 2896$
$1 + 4 + 16 +2880=$ (and $16|2880$)
$1 + 4 + 16 + 64 + 2816 = $ (and $64|2816$)
$1 + 4 + 16 + 64 +256 + 2560 =$ (and $256|2560$)
$1 + 4 + 16 + 64 + 256 + 1024 + 1536 = $ (and $1024not mid 1548$ so we are done.)
The highest power of $2$ that divides $2901$ is the highest power of $2$ that divides $1548$ with is either $256$ or $512$. And it is $512$.
....
Of course, it would probably be easier to just do $2901*3 + 1 = 512*17$.
answered 2 days ago
fleablood
60.1k22575
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
This is a collection of comments, not an answer.
This doesn't make sense; you have
$$Z(n)
=sum_i=0^c fracS(3n+1)4^i
=S(3n+1)sum_i=0^c frac14^i
< S(3n+1)sum_i=0^inftyfrac14^i
= S(3n+1)frac43leq2cdotfrac43<3,$$
which is obviously false.
Also, the first and third number in your table are not if the form $3n+1$. Where do these numbers come from? What is the second column supposed to show?
To determine the number of trailing zeroes in binary, why not simply divide by $2$ and check if the result is an integer, repeatedly, if you're programming?
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
add a comment |Â
up vote
0
down vote
This is a collection of comments, not an answer.
This doesn't make sense; you have
$$Z(n)
=sum_i=0^c fracS(3n+1)4^i
=S(3n+1)sum_i=0^c frac14^i
< S(3n+1)sum_i=0^inftyfrac14^i
= S(3n+1)frac43leq2cdotfrac43<3,$$
which is obviously false.
Also, the first and third number in your table are not if the form $3n+1$. Where do these numbers come from? What is the second column supposed to show?
To determine the number of trailing zeroes in binary, why not simply divide by $2$ and check if the result is an integer, repeatedly, if you're programming?
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
add a comment |Â
up vote
0
down vote
up vote
0
down vote
This is a collection of comments, not an answer.
This doesn't make sense; you have
$$Z(n)
=sum_i=0^c fracS(3n+1)4^i
=S(3n+1)sum_i=0^c frac14^i
< S(3n+1)sum_i=0^inftyfrac14^i
= S(3n+1)frac43leq2cdotfrac43<3,$$
which is obviously false.
Also, the first and third number in your table are not if the form $3n+1$. Where do these numbers come from? What is the second column supposed to show?
To determine the number of trailing zeroes in binary, why not simply divide by $2$ and check if the result is an integer, repeatedly, if you're programming?
This is a collection of comments, not an answer.
This doesn't make sense; you have
$$Z(n)
=sum_i=0^c fracS(3n+1)4^i
=S(3n+1)sum_i=0^c frac14^i
< S(3n+1)sum_i=0^inftyfrac14^i
= S(3n+1)frac43leq2cdotfrac43<3,$$
which is obviously false.
Also, the first and third number in your table are not if the form $3n+1$. Where do these numbers come from? What is the second column supposed to show?
To determine the number of trailing zeroes in binary, why not simply divide by $2$ and check if the result is an integer, repeatedly, if you're programming?
edited Aug 3 at 15:59
community wiki
2 revs
Servaes
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
add a comment |Â
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
updated the table now for clarity. i did not give complete table, it is just to show some examples that the trailing zeros are defined by repeating patterns of $01$, and if there are one additional $11$.
– Natural Number Guy
Aug 3 at 16:03
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Maybe $c$ should be something else, because we need to stop the summation when $n equiv 0 pmod 4$, $n equiv 2 pmod 4$ and $n equiv 3 pmod 4$ Also I don't know where you got your $infty$ from? if $c=infty$ then $rightarrow n=infty$ right?
– Natural Number Guy
Aug 3 at 16:11
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
Since all terms in the sum are positive, I've 'replaced' $c$ by $infty$ to show that no matter what the value of $c$ is, the sum will never exceed $3$. This shows that the expression cannot work, no matter what $c$ you choose.
– Servaes
23 hours ago
add a comment |Â
up vote
0
down vote
If $3n+1 equiv 0 mod 2^k$ then it's clear that $3(n + 2^k) equiv 0 mod 2^k$ and for any $j < 2^k$ that $3(n+j) + 1not equiv 2^k$.
$n=1 implies 3n+1 equiv 0 mod 2^2$ so $3(1 + 2m) + 1 equiv 0 mod 2$.
$n=5implies 3n+1 equiv 0mod 2^4, 2^3$ so $3(5 + 8m) + 1 equiv 0 mod 8$ and $3(5+16m) + 1 equiv 0 mod 16$.
$n=5+16=21 implies 3n+1 = 64equiv 0mod 2^5, 2^6$.
Proposition: If $n = sum_j=0^k 4^k= frac 4^k+1 -13$ then
$3n+1 equiv 0 mod 2^m; m le 2k + 2$.
Pf: Is obvious: $3(frac 4^k+1 -13)+ 1 = 4^k+1$.
So to find and an $n$ so that $3n+1 equiv 0 mod 2^k$, Say $k = 10$ let $n = frac 4^lceil frac k2rceil - 13$, say $n = frac 2^10-13 = frac 1024 - 13 = 1+4+16 + 64+ 256 = 341$ so $3n + 1 =1024$.
=====
Oh, you want so say given $n = 569$ what is the highest power of $2$ that divides it.
So $n = 1 + 568$ and $568$ is divisible by $4$ so $4|3n+1$
$= 1 + 4 + 564$ if $8,16|564$ then $8,16|3n+1$ but they dont't so $4$ is the highest power of $2$ that divides $3n+1$.
A better example $341 + 5*512 = 2901$
$2901 = 1 + 2900=$
$1 + 4 + 2896$
$1 + 4 + 16 +2880=$ (and $16|2880$)
$1 + 4 + 16 + 64 + 2816 = $ (and $64|2816$)
$1 + 4 + 16 + 64 +256 + 2560 =$ (and $256|2560$)
$1 + 4 + 16 + 64 + 256 + 1024 + 1536 = $ (and $1024not mid 1548$ so we are done.)
The highest power of $2$ that divides $2901$ is the highest power of $2$ that divides $1548$ with is either $256$ or $512$. And it is $512$.
....
Of course, it would probably be easier to just do $2901*3 + 1 = 512*17$.
answered 2 days ago
fleablood
60.1k22575
add a comment |Â
up vote
0
down vote
If $3n+1 equiv 0 mod 2^k$ then it's clear that $3(n + 2^k) equiv 0 mod 2^k$ and for any $j < 2^k$ that $3(n+j) + 1not equiv 2^k$.
$n=1 implies 3n+1 equiv 0 mod 2^2$ so $3(1 + 2m) + 1 equiv 0 mod 2$.
$n=5implies 3n+1 equiv 0mod 2^4, 2^3$ so $3(5 + 8m) + 1 equiv 0 mod 8$ and $3(5+16m) + 1 equiv 0 mod 16$.
$n=5+16=21 implies 3n+1 = 64equiv 0mod 2^5, 2^6$.
Proposition: If $n = sum_j=0^k 4^k= frac 4^k+1 -13$ then
$3n+1 equiv 0 mod 2^m; m le 2k + 2$.
Pf: Is obvious: $3(frac 4^k+1 -13)+ 1 = 4^k+1$.
So to find and an $n$ so that $3n+1 equiv 0 mod 2^k$, Say $k = 10$ let $n = frac 4^lceil frac k2rceil - 13$, say $n = frac 2^10-13 = frac 1024 - 13 = 1+4+16 + 64+ 256 = 341$ so $3n + 1 =1024$.
=====
Oh, you want so say given $n = 569$ what is the highest power of $2$ that divides it.
So $n = 1 + 568$ and $568$ is divisible by $4$ so $4|3n+1$
$= 1 + 4 + 564$ if $8,16|564$ then $8,16|3n+1$ but they dont't so $4$ is the highest power of $2$ that divides $3n+1$.
A better example $341 + 5*512 = 2901$
$2901 = 1 + 2900=$
$1 + 4 + 2896$
$1 + 4 + 16 +2880=$ (and $16|2880$)
$1 + 4 + 16 + 64 + 2816 = $ (and $64|2816$)
$1 + 4 + 16 + 64 +256 + 2560 =$ (and $256|2560$)
$1 + 4 + 16 + 64 + 256 + 1024 + 1536 = $ (and $1024not mid 1548$ so we are done.)
The highest power of $2$ that divides $2901$ is the highest power of $2$ that divides $1548$ with is either $256$ or $512$. And it is $512$.
....
Of course, it would probably be easier to just do $2901*3 + 1 = 512*17$.
answered 2 days ago
fleablood
60.1k22575
add a comment |Â
up vote
0
down vote
up vote
0
down vote
If $3n+1 equiv 0 mod 2^k$ then it's clear that $3(n + 2^k) equiv 0 mod 2^k$ and for any $j < 2^k$ that $3(n+j) + 1not equiv 2^k$.
$n=1 implies 3n+1 equiv 0 mod 2^2$ so $3(1 + 2m) + 1 equiv 0 mod 2$.
$n=5implies 3n+1 equiv 0mod 2^4, 2^3$ so $3(5 + 8m) + 1 equiv 0 mod 8$ and $3(5+16m) + 1 equiv 0 mod 16$.
$n=5+16=21 implies 3n+1 = 64equiv 0mod 2^5, 2^6$.
Proposition: If $n = sum_j=0^k 4^k= frac 4^k+1 -13$ then
$3n+1 equiv 0 mod 2^m; m le 2k + 2$.
Pf: Is obvious: $3(frac 4^k+1 -13)+ 1 = 4^k+1$.
So to find and an $n$ so that $3n+1 equiv 0 mod 2^k$, Say $k = 10$ let $n = frac 4^lceil frac k2rceil - 13$, say $n = frac 2^10-13 = frac 1024 - 13 = 1+4+16 + 64+ 256 = 341$ so $3n + 1 =1024$.
=====
Oh, you want so say given $n = 569$ what is the highest power of $2$ that divides it.
So $n = 1 + 568$ and $568$ is divisible by $4$ so $4|3n+1$
$= 1 + 4 + 564$ if $8,16|564$ then $8,16|3n+1$ but they dont't so $4$ is the highest power of $2$ that divides $3n+1$.
A better example $341 + 5*512 = 2901$
$2901 = 1 + 2900=$
$1 + 4 + 2896$
$1 + 4 + 16 +2880=$ (and $16|2880$)
$1 + 4 + 16 + 64 + 2816 = $ (and $64|2816$)
$1 + 4 + 16 + 64 +256 + 2560 =$ (and $256|2560$)
$1 + 4 + 16 + 64 + 256 + 1024 + 1536 = $ (and $1024not mid 1548$ so we are done.)
The highest power of $2$ that divides $2901$ is the highest power of $2$ that divides $1548$ with is either $256$ or $512$. And it is $512$.
....
Of course, it would probably be easier to just do $2901*3 + 1 = 512*17$.
answered 2 days ago
fleablood
60.1k22575
If $3n+1 equiv 0 mod 2^k$ then it's clear that $3(n + 2^k) equiv 0 mod 2^k$ and for any $j < 2^k$ that $3(n+j) + 1not equiv 2^k$.
$n=1 implies 3n+1 equiv 0 mod 2^2$ so $3(1 + 2m) + 1 equiv 0 mod 2$.
$n=5implies 3n+1 equiv 0mod 2^4, 2^3$ so $3(5 + 8m) + 1 equiv 0 mod 8$ and $3(5+16m) + 1 equiv 0 mod 16$.
$n=5+16=21 implies 3n+1 = 64equiv 0mod 2^5, 2^6$.
Proposition: If $n = sum_j=0^k 4^k= frac 4^k+1 -13$ then
$3n+1 equiv 0 mod 2^m; m le 2k + 2$.
Pf: Is obvious: $3(frac 4^k+1 -13)+ 1 = 4^k+1$.
So to find and an $n$ so that $3n+1 equiv 0 mod 2^k$, Say $k = 10$ let $n = frac 4^lceil frac k2rceil - 13$, say $n = frac 2^10-13 = frac 1024 - 13 = 1+4+16 + 64+ 256 = 341$ so $3n + 1 =1024$.
=====
Oh, you want so say given $n = 569$ what is the highest power of $2$ that divides it.
So $n = 1 + 568$ and $568$ is divisible by $4$ so $4|3n+1$
$= 1 + 4 + 564$ if $8,16|564$ then $8,16|3n+1$ but they dont't so $4$ is the highest power of $2$ that divides $3n+1$.
A better example $341 + 5*512 = 2901$
$2901 = 1 + 2900=$
$1 + 4 + 2896$
$1 + 4 + 16 +2880=$ (and $16|2880$)
$1 + 4 + 16 + 64 + 2816 = $ (and $64|2816$)
$1 + 4 + 16 + 64 +256 + 2560 =$ (and $256|2560$)
$1 + 4 + 16 + 64 + 256 + 1024 + 1536 = $ (and $1024not mid 1548$ so we are done.)
The highest power of $2$ that divides $2901$ is the highest power of $2$ that divides $1548$ with is either $256$ or $512$. And it is $512$.
....
Of course, it would probably be easier to just do $2901*3 + 1 = 512*17$.
answered 2 days ago
fleablood
60.1k22575
edited 2 days ago
answered 2 days ago
fleablood
60.1k22575
answered 2 days ago
fleablood
60.1k22575
answered 2 days ago
fleablood
60.1k22575
60.1k22575
add a comment |Â
add a comment |Â
The question should be stated more clearly, at the beginning of the post if you can, and emphasized - e.g. using ">".
– Arnaud Mortier
Aug 3 at 15:47
2
What is your question?
– gammatester
Aug 3 at 15:48
"wondering if my math-notation for these functions are written correct, and also wether there are other functions like these that are simpler to find the trailing zeros."
– Natural Number Guy
Aug 3 at 16:15
Not really relevant to your question, but. If you are embarking on a quest to attack Collatz by studying the various bit patterns I want to give you the same warning I gave once already - to each putative non-trivial Collatz period there is a (usually infinitely repeating) bit pattern that matches with it.
– Jyrki Lahtonen
Aug 3 at 16:29
Jyrki Lahtonen: yes, that is true. I have builded a map (or graph) over these. Each sub-pattern can progress through to any other pattern if it finds the right path. I am studying these locally, and trying to build functions along the way (wether they turn out to be usable or not in the end).
– Natural Number Guy
Aug 3 at 16:43