|
|
A117658
|
|
Number of solutions to x^(k+1) = x^k mod n for some k >= 1.
|
|
2
|
|
|
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, 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, 33, 4, 8, 2, 6, 4, 8, 2, 20, 2, 4, 12
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
If n is prime, then the solutions are x = 0, 1, and so a(n) = 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
|
|
|
FORMULA
|
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
Multiplicative with a(p^e) = 1 + p^(e-1) for primes p. - Robert Israel, Jul 06 2016
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
|
|
EXAMPLE
|
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
|
|
MAPLE
|
f:= proc(n) local F, f;
F:= ifactors(n)[2];
mul(1 + f[1]^(f[2]-1), f = F)
end proc:
|
|
MATHEMATICA
|
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 *)
|
|
PROG
|
(PARI) a(n) = {my(f = factor(n)); prod(i = 1, #f~, 1 + f[i, 1]^(f[i, 2]-1)); } \\ Amiram Eldar, Sep 21 2023
|
|
CROSSREFS
|
|
|
KEYWORD
|
mult,nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|