OFFSET
1,3
COMMENTS
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
Known solutions to 2^n == 3 (mod n) are given in A050259.
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
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
REFERENCES
Richard K. Guy, Unsolved Problems in Number Theory, F10.
LINKS
T. D. Noe, Table of n, a(n) for n=1..10000
Albert Frank, International Contest Of Logical Sequences, 2002 - 2003. Item 4
Albert Frank, Solutions of International Contest Of Logical Sequences, 2002 - 2003.
Peter L. Montgomery, 65-digit solution.
FORMULA
a(2^k) = 0. - Alonso del Arte, Nov 10 2014
a(n) == 2^(n-phi(n)) mod n, where phi(n) = A000010(n). - Thomas Ordowski, Mar 26 2016
EXAMPLE
a(7) = 2 because 2^7 = 128 = 2 mod 7.
a(8) = 0 because 2^8 = 256 = 0 mod 8.
a(9) = 8 because 2^9 = 512 = 8 mod 9.
MAPLE
A015910 := n-> modp(2 &^ n, n) ; # Zerinvary Lajos, Feb 15 2008
MATHEMATICA
Table[PowerMod[2, n, n], {n, 85}]
PROG
(Maxima) makelist(power_mod(2, n, n), n, 1, 84); /* Bruno Berselli, May 20 2011 */
(PARI) a(n)=lift(Mod(2, n)^n) \\ Charles R Greathouse IV, Jul 15 2011
(Haskell)
import Math.NumberTheory.Moduli (powerMod)
a015910 n = powerMod 2 n n -- Reinhard Zumkeller, Oct 17 2015
(Magma) [Modexp(2, n, n): n in [1..100]]; // Vincenzo Librandi, Nov 09 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
STATUS
approved