A385989 a(n) is the least m > n such that 2^n and 2^m are congruent modulo n.

2, 3, 5, 5, 9, 8, 10, 9, 15, 14, 21, 14, 25, 17, 19, 17, 25, 24, 37, 24, 27, 32, 34, 26, 45, 38, 45, 31, 57, 34, 36, 33, 43, 42, 47, 42, 73, 56, 51, 44, 61, 48, 57, 54, 57, 57, 70, 50, 70, 70, 59, 64, 105, 72, 75, 59, 75, 86, 117, 64, 121, 67, 69, 65, 77, 76

Offset: 1

Author

Rémy Sigrist, Jul 14 2025

Keywords

• nonn

Links

• Rémy Sigrist, Table of n, a(n) for n = 1..10000

Crossrefs

See A270096 for a similar sequence.

Cf. A007733.

Programs

Mathematica

a[n_]:=Module[{m=n+1},While[PowerMod[2,n,n]!=PowerMod[2,m,n], m++]; m]; Array[a,66] (* Stefano Spezia, Jul 16 2025 *)

PARI

a(n) = { my (u = Mod(2, n)^n, v = u); for (m = n+1, oo, if (u==v*=2, return (m));); }

Formula

a(2^k) = 2^k + 1 for any k >= 0.

a(n) <= n + A007733(n).