A015948 -id:A015948 - cp's OEIS frontend

1, 0, 3, 4700063497, 6, 19147, 10669, 25, 9, 2228071, 18, 262279, 3763, 95, 1010, 481, 20, 45, 35, 2873, 2951, 3175999, 42, 555, 50, 95921, 27, 174934013, 36, 777, 49, 140039, 56, 2463240427, 110, 477, 697, 91, 578, 623, 156, 2453, 540923, 55, 70, 345119, 287

Offset: 0

David W. Wilson

a(1) = 0, that is, no n exists with 2^n mod n = 1. Proof: Assume that there exists such n > 1. Consider its smallest prime divisor p. Then 2^n == 1 (mod p) implying that the multiplicative order ord_p(2) divides n. However, since ord_p(2) < p and p is the smallest divisor of n, we have ord_p(2) = 1, that is, p divides 2^1 - 1 = 1 which is impossible. - Max Alekseyev
_Labos Elemer_ asked on Sep 27 2001 if all numbers > 1 eventually appear in A015910, that is, if a(n) > 0 for n > 1.
Ron Graham's conjecture from 1960 states that for any n > 1 there are infinitely many solutions to 2^k mod k = n. - Max Alekseyev, Oct 19 2024
Obviously k > n. - Daniel Forgues, Jul 06 2015

			n = 0: 2^1 mod 1 = 0, a(0) = 1;
n = 1: 2^k mod k = 1, no such k exists, so a(1) = 0;
n = 2: 2^3 mod 3 = 2, a(2) = 3;
n = 3: 2^4700063497 mod 4700063497 = 3, a(3) = 4700063497.

P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathématique, 28, 1980.
R. K. Guy, Unsolved Problems in Number Theory, Section F10.

David W. Wilson, Table of n, a(n) for n = 0..1026 (from the Havermann file)
Joe K. Crump, 2^n mod n
Hans Havermann, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown
Nick Hobson, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown. [With 101 new terms and 2 corrections, this supersedes the earlier table from Hans Havermann. The corrections are to terms a(799) and a(881), where smaller values of k were found.]
Nick Hobson, C program
Eric Weisstein's World of Mathematics, 2

Cf. A015910, A015948, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821.

Bisections: A122182, A124977.

a = Table[0, {75} ]; Do[ b = PowerMod[2, n, n]; If[b < 76 && a[[b]] == 0, a[[b]] = n], {n, 1, 5*10^9} ]; a
(* Second program: *)
t = Table[0, {1000} ]; k = 1; While[ k < 6500000000, b = PowerMod[2, k, k]; If[b < 1001 && t[[b]] == 0, t[[b]] = k]; k++ ]; t
nk[n_] := Module[ {k}, k = 1; While[PowerMod[2, k, k] != n, k++]; k]
Join[{1, 0}, Table[nk[i], {i, 2, 46}]]  (* Robert Price, Oct 11 2018 *)

a(n)=if(n==1,return(0));my(k=n);while(lift(Mod(2,k)^k)!=n,k++);k \\ Charles R Greathouse IV, Oct 12 2011

It's obvious that for each k, a(k) > k and we can easily prove that 2^(3^n) = 3^n-1 (mod 3^n). So 3^n is the least k with 2^k mod k = 3^n-1. Hence for each n, a(3^n-1) = 3^n. - Farideh Firoozbakht, Nov 14 2006

a(3) was first computed by the Lehmers.
More terms from Joe K. Crump (joecr(AT)carolina.rr.com), Sep 04 2000
a(69) = 887817490061261 = 29 * 37 * 12967 * 63809371. - Hagen von Eitzen, Jul 26 2009
Edited by Max Alekseyev, Jul 29 2011

cp's OEIS Frontend

A036237 Duplicate of A015948.

Views

Author

Keywords

A036236 Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions