login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A320481 Primes in A301916 but not in A045318. 4
2, 769, 1297, 6529, 7057, 8017, 8737, 12097, 12289, 13297, 13441, 14929, 15073, 15361, 15937, 16273, 18913, 19441, 20593, 21601, 21649, 22273, 22369, 23857, 25633, 26017, 26449, 26497, 27793, 28513, 30529, 31249, 34369, 34849, 36913, 37057, 37441, 37633, 38833, 38977, 39409 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Is there a simpler characterization of these primes?

Answer from Don Reble, Oct 25 2018. (Start)

Let POT(x) be the largest power of 2 which divides x (A006519).

Apart from the initial 2, this sequence consists of those primes P such that

        2 <= POT(the order of 3 modulo P) <= POT(P-1)/8.

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)

Comments from Richard Bumby, Nov 12 2018 (Start):

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.

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).

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.

I was told that Odoni had some results on findin 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)

REFERENCES

Georg Fischer, email to N. J. A. Sloane, Oct 16 2018.

LINKS

Ray Chandler, Table of n, a(n) for n = 1..10000

CROSSREFS

Cf. A006519, A045317, A045318, A062117, A301916, A301917.

Sequence in context: A179960 A344663 A167448 * A078169 A226779 A243409

Adjacent sequences:  A320478 A320479 A320480 * A320482 A320483 A320484

KEYWORD

nonn

AUTHOR

N. J. A. Sloane, Oct 17 2018

EXTENSIONS

More terms from Michel Marcus, Oct 17 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 21:32 EDT 2021. Contains 346455 sequences. (Running on oeis4.)