|
%I #85 Feb 05 2024 11:25:36
%S 1,0,3,4700063497,6,19147,10669,25,9,2228071,18,262279,3763,95,1010,
%T 481,20,45,35,2873,2951,3175999,42,555,50,95921,27,174934013,36,777,
%U 49,140039,56,2463240427,110,477,697,91,578,623,156,2453,540923,55,70,345119,287
%N Least inverse of A015910: smallest integer k > 0 such that 2^k mod k = n, or 0 if no such k exists.
%C 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_
%C _Labos Elemer_ asked on Sep 27 2001 if all numbers > 1 eventually appear in A015910, that is, if a(n) > 0 for n > 1.
%C Obviously, k > n. - _Daniel Forgues_, Jul 06 2015
%D P. Erdős and R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de L'Enseignement Mathematique, 28, 1980.
%D R. K. Guy, Unsolved Problems in Number Theory, Section F10.
%H David W. Wilson, <a href="/A036236/b036236.txt">Table of n, a(n) for n = 0..1026</a> (from the Havermann file)
%H Joe K. Crump, <a href="http://web.archive.org/web/20070614175509/http://www.immortaltheory.com/NumberTheory/2nmodn.htm">2^n mod n</a>
%H Hans Havermann, <a href="/A036236/a036236.txt">Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown</a>
%H Nick Hobson, <a href="/A036236/a036236.log.txt">Table of n, a(n) for n = 1..10000 with -1 for those entries where a(n) is unknown.</a> [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.]
%H Nick Hobson, <a href="/A036236/a036236.c.txt">C program</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/2.html">2</a>
%F 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
%e n = 0: 2^1 mod 1 = 0, a(0) = 1;
%e n = 1: 2^k mod k = 1, no such k exists, so a(1) = 0;
%e n = 2: 2^3 mod 3 = 2, a(2) = 3;
%e n = 3: 2^4700063497 mod 4700063497 = 3, a(3) = 4700063497.
%t 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 (* Second program: *)
%t 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
%t nk[n_] := Module[ {k}, k = 1; While[PowerMod[2, k, k] != n, k++]; k]
%t Join[{1, 0}, Table[nk[i], {i, 2, 46}]] (* _Robert Price_, Oct 11 2018 *)
%o (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
%Y Cf. A015910, A015948, A078457, A119678, A119679, A127816, A119715, A119714, A127817, A127818, A127819, A127820, A127821.
%Y Bisections: A122182, A124977.
%K nonn,nice
%O 0,3
%A _David W. Wilson_
%E a(3) was first computed by the Lehmers.
%E More terms from Joe K. Crump (joecr(AT)carolina.rr.com), Sep 04 2000
%E a(69) = 887817490061261 = 29 * 37 * 12967 * 63809371. - _Hagen von Eitzen_, Jul 26 2009
%E Edited by _Max Alekseyev_, Jul 29 2011
|
