A015910 a(n) = 2^n mod n.

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

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

Cf. A036236, A015911, A015921, A001567.

Cf. A000079, A062173, A082495.

Sequence in context: A144182 A037036 A055947 * A182256 A164993 A305572

Adjacent sequences: A015907 A015908 A015909 * A015911 A015912 A015913

Keyword

nonn

Author

Robert G. Wilson v

Status

approved