A344681 a(n) is the smallest k > n such that 2^(k-n) == 1 (mod k).

1, 3, 20737, 9, 7, 25, 31, 15, 127, 17, 73, 15, 23, 33, 3479, 21, 31, 65, 131071, 51, 524287, 31, 127, 33, 47, 69, 31, 39, 49, 43, 233, 87, 1361567, 45, 89, 51, 71, 73, 223, 57, 79, 65, 13367, 51, 431, 63, 73, 69, 2351, 97, 127, 63, 103, 65, 6361, 73, 89, 63, 721, 87, 179951

Offset: 0

Author

Thomas Ordowski, Aug 17 2021

Keywords

• nonn

Comments

Smallest odd k > n such that 2^k == 2^n (mod k).

a(n) is the smallest odd k > n such that A002326((k-1)/2) divides k-n.

If a(n) is a prime p, then 2^(n-1) == 1 (mod p).

Note that a(2n+2) <= A002184(n) for n > 0.

If p is an odd prime, then a(p) <= p^2.

Links

• Michel Marcus, Table of n, a(n) for n = 0..149

Crossrefs

Cf. A002184, A002326, A346988.

Programs

Mathematica

a[0] = 1; a[n_] := Module[{k = n + 1}, While[PowerMod[2, k - n, k] != 1, k++];
k]; Array[a, 60, 0] (* Amiram Eldar, Aug 17 2021 *)

PARI

a(n) = my(k=n+1); while(Mod(2, k)^(k-n) != 1, k++); k; \\ Michel Marcus, Aug 17 2021

Python

def a(n):
    if n == 0: return 1
    k = n + 1
    while pow(2, k-n, k) != 1: k += 1
    return k
print([a(n) for n in range(61)]) # Michael S. Branicky, Aug 17 2021

Extensions

More terms from Amiram Eldar, Aug 17 2021