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

%I #30 Apr 21 2024 18:12:47

%S 1,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,

%T 97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,

%U 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

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

%C 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

%C 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

%C These numbers were called "fermatians" by Shanks (1962). - _Amiram Eldar_, Apr 21 2024

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

%H Seiichi Manyama, <a href="/A176997/b176997.txt">Table of n, a(n) for n = 1..10000</a>

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

%t m = 1; Join[Select[Range[m], Divisible[2^(# - 1) - m, #] &],

%t Select[Range[m + 1, 10^3], PowerMod[2, # - 1, #] == m &]] (* _Robert Price_, Oct 12 2018 *)

%o (PARI) isok(n) = Mod(2, n)^(n-1) == 1; \\ _Michel Marcus_, Sep 23 2016

%o (Python)

%o from itertools import count, islice

%o def A176997_gen(startvalue=1): # generator of terms >= startvalue

%o if startvalue <= 1:

%o yield 1

%o k = 1<<(s:=max(startvalue,1))-1

%o for n in count(s):

%o if k % n == 1:

%o yield n

%o k <<= 1

%o A176997_list = list(islice(A176997_gen(),30)) # _Chai Wah Wu_, Jun 30 2022

%Y The odd terms of A015919.

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

%Y Cf. A000079, A062173, A062175, A176817.

%K nonn

%O 1,2

%A _Juri-Stepan Gerasimov_, Dec 08 2010

%E Edited by _Max Alekseyev_, Sep 22 2016