|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
STATUS
|
approved
|
| |
|
|
