A332965 a(n) is the number of distinct values in the sequence s defined by s(1) = 0 and for any k > 0, s(k+1) = (s(k)^2+1) mod n.

1, 2, 3, 3, 3, 4, 4, 4, 5, 6, 6, 4, 4, 5, 5, 5, 8, 8, 6, 7, 4, 6, 8, 4, 4, 4, 5, 5, 11, 8, 5, 5, 6, 8, 6, 8, 6, 7, 6, 8, 7, 5, 8, 6, 5, 8, 14, 5, 9, 7, 8, 5, 9, 8, 10, 5, 6, 11, 11, 8, 15, 6, 6, 6, 12, 6, 12, 8, 8, 9, 18, 8, 9, 7, 5, 7, 6, 6, 8, 9, 11, 14, 11

Offset

1,2

Comments

For any n > 0, the sequence s is eventually periodic, so this sequence is well defined.

a(n) tends to infinity as n tends to infinity.

Links

Rémy Sigrist, Table of n, a(n) for n = 1..10000

Formula

a(n) > k for any k >= 0 and n > A003095(k).

Example

For n = 42:
- we have:
  k  s(k)
  -  ----
  1     1
  2     2
  3     5
  4    26
  5     5
  6    26
  ...
- the sequence s has 4 distinct values, so a(42) = 4.

Prog

(PARI) a(n) = { my (s=0, v=0, w=0); while (!bittest(w, s), w+=2^s; v++; s=(s^2+1)%n); v }

Crossrefs

Cf. A003095, A332966.

Sequence in context: A348385 A080405 A039728 * A354779 A334220 A234016

Adjacent sequences: A332962 A332963 A332964 * A332966 A332967 A332968

Keyword

nonn

Author

Rémy Sigrist, Mar 04 2020

Status

approved