login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A036236 Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists. 68
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 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,3
COMMENTS
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.
Obviously, k > n. - Daniel Forgues, Jul 06 2015
REFERENCES
P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathematique, 28, 1980.
R. K. Guy, Unsolved Problems in Number Theory, Section F10.
LINKS
David W. Wilson, Table of n, a(n) for n = 0..1026 (from the Havermann file)
Joe K. Crump, 2^n mod n
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
FORMULA
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
EXAMPLE
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.
MATHEMATICA
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 *)
PROG
(PARI) 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
CROSSREFS
Bisections: A122182, A124977.
Sequence in context: A067481 A058433 A154998 * A235357 A260002 A368723
KEYWORD
nonn,nice
AUTHOR
EXTENSIONS
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
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)