

A015910


a(n) = 2^n mod n.


60



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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, 65digit solution.


FORMULA

a(2^k) = 0.  Alonso del Arte, Nov 10 2014
a(n) == 2^(nphi(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



