cp's OEIS Frontend

A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.

%I A060749 #47 Jun 05 2022 04:21:23
%S A060749 1,2,2,3,3,5,2,6,7,8,2,6,7,11,3,5,6,7,10,11,12,14,2,3,10,13,14,15,5,7,
%T A060749 10,11,14,15,17,19,20,21,2,3,8,10,11,14,15,18,19,21,26,27,3,11,12,13,
%U A060749 17,21,22,24,2,5,13,15,17,18,19,20,22,24,32,35,6,7,11,12,13,15,17,19,22,24,26,28,29,30,34,35
%N A060749 Triangle in which n-th row lists all primitive roots modulo the n-th prime.
%C A060749 Row n has A008330(n) terms. - _Alford Arnold_, Aug 22 2004
%D A060749 R. Osborn, Tables of All Primitive Roots of Odd Primes Less Than 1000, Univ. Texas Press, 1961.
%H A060749 T. D. Noe, <a href="/A060749/b060749.txt">Table of n, a(n) for n = 1..9076</a> (first 100 rows)
%H A060749 C. W. Curtis, <a href="http://dx.doi.org/10.1090/S0273-0979-00-00867-3">Pioneers of Representation Theory</a>, Amer. Math. Soc., 1999; see p. 3.
%e A060749 The triangle a(n,k) begins (second column pr(n) is here prime(n)):
%e A060749 n  pr(n)\k 1  2  3  4  5  6  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27...
%e A060749 1    2     1
%e A060749 2    3     2
%e A060749 3    5     2  3
%e A060749 4    7     3  5
%e A060749 5   11     2  6  7  8
%e A060749 6   13     2  6  7 11
%e A060749 7   17     3  5  6  7 10 11 12 14
%e A060749 8   19     2  3 10 13 14 15
%e A060749 9   23     5  7 10 11 14 15 17 19 20 21
%e A060749 10  29     2  3  8 10 11 14 15 18 19 21 26 27
%e A060749 11  31     3 11 12 13 17 21 22 24
%e A060749 12  37     2  5 13 15 17 18 19 20 22 24 32 35
%e A060749 13  41     6  7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
%e A060749 14  43     3  5 12 18 19 20 26 28 29 30 33 34
%e A060749 15  47     5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45
%e A060749 16  53     2  3  5  8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
%e A060749 17  59     2  6  8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56
%e A060749 18  61     2  6  7 10 17 18 26 30 31 35 43 44 51 54 55 59
%e A060749 19  67     2  7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63
%e A060749 20  71     7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
%e A060749 ---------------------------------------------------------------------------------
%e A060749 ... reformatted and extended. - _Wolfdieter Lang_, May 18 2014
%t A060749 prQ[p_, a_] := Block[{d = Most@Divisors[p - 1]}, If[ GCD[p, a] == 1, FreeQ[ PowerMod[a, d, p], 1], False]]; f[n_] := Select[Range@n, prQ[n, # ] &]; Table[ f[Prime[n]], {n, 13}] // Flatten (* _Robert G. Wilson v_, Dec 17 2005 *)
%t A060749 primRoots[p_] := (g = PrimitiveRoot[p]; goodOddIntegers = Select[Range[1, p-1, 2], CoprimeQ[#, p-1]&]; allPrimRoots = PowerMod[g, #, p]& /@ goodOddIntegers; Sort[allPrimRoots]); primRoots /@ Prime[Range[50]] // Flatten (* _Jean-François Alcover_, Nov 12 2014, after _Peter Luschny_ *)
%t A060749 roots[n_] := PrimitiveRootList[Prime[n]]; Array[roots, 50] // Flatten (* _Jean-François Alcover_, Feb 01 2016 *)
%o A060749 {Haskell} main=print[[n|n<-[1..p-1],let h x=if x==1 then 1 else 1+h(x*n`mod`p)in h n==p-1]|p<-let p=2:[n|(n,r)<-drop 2(zip[1..](concat[replicate(2*n+1)(toInteger n)|n<-[1..]])) and[n`mod`x/=0|x<-takeWhile(<=r)p]]in p] -- Stoeber
%o A060749 (PARI) ar(n)=local(r,p,pr,j);p=prime(n);r=vector(eulerphi(p-1));pr=znprimroot(p);for(i=1,p-1,if(gcd(i,p-1)==1,r[j++]=lift(pr^i)));vecsort(r) \\ _Franklin T. Adams-Watters_, Jan 22 2012
%o A060749 (Sage)
%o A060749 def primroots(p):
%o A060749     g = primitive_root(p)
%o A060749     znorder = p - 1
%o A060749     is_coprime = lambda x: gcd(x, znorder) == 1
%o A060749     good_odd_integers = filter(is_coprime, [1..p-1, step=2])
%o A060749     all_primroots = [power_mod(g, k, p) for k in good_odd_integers]
%o A060749     all_primroots.sort()
%o A060749     return all_primroots # Minh Van Nguyen, Functional Programming for Mathematicians, Tutorial at sagemath.org
%o A060749 for p in primes(1, 50) : print(primroots(p)) # _Peter Luschny_, Jun 08 2011
%Y A060749 Diagonals give A001918, A071894.
%Y A060749 Cf. A008330, A046147.
%K A060749 nonn,tabf,nice,easy
%O A060749 1,2
%A A060749 _N. J. A. Sloane_, Apr 23 2001
%E A060749 More terms from _Alford Arnold_, Aug 22 2004
%E A060749 More terms from Paul Stoeber (pstoeber(AT)uni-potsdam.de), Oct 08 2005
%E A060749 Terms 26, 28, 29, 30, 34, 35 added; completion of row n=13. - _Wolfdieter Lang_, May 18 2014