A368350 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.

0, -1, 1, 7, 3, 27, 43, 75, 139, 11, 779, 267, 1291, 3339, 7435, 32011, 48395, 81163, 146699, 277771, 15627, 1588491, 2637067, 539915, 4734219, 13122827, 63454475, 29900043, 231226635, 97008907, 902315275, 365444363, 1439186187, 3586669835, 7881637131

Offset: 1

Author

Yifan Xie, Dec 22 2023

Keywords

• sign

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)

Examples

			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.
		

Links

• Yifan Xie, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A006519 (2-valuation of n), A168610.

Programs

PARI

a(n) = my(t=znlog(2^n-5, Mod(3, 2^(n+1)))); if(type(t)=="t_INT", t, -1);

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)