%I #52 Dec 31 2023 03:42:40
%S 0,-1,1,7,3,27,43,75,139,11,779,267,1291,3339,7435,32011,48395,81163,
%T 146699,277771,15627,1588491,2637067,539915,4734219,13122827,63454475,
%U 29900043,231226635,97008907,902315275,365444363,1439186187,3586669835,7881637131
%N a(n) is the least nonnegative integer k such that the 2-valuation of 3^k+5 is n, or -1 if no such number exists.
%C 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.
%C Theorem: For n >= 3, a(n+1) is the remainder of a(n) + 2^(n-1) +- 2^(n-2) modulo 2^n.
%C Proof: (Start)
%C 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.
%C 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)
%H Yifan Xie, <a href="/A368350/b368350.txt">Table of n, a(n) for n = 1..1000</a>
%F a(n) < 2^(n-1).
%F a(n+1) = a(n) + 3*2^(n-2) or a(n) - 2^(n-2) if a(n) > 2^(n-2);
%F 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)
%e 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.
%e 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.
%e 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.
%o (PARI) a(n) = my(t=znlog(2^n-5, Mod(3, 2^(n+1)))); if(type(t)=="t_INT", t, -1);
%Y Cf. A006519 (2-valuation of n), A168610.
%K sign
%O 1,4
%A _Yifan Xie_, Dec 22 2023
|