OFFSET
1,4
COMMENTS
a(n) is the least nonnegative integer k such that 3^k == 2^n-5 (mod 2^(n+1)), or -1 if no such number exists.
Theorem: For n >= 3, a(n+1) is the remainder of a(n) + 2^(n-1) +- 2^(n-2) modulo 2^n.
Proof: (Start)
We first prove that the 2-valuation of 3^(2^(k - 2)) - 1 is k for k >= 3. Using mathematical induction we can know that 3^(2^i) = 1 + 2^(i + 2)*u(i), where u(i)'s are odd positive integers, thus the theorem is the case where i = k - 2.
Then we prove the original theorem. Suppose that 3^a(n) = x*2^(n + 1) + 2^n - 5. Using the theorem proved before, we have 3^(2^(n-2)) = y*2^(n + 1) + 2^n + 1, where x and y are no negative integers. Therefore, 3^(a(n) + 2^(n - 2)) == (x - y)*2^(n + 1) - 5 (mod 2^(n + 2)), 3^(a(n) + 3*2^(n - 2)) == (x - y + 1)*2^(n + 1) - 5 (mod 2^(n + 2)). Since there must be an odd number between x - y and x - y + 1, suppose that 3^(a(n) + 2^(n-1) +- 2^(n-2)) == 2^(n + 1) - 5 (mod 2^(n + 2)). Since the multiplicative order of 3 mod 2^(n + 2) is 2^n, a(n + 1) is the remainder of a(n) + 2^(n-1) +- 2^(n-2) modulo 2^n. (End)
LINKS
Yifan Xie, Table of n, a(n) for n = 1..1000
FORMULA
a(n) < 2^(n-1).
a(n+1) = a(n) + 3*2^(n-2) or a(n) - 2^(n-2) if a(n) > 2^(n-2);
a(n+1) = a(n) + 3*2^(n-2) or a(n) + 2^(n-2) if a(n) < 2^(n-2). (See COMMENTS for proof)
EXAMPLE
a(2) = -1 because if 3^n+5 is divisible by 2^2, n must be odd, so 3^n+5 is divisible by 2^3.
a(10) = 11 because the 2-valuation of 3^11+5 is 10, and it's easy to verify that it is the least one.
Since a(13) = 1291 < 2^11, a(14) = 1291 + 2^12 +- 2^11. Then we can verify that the former is correct, thus a(14) = 3339.
PROG
(PARI) a(n) = my(t=znlog(2^n-5, Mod(3, 2^(n+1)))); if(type(t)=="t_INT", t, -1);
CROSSREFS
KEYWORD
sign
AUTHOR
Yifan Xie, Dec 22 2023
STATUS
approved