A155836 2^(2^n) mod n.

0, 0, 1, 0, 1, 4, 4, 0, 4, 6, 3, 4, 9, 2, 1, 0, 1, 16, 4, 16, 4, 16, 3, 16, 21, 16, 13, 16, 16, 16, 8, 0, 4, 18, 11, 16, 33, 16, 22, 16, 37, 16, 4, 20, 31, 6, 21, 16, 4, 16, 1, 16, 42, 52, 36, 16, 28, 54, 20, 16, 57, 16, 4, 0, 61, 16, 21, 52, 64, 16, 12, 16, 4, 16, 31, 24, 4, 16, 73, 16, 40

Offset: 1

Author

T. D. Noe, Jan 28 2009

Keywords

• nonn

Comments

From the randomness of the graph, it seems likely that every number will eventually occur. a(n)=1 for the n in A094358. When do 5 and 23 occur? The number 14 finally appears at n=34913. a(n) can be computed rapidly using two applications of the powermod function.

Examples

			a(1941491)=a(43228711)=a(75548489)=5 and a(100867561)=23. See A155886 for the first occurrence of each number. [From _T. D. Noe_, Jan 31 2009]
		

Links

• T. D. Noe, Table of n, a(n) for n = 1..10000

Crossrefs

A015910 (2^n mod n), A036236.

Programs

Mathematica

Table[e=IntegerExponent[n,2]; d=n/2^e; k=MultiplicativeOrder[2,d]; r=PowerMod[2,n,k]-e; r=Mod[r,k]; 2^e PowerMod[2,r,d], {n, 100}]
Table[PowerMod[2,2^n,n],{n,100}] (* Harvey P. Dale, Oct 16 2022 *)

PARI

a(n)=my(ph=eulerphi(n));lift(Mod(2,n)^(ph+lift(Mod(2,ph)^n))) \\ Charles R Greathouse IV, Feb 24 2012