

A117659


Number of solutions to x^(k+2)=x^k mod n for some k>=1.


4



1, 2, 3, 4, 3, 6, 3, 8, 5, 6, 3, 12, 3, 6, 9, 12, 3, 10, 3, 12, 9, 6, 3, 24, 7, 6, 11, 12, 3, 18, 3, 20, 9, 6, 9, 20, 3, 6, 9, 24, 3, 18, 3, 12, 15, 6, 3, 36, 9, 14, 9, 12, 3, 22, 9, 24, 9, 6, 3, 36, 3, 6, 15, 36, 9, 18, 3, 12, 9, 18, 3, 40, 3, 6, 21
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

If n is an odd prime, a(n) = 3, and the solutions are x = 0, 1, and 1. For n = 2, the solutions are the same, but a(n) = 2 since 1 and 1 are equal (mod 2).  Michael B. Porter, Jul 08 2016
The set of solutions is independent of the choice of k.  Michael B. Porter, Jul 08 2016


LINKS

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Michael De Vlieger)
Steven R. Finch, Idempotents and Nilpotents Modulo n, arXiv:math/0605019 [math.NT], 20062017.


FORMULA

a(n) = Sum_{k=1..n} floor((k^(n+2)k^n)/n)floor((k^(n+2)k^n 1)/n).  Anthony Browne, Jul 06 2016
Multiplicative with a(2^e) = 2^e for e < 3 and 2^(e1) + 4 for e >= 3, and a(p^e) = p^(e1) + 2 for p > 2.  Amiram Eldar, Sep 08 2020


EXAMPLE

For n = 10, using k = 1, the solutions are x = 0, 1, 4, 5, 6, and 9, so a(10) = 6.  Michael B. Porter, Jul 08 2016


MATHEMATICA

Table[Sum[Floor[(k^(n + 2)  k^n)/n]  Floor[(k^(n + 2)  k^n  1)/n], {k, n}], {n, 75}] (* Michael De Vlieger, Jul 07 2016 *)
f[2, e_] := If[e < 3, 2^e, 2^(e  1) + 4]; f[p_, e_] := p^(e  1) + 2; a[1] = 1; a[n_] := Times @@ f @@@ FactorInteger[n]; Array[a, 100] (* Amiram Eldar, Sep 08 2020 *)


PROG

(PARI) a(n) = sum(k=1, n, (k^(n+2)k^n)\n  (k^(n+2)k^n 1)\n); \\ Michel Marcus, Jul 07 2016


CROSSREFS

Cf. A117658.
Sequence in context: A086369 A337532 A092089 * A079065 A097272 A126630
Adjacent sequences: A117656 A117657 A117658 * A117660 A117661 A117662


KEYWORD

mult,nonn


AUTHOR

Steven Finch, Apr 11 2006


STATUS

approved



