%I #25 Apr 11 2022 21:54:48
%S 2,769,1297,6529,7057,8017,8737,12097,12289,13297,13441,14929,15073,
%T 15361,15937,16273,18913,19441,20593,21601,21649,22273,22369,23857,
%U 25633,26017,26449,26497,27793,28513,30529,31249,34369,34849,36913,37057,37441,37633,38833,38977,39409
%N Primes in A301916 but not in A045318.
%C Is there a simpler characterization of these primes?
%C Answer from _Don Reble_, Oct 25 2018: (Start)
%C Let POT(x) be the largest power of 2 which divides x (A006519).
%C Apart from the initial 2, this sequence consists of those primes P such that
%C 2 <= POT(the order of 3 modulo P) <= POT(P-1)/8.
%C The condition "2 <=" ensures that P divides some 3^k+1, and the condition "<= POT(P-1)/8" is so that 3 has an eighth root modulo P. A062117 is the order of 3 modulo prime(n). (End)
%C Comments from Richard Bumby, Nov 12 2018: (Start)
%C When considering methods for finding square roots mod p one is led to filtering the nonzero elements by the power of 2 dividing the multiplicative order of the element. The lowest level -- elements of odd order -- have easily computed square roots, and the square roots of other elements can be found if you can discover at least one element at a higher level.
%C To say that "x^8 = 3 has no solution mod p" is to say that 3 is in one of the top three levels and that there are more than 3 levels (so that 8 divides p-1).
%C To say that primes "divide numbers of the form 3^k + 1" is to say that -1 is a power of 3 mod p, or that 3 is not at the lowest level. If there are only four levels (9 mod 16), these statements are equivalent. Otherwise, the two statements are different. An interesting case has 3 at the second level, so that (-3) has odd order allowing cube roots of unity to be found quickly.
%C I was told that Odoni had some results on finding the number of primes with k levels for which a given number (e.g., 3) is at level j, but I never tracked down a reference. If the asymptotic behavior is what one would expect, A045318 and A301916 are really far from being "almost the same", except in the trivial sense of "zero density". (End)
%D Georg Fischer, email to N. J. A. Sloane, Oct 16 2018.
%H Ray Chandler, <a href="/A320481/b320481.txt">Table of n, a(n) for n = 1..10000</a>
%t Select[Prime@Range@4200,PowerModList[3,1/8,#]!={}&&IntegerQ@MultiplicativeOrder[3,#,-1]&] (* _Giorgos Kalogeropoulos_, Feb 23 2022 *)
%Y Cf. A006519, A045317, A045318, A062117, A301916, A301917.
%K nonn
%O 1,1
%A _N. J. A. Sloane_, Oct 17 2018
%E More terms from _Michel Marcus_, Oct 17 2018