login
A015910
a(n) = 2^n mod n.
65
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, 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, 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
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
Albert Frank, International Contest Of Logical Sequences, 2002 - 2003. Item 4
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
STATUS
approved