Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.
%I #33 Mar 24 2024 07:59:32
%S 0,1,3,27,531,1035,4635,6363,11475,19683,40131,80955,266475,280755,
%T 307395,356643,490371,544347,557955,565515,572715,808227,1256355,
%U 1695483,1959075,1995075,2771595,2837835,3004155,3208491,3337635,3886443,4670955,5619411,6434595,6942817
%N Numbers k such that k + 1 divides 3^k + 1.
%C The sequence is infinite. It contains all numbers of the form 3^(3^m).
%C After 3, the smallest term that is not a multiple of 9 is a(13) = 266475.
%C After 1, the smallest term that is not a multiple of 3 is a(36) = 6942817.
%C After 1, the smallest term that is not 3 (mod 8) is, also, a(36) = 6942817.
%C No term can be 2 (mod 3). Proof: Otherwise, k + 1 would be a multiple of 3 while 3^k + 1 would not.
%C 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.
%C 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.)
%C Empirically, approximately 80% of the terms are 27 (mod 72).
%H Zubin Mukerjee, <a href="/A370578/b370578.txt">Table of n, a(n) for n = 1..214</a>
%H Mathematics Stack Exchange, <a href="https://math.stackexchange.com/q/4867910">Why do so many solutions to n+1 | 3^n+1 satisfy n = 27 (mod 72)?</a>
%e (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.
%t Select[Range[0,7000000],TrueQ[PowerMod[3,#,#+1]==#]&] (* _James C. McMahon_, Feb 25 2024 *)
%o (Python)
%o for n in range(100_000_000):
%o if (pow(3,n,n+1)==n):
%o print(n)
%Y Cf. A006521, A006517, A007814, A015973, A055777.
%K nonn
%O 1,3
%A _Akiva Weinberger_, Feb 22 2024