%I #22 Sep 08 2020 05:51:01
%S 1,2,3,4,5,6,7,6,9,10,11,12,13,14,15,12,17,18,19,20,21,22,23,18,25,26,
%T 21,28,29,30,31,20,33,34,35,36,37,38,39,30,41,42,43,44,45,46,47,36,49,
%U 50,51,52,53,42,55,42,57,58,59,60,61,62,63,40,65,66,67,68,69,70,71,54
%N Number of solutions to x^(k+2)=x^2 mod n for some k>=1.
%H Amiram Eldar, <a href="/A117656/b117656.txt">Table of n, a(n) for n = 1..10000</a> (terms 1..1000 from Andrew Howroyd)
%H Steven R. Finch, <a href="https://arxiv.org/abs/math/0605019">Idempotents and Nilpotents Modulo n</a>, arXiv:math/0605019 [math.NT], 2006-2017.
%F Multiplicative with a(p^e) = p^floor(e/2) + (p-1)*p^(e-1) for prime p. - _Andrew Howroyd_, Jul 17 2018
%F Sum_{k=1..n} a(k) ~ c*n^2, where c = (1/2) * Product_{p prime} (1 - 1/(p^2*(p^2 + p + 1))) = 0.47717662698737204270... - _Amiram Eldar_, Sep 08 2020
%t a[n_] := Product[{p, e} = pe; p^Quotient[e, 2] + (p-1)*p^(e-1), {pe, FactorInteger[n]}]; Array[a, 72] (* _Jean-François Alcover_, Sep 13 2018, after _Andrew Howroyd_ *)
%o (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my(p=f[i,1], e=f[i,2]); p^(e\2) + (p-1)*p^(e-1))} \\ _Andrew Howroyd_, Jul 17 2018
%Y Cf. A117657, A117659.
%K mult,nonn
%O 1,2
%A _Steven Finch_, Apr 11 2006
|