login
Primes in A301916 but not in A045318.
4

%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