login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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.

REFERENCES

P. Erdos 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

Hans Havermann, Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown

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

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

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

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

Bisections: A122182, A124977.

Sequence in context: A067481 A058433 A154998 * A235357 A058447 A230810

Adjacent sequences:  A036233 A036234 A036235 * A036237 A036238 A036239

KEYWORD

nonn,nice

AUTHOR

David W. Wilson

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 25 09:00 EDT 2014. Contains 244900 sequences.