cp's OEIS Frontend

A370578 Numbers k such that k + 1 divides 3^k + 1.

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