Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #74 Sep 08 2022 08:44:40
%S 0,0,2,0,2,4,2,0,8,4,2,4,2,4,8,0,2,10,2,16,8,4,2,16,7,4,26,16,2,4,2,0,
%T 8,4,18,28,2,4,8,16,2,22,2,16,17,4,2,16,30,24,8,16,2,28,43,32,8,4,2,
%U 16,2,4,8,0,32,64,2,16,8,44,2,64,2,4,68,16,18,64,2,16,80,4,2,64
%N a(n) = 2^n mod n.
%C 2^n == 2 mod n if and only if n is a prime or a member of A001567 or of A006935. [Guy]. - _N. J. A. Sloane_, Mar 22 2012; corrected by _Thomas Ordowski_, Mar 26 2016
%C Known solutions to 2^n == 3 (mod n) are given in A050259.
%C This sequence is conjectured to include every integer k >= 0 except k = 1. A036236 includes a proof that k = 1 is not in this sequence, and n = A036236(k) solves a(n) = k for all other 0 <= k <= 1000. - _David W. Wilson_, Oct 11 2011
%C It could be argued that a(0) := 1 would make sense, e.g., thinking of "mod n" as "in Z/nZ", and/or because (anything)^0 = 1. See also A112987. - _M. F. Hasler_, Nov 09 2018
%D Richard K. Guy, Unsolved Problems in Number Theory, F10.
%H T. D. Noe, <a href="/A015910/b015910.txt">Table of n, a(n) for n=1..10000</a>
%H Albert Frank, <a href="http://www.paulcooijmans.com/oth/intcont2003.html">International Contest Of Logical Sequences</a>, 2002 - 2003. Item 4
%H Albert Frank, <a href="http://www.paulcooijmans.com/oth/intcont2003ans.html">Solutions of International Contest Of Logical Sequences</a>, 2002 - 2003.
%H Peter L. Montgomery, <a href="http://www.cs.ucla.edu/~klinger/newno.html">65-digit solution</a>.
%F a(2^k) = 0. - _Alonso del Arte_, Nov 10 2014
%F a(n) == 2^(n-phi(n)) mod n, where phi(n) = A000010(n). - _Thomas Ordowski_, Mar 26 2016
%e a(7) = 2 because 2^7 = 128 = 2 mod 7.
%e a(8) = 0 because 2^8 = 256 = 0 mod 8.
%e a(9) = 8 because 2^9 = 512 = 8 mod 9.
%p A015910 := n-> modp(2 &^ n,n) ; # _Zerinvary Lajos_, Feb 15 2008
%t Table[PowerMod[2, n, n], {n, 85}]
%o (Maxima) makelist(power_mod(2, n, n), n, 1, 84); /* _Bruno Berselli_, May 20 2011 */
%o (PARI) a(n)=lift(Mod(2,n)^n) \\ _Charles R Greathouse IV_, Jul 15 2011
%o (Haskell)
%o import Math.NumberTheory.Moduli (powerMod)
%o a015910 n = powerMod 2 n n -- _Reinhard Zumkeller_, Oct 17 2015
%o (Magma) [Modexp(2, n, n): n in [1..100]]; // _Vincenzo Librandi_, Nov 09 2018
%Y Cf. A036236, A015911, A015921, A001567.
%Y Cf. A000079, A062173, A082495.
%K nonn
%O 1,3
%A _Robert G. Wilson v_