cp's OEIS Frontend

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

%I A117658 #31 Sep 21 2023 01:45:29
%S A117658 1,2,2,3,2,4,2,5,4,4,2,6,2,4,4,9,2,8,2,6,4,4,2,10,6,4,10,6,2,8,2,17,4,
%T A117658 4,4,12,2,4,4,10,2,8,2,6,8,4,2,18,8,12,4,6,2,20,4,10,4,4,2,12,2,4,8,
%U A117658 33,4,8,2,6,4,8,2,20,2,4,12
%N A117658 Number of solutions to x^(k+1) = x^k mod n for some k >= 1.
%C A117658 If n is prime, then the solutions are x = 0, 1, and so a(n) = 2. - _Michael B. Porter_, Jul 08 2016
%C A117658 The set of solutions is independent of the choice of k. - _Michael B. Porter_, Jul 08 2016
%H A117658 Robert Israel, <a href="/A117658/b117658.txt">Table of n, a(n) for n = 1..10000</a>
%H A117658 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 A117658 a(n) = Sum_{k=1..n} floor((k^n-k^(n-1))/n)-floor((k^n-k^(n-1)-1)/n). - _Anthony Browne_, Jul 06 2016
%F A117658 Multiplicative with a(p^e) = 1 + p^(e-1) for primes p. - _Robert Israel_, Jul 06 2016
%F A117658 Dirichlet g.f.: zeta(s) * zeta(s-1) * Product_{p prime} (1 - 1/p^(s-1) + 1/p^s - 1/p^(2*s)). - _Amiram Eldar_, Sep 21 2023
%e A117658 For n = 10, using k = 1, the solutions are x = 0, 1, 5, and 6, so a(10) = 4. - _Michael B. Porter_, Jul 08 2016
%p A117658 f:= proc(n) local F,f;
%p A117658     F:= ifactors(n)[2];
%p A117658     mul(1 + f[1]^(f[2]-1), f = F)
%p A117658 end proc:
%p A117658 map(f, [$1..100]); # _Robert Israel_, Jul 06 2016
%t A117658 a[n_] := Module[{F, f}, F = FactorInteger[n]; Product[1 + f[[1]]^(f[[2]] - 1), {f, F}]]; a[1] = 1; Array[a, 100] (* _Jean-François Alcover_, Nov 05 2016, after _Robert Israel_ *)
%o A117658 (PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, 1 + f[i,1]^(f[i,2]-1));} \\ _Amiram Eldar_, Sep 21 2023
%Y A117658 Cf. A117659.
%K A117658 mult,nonn,easy
%O A117658 1,2
%A A117658 _Steven Finch_, Apr 11 2006