A370578 Numbers k such that k + 1 divides 3^k + 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

Offset: 1

Author

Akiva Weinberger, Feb 22 2024

Keywords

• nonn

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

Examples

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

Links

• Zubin Mukerjee, Table of n, a(n) for n = 1..214
• Mathematics Stack Exchange, Why do so many solutions to n+1 | 3^n+1 satisfy n = 27 (mod 72)?

Crossrefs

Cf. A006521, A006517, A007814, A015973, A055777.

Programs

Mathematica

Select[Range[0,7000000],TrueQ[PowerMod[3,#,#+1]==#]&] (* James C. McMahon, Feb 25 2024 *)

Python

for n in range(100_000_000):
  if (pow(3,n,n+1)==n):
    print(n)