A176997 Integers k such that 2^(k-1) == 1 (mod k).

1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331

Offset

1,2

Comments

Old definition was: Odd integers n such that 2^(n-1) == 4^(n-1) == 8^(n-1) == ... == k^(n-1) (mod n), where k = A062383(n). Dividing 2^(n-1) == 4^(n-1) (mod n) by 2^(n-1), we get 1 == 2^(n-1) (mod n), implying the current definition. - Max Alekseyev, Sep 22 2016

The union of {1}, the odd primes, and the Fermat pseudoprimes, i.e., {1} U A065091 U A001567. Also, the union of A006005 and A001567 (conjectured by Alois P. Heinz, Dec 10 2010). - Max Alekseyev, Sep 22 2016

These numbers were called "fermatians" by Shanks (1962). - Amiram Eldar, Apr 21 2024

References

Daniel Shanks, Solved and Unsolved Problems in Number Theory, Spartan Books, Washington D.C., 1962.

Links

Seiichi Manyama, Table of n, a(n) for n = 1..10000

Example

5 is in the sequence because 2^(5-1) == 4^(5-1) == 8^(5-1) == 1 (mod 5).

Mathematica

m = 1; Join[Select[Range[m], Divisible[2^(# - 1) - m, #] &],
Select[Range[m + 1, 10^3], PowerMod[2, # - 1, #] == m &]] (* Robert Price, Oct 12 2018 *)

Prog

(PARI) isok(n) = Mod(2, n)^(n-1) == 1; \\ Michel Marcus, Sep 23 2016
(Python)
from itertools import count, islice
def A176997_gen(startvalue=1): # generator of terms >= startvalue
    if startvalue <= 1:
        yield 1
    k = 1<<(s:=max(startvalue, 1))-1
    for n in count(s):
        if k % n == 1:
            yield n
        k <<= 1
A176997_list = list(islice(A176997_gen(), 30)) # Chai Wah Wu, Jun 30 2022

Crossrefs

The odd terms of A015919.

Odd integers n such that 2^n == 2^k (mod n): this sequence (k=1), A173572 (k=2), A276967 (k=3), A033984 (k=4), A276968 (k=5), A215610 (k=6), A276969 (k=7), A215611 (k=8), A276970 (k=9), A215612 (k=10), A276971 (k=11), A215613 (k=12).

Cf. A000079, A062173, A062175, A176817.

Sequence in context: A006005 A065091 A160656 * A240699 A065380 A211075

Adjacent sequences: A176994 A176995 A176996 * A176998 A176999 A177000

Keyword

nonn,changed

Author

Juri-Stepan Gerasimov, Dec 08 2010

Extensions

Edited by Max Alekseyev, Sep 22 2016

Status

approved