A177023 a(n) = 2^(2*n) mod (2*n+1).

1, 1, 1, 4, 1, 1, 4, 1, 1, 4, 1, 16, 13, 1, 1, 4, 9, 1, 4, 1, 1, 31, 1, 15, 4, 1, 49, 4, 1, 1, 4, 16, 1, 4, 1, 1, 34, 9, 1, 40, 1, 16, 4, 1, 64, 4, 54, 1, 58, 1, 1, 46, 1, 1, 4, 1, 39, 22, 30, 56, 4, 91, 1, 4, 1, 64, 94, 1, 1, 4, 114, 16, 25, 1, 1, 103, 109, 1, 4, 156, 1, 16, 1, 40, 85, 1, 134

Offset: 1

Author

Nikolay Ulyanov (ulyanick(AT)gmail.com), May 01 2010

Keywords

• easy
• nonn

Comments

It is known that a(n) equals 1 when 2*n+1 is prime as a result of Fermat's little theorem. If not then a(n) equals 1 when 2*n+1 is a pseudoprime to base 2.

Examples

			a(3) = 2^(2 * 3) mod (2 * 3 + 1) = 64 mod 7 = 1.
a(4) = 2^(2 * 4) mod (2 * 4 + 1) = 256 mod 9 = 4.
a(5) = 2^(2 * 5) mod (2 * 5 + 1) = 1024 mod 11 = 1.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..20000 (first 5000 terms from Muniru A Asiru)
• Wikipedia, Fermat's little theorem

Crossrefs

Cf. A000040, A001567.

Programs

GAP

A177023 := List([1..10^3], n -> 2^(2*n) mod (2*n + 1)); # Muniru A Asiru, Jan 14 2018

Maple

seq(2&^(2*n) mod (2*n + 1), n=1..10^2); # Muniru A Asiru, Jan 14 2018

Mathematica

Table[PowerMod[2, 2n, 2n + 1], {n, 90}] (* Harvey P. Dale, May 09 2012 *)

PARI

a(n) = lift(Mod(4, 2*n+1)^n); \\ Michel Marcus, Jan 15 2018

Formula

a(n) = 2^(2*n) mod (2*n+1) or a(n) = 4^n mod (2*n+1)