A233521 -id:A233521 - cp's OEIS frontend

A233520 The number of distinct values of x^x (mod n) - x for x in 0 < x < n.

0, 1, 2, 2, 4, 2, 5, 4, 5, 5, 6, 4, 10, 7, 8, 9, 11, 5, 12, 9, 12, 10, 15, 9, 14, 12, 14, 12, 19, 11, 21, 19, 18, 16, 19, 12, 28, 18, 18, 18, 30, 13, 33, 20, 22, 23, 36, 18, 28, 20, 23, 27, 39, 17, 35, 24, 32, 30, 43, 20, 46, 33, 26, 37, 37, 22, 49, 34, 34, 30

Offset: 1

T. D. Noe, Feb 19 2014

nonn

According to Kurlberg et al. (who quote Crocker and Somer), for primes p, the count is between floor(sqrt((p-1)/2)) and 3p/4 + O(p^(1/2 + o(1))).

Note that the subtraction is not done mod n. - Robert Israel, Dec 17 2014

			For n = 5 the a(5) = 4 values are 1-1=0, 4-2=2, 2-3=-1, 1-4=-3. - _Robert Israel_, Dec 17 2014

T. D. Noe, Table of n, a(n) for n = 1..10000
Roger Crocker, On residues of n^n, Amer. Math. Monthly, 76 (1969), 1028-1029.
Pär Kurlberg, Florian Luca, and Igor Shparlinski, On the fixed points of the map x -> x^x modulo a prime, arXiv:1402.4464 [math.NT], 2014.
Lawrence Somer, The residues of n^n modulo p, The Fibonacci Quart., 19 (1981), 110-117.

Cf. A065295, A233518, A233519, A233521.

f:= n -> nops({seq((x &^ x mod n - x) , x = 1 .. n-1)}):
seq(f(n), n=1..100); # Robert Israel, Dec 17 2014

fs[p_] := Module[{x = Range[p - 1]}, Length[Union[PowerMod[x, x, p] - x]]]; Table[fs[n], {n, 100}]

a(n) = #Set(vector(n-1, j, lift(Mod(j, n)^j) - j)); \\ Michel Marcus, Dec 16 2014

A323424 Number of cycles (mod n) under Collatz map.

Original entry on oeis.org

1, 1, 2, 1, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 3, 3, 2, 3, 2, 4, 2, 3, 2, 3, 2, 3, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 3, 2, 3, 2, 2, 2, 3, 3, 2, 2, 3, 2, 2, 2, 4, 2, 2, 2, 3

Offset: 1

Rémy Sigrist, Jan 14 2019

nonn

This sequence is likely to be unbounded.

			The initial terms, alongside the corresponding cycles, are:
  n   a(n)  cycles
  --  ----  --------------------
   1     1  (0)
   2     1  (0)
   3     2  (0), (1)
   4     1  (0)
   5     2  (0), (1, 4, 2)
   6     2  (0), (1, 4, 2)
   7     3  (0), (1, 4, 2), (3)
   8     2  (0), (1, 4, 2)
   9     2  (0), (1, 4, 2)
  10     2  (0), (1, 4, 2)
  11     3  (0), (1, 4, 2), (5)
  12     2  (0), (1, 4, 2)
  13     3  (0), (1, 4, 2), (3, 10, 5)
  14     2  (0), (1, 4, 2)
  15     3  (0), (1, 4, 2), (7)
  16     2  (0), (1, 4, 2)
  17     2  (0), (1, 4, 2)
  18     2  (0), (1, 4, 2)
  19     3  (0), (1, 4, 2), (9)
  20     2  (0), (1, 4, 2)

Rémy Sigrist, Illustration for n = 13
Index entries for sequences related to 3x+1 (or Collatz) problem

See A000374, A023135, A023153, A233521 for similar sequences.

Cf. A006370.

a(n, f = k -> if (k%2, 3*k+1, k/2)) = { my (c=0, s=0); for (k=0, n-1, if (!bittest(s, k), my (v=0, i=k); while (1, v += 2^i; i = f(i) % n; if (bittest(s, i), break, bittest(v, i), c++; break)); s += v)); return (c) }

a(n) >= 2 for any n > 4 (as we have at least the cycles (0) and (1, 4, 2)).

cp's OEIS Frontend

A233520 The number of distinct values of x^x (mod n) - x for x in 0 < x < n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI