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

Author

Robert G. Wilson v

Keywords

• nonn

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

Examples

			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.
		

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.

Crossrefs

Cf. A036236, A015911, A015921, A001567.

Cf. A000079, A062173, A082495.

Programs

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

Maple

A015910 := n-> modp(2 &^ n,n) ; # Zerinvary Lajos, Feb 15 2008

Mathematica

Table[PowerMod[2, n, n], {n, 85}]

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

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