cp's OEIS Frontend

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

%I A117659 #25 Sep 08 2020 05:50:13
%S A117659 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,
%T A117659 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,
%U A117659 36,3,6,15,36,9,18,3,12,9,18,3,40,3,6,21
%N A117659 Number of solutions to x^(k+2)=x^k mod n for some k>=1.
%C A117659 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
%C A117659 The set of solutions is independent of the choice of k. - _Michael B. Porter_, Jul 08 2016
%H A117659 Amiram Eldar, <a href="/A117659/b117659.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from Michael De Vlieger)
%H A117659 Steven R. Finch, <a href="http://arXiv.org/abs/math.NT/0605019">Idempotents and Nilpotents Modulo n</a>, arXiv:math/0605019 [math.NT], 2006-2017.
%F A117659 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
%F A117659 Multiplicative with a(2^e) = 2^e for e < 3 and 2^(e-1) + 4 for e >= 3, and a(p^e) =  p^(e-1) + 2 for p > 2. - _Amiram Eldar_, Sep 08 2020
%e A117659 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
%t A117659 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 *)
%t A117659 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 *)
%o A117659 (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
%Y A117659 Cf. A117658.
%K A117659 mult,nonn
%O A117659 1,2
%A A117659 _Steven Finch_, Apr 11 2006