A064434 a(n) = (2*a(n-1) + 1) mod n.

0, 1, 0, 1, 3, 1, 3, 7, 6, 3, 7, 3, 7, 1, 3, 7, 15, 13, 8, 17, 14, 7, 15, 7, 15, 5, 11, 23, 18, 7, 15, 31, 30, 27, 20, 5, 11, 23, 8, 17, 35, 29, 16, 33, 22, 45, 44, 41, 34, 19, 39, 27, 2, 5, 11, 23, 47, 37, 16, 33, 6, 13, 27, 55, 46, 27, 55, 43, 18, 37, 4, 9, 19, 39, 4, 9, 19, 39, 0

Offset: 1

Author

Jonathan Ayres (JonathanAyres(AT)btinternet.com), Oct 01 2001

Keywords

• nonn

Comments

a(n) is the remainder when (2*a(n-1) + 1) is divided by n.

Can be generalized to a(n) = f(a(n-1)) mod n, where f is any polynomial function.

Examples

			0, (0*2+1) mod 2 = 1, (1*2+1) mod 3 = 0, (0*2+1) mod 4 = 1, (1*2+1) mod 5 = 3 (3*2+1) mod 6 = 1.
		

Links

• Harry J. Smith, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A064456, A079878.

Programs

GAP

a:=[0];; for n in [2..90] do a[n]:=(2*a[n-1]+1) mod n; od; a; # Muniru A Asiru, Jun 24 2018

Magma

[n le 1 select n-1 else (2*Self(n-1)+1) mod n: n in [1..80]]; // Vincenzo Librandi, Jun 24 2018

Mathematica

nxt[{n_,a_}]:={n+1,Mod[2a+1,n+1]}; Transpose[NestList[nxt,{1,0},80]][[2]] (* Harvey P. Dale, Feb 10 2014 *)

PARI

{ a=0; for (n=1, 1000, a=(2*a + 1)%n; write("b064434.txt", n, " ", a); ) } \\ Harry J. Smith, Sep 13 2009

Formula

a(n) = (a(n-1) * 2 + 1) mod n.