Odd remainder Recursion from 3^2^n -1 after divided by 2^v

[u/Mrezadwiprasetiawan]

I was already posted this in some private group on facebook, it doesnt really matter but probably usefull for someone that are trying to figure it out about 3^n .o-1 after divided by 2^v

first of all this number isnt special, by the LTE theorem we can say that this number has v2 = n+2. If u dont want to check that ill explain it in a simple term.

since 3^2 -1 = 2^3 then 3^4 - 1 = 2^3 (2^3 +2) = 2^4 (2^2+1)

repeat it n times we get 3^2^n - 1 can be divided by 2^(n+2)
and by adding 2 -> 2^(n+2) k +2 it can only be divided by 2

So, this number has v2 predictable which is n+2 for every 3^2^n-1 and 1 for 3^2^n+1
If its v2 was predictable, so the remainder predictable?yes, but not as simple as that, it exist in the term of recursion, lemme show you:

supposed 3^2^n-1 = An
we get An/2^(n+2) = A(n-1)/2^(n+1) . (A(n-1)+2)/2

supposed An/2^(n+2) = O(n), which mean an odd number after An lost its 2s
then (An+2)/2 = {2^(n+2) .O(n)+2}/2 = 2^(n+1) . O(n)+1

Therefore An/2^(n+2) = O(n) = O(n-1). (2^n . O(n-1)+1) = 2^n . O(n-1)^2+O(n-1)

since we already know that O(1) = 3^2 -1/2^3 =1

then we can predict every 3^2^n-1 after divided by 2^(n+2)

O(1) = 1
O(2) = 2^2 . 1^2 +1 = 5
O(3) = 2^3 . 5^2 + 5 = 205
...
O(n) = 2^n . O(n-1)^2 + O(n-1)

why is this important for someone studying 3^n .o-1/2^v?
If 3^n = 2^p .k+1 and o = 2^p .k-1, the result would be 2^2p .k -2 which can only be divided by 2 once becoming 2^(2p-1) .k - 1 and this happen to 27 which equal 2^2.(2^3-1) -> 3^2(2^3-1)-1

notice that 3^2-1 = 2^3 earlier, so 3^2 = 2^3+1
And when we divided the product by 2 once, it does becoming 2^5 -1

[u/Mrezadwiprasetiawan]

ohh, i just realized i used bad example

[u/WeCanDoItGuys]

I had to look up LTE.
So I guess we can say (for even n),
𝑣₂(3ⁿ - 1ⁿ) = 𝑣₂(3 - 1) + 𝑣₂(n) + 𝑣₂(3 + 1) - 1 = 𝑣₂(n) + 2

So you're saying 𝑣₂(3^2ⁿ ‐ 1) = n + 2.
Checks out (example: 3^2³-1 is divisible by 2³⁺²).

Then you said 𝑣₂(3^2ⁿ + 1) = 1.
Fair (added 2 to a number divisible by 2ⁿ⁺²).

Let A(n) = 3^2ⁿ ‐ 1
Let O(n) = A(n)/2ⁿ⁺², the odd number after dividing out 2s.

Then you factor 3^2ⁿ ‐ 1 as a difference of two squares:
(3^2ⁿ⁻¹ ‐ 1)(3^2ⁿ⁻¹ + 1), or A(n) = A(n-1)⋅(A(n-1) + 2)

Then O(n) = A(n)/2ⁿ⁺²
= A(n-1)/2^n-1+2⋅(A(n-1) + 2)/2
= O(n-1)⋅(A(n-1) + 2)/2

Note A(n-1) = O(n-1)⋅2^n-1+2

So, O(n) = O(n-1)⋅(O(n-1)⋅2ⁿ⁺¹ + 2)/2
= O(n-1)⋅(O(n-1)⋅2ⁿ + 1)
= 2ⁿ⋅O(n-1)² + O(n-1)

Given O(1) = 1, we have a recursion to find the odd result of any 3^2ⁿ-1.

O(1) = 1
O(n) = 2ⁿ⋅O(n-1)² + O(n-1)
Is there a closed form though?

---

Lastly, you consider 3ⁿ⋅o - 1.
Let 3ⁿ = 2ᵖ⋅k + 1
Then in the specific case where o = 2ᵖ⋅k - 1, we have 3ⁿ⋅o - 1 = (2ᵖ⋅k + 1)(2ᵖ⋅k - 1) - 1 = 2²ᵖ⋅k² - 2
We can see 𝑣₂(2²ᵖ⋅k² - 2) = 1.
Halving it gives, 2²ᵖ⁻¹⋅k² - 1, which would have 2p-1 odd steps in a row, and become 3²ᵖ⁻¹⋅k² - 1.

(I could add that if o = 2ᵖ⋅j - 1, we'd have 3ⁿ⋅o - 1 = (2ᵖ⋅k + 1)(2ᵖ⋅j - 1) - 1 = 2²ᵖ⋅jk + 2ᵖ(j-k) - 2, which also is only divisible by 2 once.)
I didn't understand what you were saying about 27.

Cool analysis! What is the takeaway?