|
%I #32 Apr 21 2024 19:17:20
%S 1,0,1,1,2,3,7,3,6,10,7,6,11,10,13,13,16,11,13,15,16,16,23,28,21,24,
%T 20,29,16,32,19,31,41,27,46,22,29,29,56,52,50,27,51,46,57,35,24,45,60,
%U 42,68,63,45,56,74,85,75,58,59,69,53,86,68,79,57,94,54,71,103,64,109,117,76
%N The number of primitive roots g such that there exists an x with g^x == x (mod p), where p=prime(n).
%C a(n) is the number of primitive roots g of p=prime(n) for which an x with 0 < x < p exists such that g^x == x (mod p). - _Robert Israel_, May 12 2017 [Corrected by _Tim Peters_ (following an observation made by _José Hernández_), Apr 16 2024]
%C The number x is called a fixed point of the discrete logarithm with base g.
%H Robert Israel, <a href="/A174407/b174407.txt">Table of n, a(n) for n = 1..1000</a>
%H M. Levin, C. Pomerance, and K. Soundararajan, <a href="https://doi.org/10.1007/978-3-642-14518-6_5">Fixed Points for Discrete Logarithms</a>. In: G. Hanrot, F. Morain, and E. Thomé (eds), Algorithmic Number Theory. ANTS 2010. Lecture Notes in Computer Science, vol 6197. Springer, Berlin, Heidelberg (2010).
%H Math Overflow, <a href="https://mathoverflow.net/q/269368">Fixed points of g^x (modulo a prime)</a>.
%p g:= proc(n) local p, r, S, R,x;
%p p:= ithprime(n);
%p r:= numtheory:-primroot(p);
%p S:= select(t -> igcd(t,p-1) = 1, {$1..p-1});
%p R:= map(s -> r &^ s mod p, S);
%p for x from 2 to p-2 do
%p R:= remove(t -> (t &^ x - x mod p = 0), R);
%p od;
%p numtheory:-phi(p-1)-nops(R);
%p end proc:
%p g(1):= 1:
%p map(g, [$1..100]); # _Robert Israel_, May 12 2017
%t Table[p = Prime[n]; Length[Select[PrimitiveRootList[p], MemberQ[PowerMod[#, Range[p-1], p] - Range[p-1], 0]&]], {n, 1, 100}] (* updated by _Jean-François Alcover_, Oct 11 2020 *)
%o (PARI) apply( {A174407(n, p=prime(n), s=0)=for(r=1,p-1, my(g=Mod(r,p)); if(znorder(g)==p-1, for(x=1, p-1, g^x==x && s++ && next(2))));s}, [1..99]) \\ quite inefficient code, for illustration. - _M. F. Hasler_, Apr 15 2024
%Y Cf. A174329 and A174330 (least g and x for each p).
%K nonn,changed
%O 1,5
%A _T. D. Noe_, Mar 18 2010
%E Definition edited, and a(1) and a(2) inserted, by _Robert Israel_, May 12 2017
|
