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,1

Links

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

Formula

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

a(n) = n + A007733(n). - Chai Wah Wu, Jul 17 2025

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

Prog

(PARI) a(n) = { my (u = Mod(2, n)^n, v = u); for (m = n+1, oo, if (u==v*=2, return (m)); ); }
(Python)
from sympy import n_order
def A385989(n): return n+n_order(2, n>>(~n & n-1).bit_length()) # Chai Wah Wu, Sep 16 2025

Crossrefs

See A270096 for a similar sequence.

Cf. A007733.

Sequence in context: A096736 A128188 A318636 * A366975 A267582 A360072

Adjacent sequences: A385986 A385987 A385988 * A385990 A385991 A385992

Keyword

nonn

Author

Rémy Sigrist, Jul 14 2025

Status

approved