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,5

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.

Links

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

Formula

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

Example

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.

Mathematica

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

Prog

(PARI) { a=0; for (n=1, 1000, a=(2*a + 1)%n; write("b064434.txt", n, " ", a); ) } \\ Harry J. Smith, Sep 13 2009
(Magma) [n le 1 select n-1 else (2*Self(n-1)+1) mod n: n in [1..80]]; // Vincenzo Librandi, Jun 24 2018
(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

Crossrefs

Cf. A064456, A079878.

Sequence in context: A280995 A092689 A281553 * A328988 A086401 A095732

Adjacent sequences: A064431 A064432 A064433 * A064435 A064436 A064437

Keyword

nonn

Author

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

Status

approved