|
| |
|
|
A370578
|
|
Numbers k such that k + 1 divides 3^k + 1.
|
|
1
|
|
|
|
0, 1, 3, 27, 531, 1035, 4635, 6363, 11475, 19683, 40131, 80955, 266475, 280755, 307395, 356643, 490371, 544347, 557955, 565515, 572715, 808227, 1256355, 1695483, 1959075, 1995075, 2771595, 2837835, 3004155, 3208491, 3337635, 3886443, 4670955, 5619411, 6434595, 6942817
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The sequence is infinite. It contains all numbers of the form 3^(3^m).
After 3, the smallest term that is not a multiple of 9 is a(13) = 266475.
After 1, the smallest term that is not a multiple of 3 is a(36) = 6942817.
After 1, the smallest term that is not 3 (mod 8) is, also, a(36) = 6942817.
No term can be 2 (mod 3). Proof: Otherwise, k + 1 would be a multiple of 3 while 3^k + 1 would not.
All terms after 0 are odd. Proof: Suppose k is even, so that k+1 is odd. Let p be a prime factor of k+1. Then (by definition of k) 3^k == -1 (mod p) and 3^(2k) == 1 (mod p), so the order of 3 (mod p) divides 2k but not k. Thus the order of 3 is a multiple of 2^(v_2(k)+1) where v_2(k) = A007814(k) is the exponent of 2 in the prime factorization of k. But 3^(p-1) == 1 (mod p) by Fermat's little theorem, so p == 1 (mod 2^(v_2(k)+1)). Multiplying this for all prime factors p of k+1 gives k+1 == 1 (mod 2^(v_2(k)+1)), or k == 0 (mod 2^(v_2(k)+1)). But this contradicts the definition of v_2.
Apart from 0, the only possible residues mod 72 are 1, 3, 13, 25, 27, 37, 49, 51, and 61. It is conjectured that all appear eventually. (See John Omielan's answer to the author's question on Mathematics Stack Exchange.)
Empirically, approximately 80% of the terms are 27 (mod 72).
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
(3^27+1)/(27+1) is an integer, so 27 is in the sequence. This can be shown efficiently using a modular exponentiation algorithm to find 3^27 mod 28.
|
|
|
MATHEMATICA
|
Select[Range[0, 7000000], TrueQ[PowerMod[3, #, #+1]==#]&] (* James C. McMahon, Feb 25 2024 *)
|
|
|
PROG
|
(Python)
for n in range(100_000_000):
if (pow(3, n, n+1)==n):
print(n)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
