My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 20th, 2013, 08:46 AM   #1
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Conjecture about primes of a special form





In other words, some primes and all composites fail the test. The first 10 integers in the sequence are 5, 11, 59, 107, 347, 587, 1019, 1307, 2027, and 2459. Is this a well-known conjecture or theory? Also, I get the feeling that this could be generalized somehow. Any thoughts on this? Counterexamples?
Sebastian Garth is offline  
 
November 20th, 2013, 08:13 PM   #2
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

I just realized something else: all of the above appear to be a subset of the safe primes!
Sebastian Garth is offline  
November 20th, 2013, 11:11 PM   #3
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Conjecture about primes of a special form

I think it's likely to be false, but the first counterexample might be large since even most primes fail these conditions. Indeed, there is no counterexample below 2^64.
CRGreathouse is offline  
November 21st, 2013, 12:09 AM   #4
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

Quote:
Originally Posted by CRGreathouse
I think it's likely to be false, but the first counterexample might be large since even most primes fail these conditions. Indeed, there is no counterexample below 2^64.
Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.
Sebastian Garth is offline  
November 21st, 2013, 10:25 AM   #5
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

Whoops, there was an error in my safe prime identification code. Having fixed it, it turns out that n=32140859 passes the SpecialPrime test but in that case (n-1)/2 is not a Sophie-Germaine, so the assumption that every value in the sequence is a safe prime is false. Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Sebastian Garth is offline  
November 21st, 2013, 10:46 AM   #6
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Conjecture about primes of a special form

Quote:
Originally Posted by Sebastian Garth
Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.
Better is to look at pseudoprimes, because any counterexample is of necessity a 2-pseudoprime congruent to 3 mod 4.
CRGreathouse is offline  
November 21st, 2013, 10:54 AM   #7
Global Moderator
 
CRGreathouse's Avatar
 
Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 937

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Conjecture about primes of a special form

Quote:
Originally Posted by Sebastian Garth
Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!
CRGreathouse is offline  
November 21st, 2013, 12:00 PM   #8
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by Sebastian Garth
Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!
Interesting. So why do you proffer that particular constant?
Sebastian Garth is offline  
November 21st, 2013, 12:16 PM   #9
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by Sebastian Garth
Yes, but what of the fact that every number in the sequence happens to be a safe prime (I've done much searching and haven't found a single one yet that wasn't)? Just seems unlikely to be a mere coincidence, from a heuristic standpoint at least (speaking of heuristics, the primitive root of a safe prime is always either 2 or -2, and in the case of the sequence in question it's always the former). Also, I wonder if the quadratic non-residues thereof have anything to do with the seemingly "picky" selection of certain safe primes? I'll look into that... Anyway, thanks for the response. You have a pretty good intuition and grasp about these sorts of matters - I know well not to take your advice lightly.
Better is to look at pseudoprimes, because any counterexample is of necessity a 2-pseudoprime congruent to 3 mod 4.
Right, good point.
Sebastian Garth is offline  
November 22nd, 2013, 02:38 PM   #10
Member
 
Joined: Jul 2010

Posts: 64
Thanks: 0

Re: Conjecture about primes of a special form

[quote=Sebastian Garth]
Quote:
Originally Posted by CRGreathouse
Quote:
Originally Posted by "Sebastian Garth":ds17ebf9
Still haven't found any composites that pass the SpecialPrime test, so the original assertion of the conjecture still stands though.
Unless you're checking above 18446744073709551616, don't bother...!
Interesting. So why do you proffer that particular constant?[/quote:ds17ebf9]

Oh, right...2^64.
Sebastian Garth is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
conjecture, form, primes, special



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Mersenne Primes and Goldbach Conjecture goodjobbro Number Theory 2 December 1st, 2013 10:38 PM
The proof of the Twin Primes conjecture Al7-8Ex5-3:Fe#!D%03 Number Theory 3 September 30th, 2013 04:52 PM
Conjecture on cycle length and primes : prime abc conjecture miket Number Theory 5 May 15th, 2013 05:35 PM
Twin primes conjecture ibougueye Number Theory 1 August 13th, 2012 08:24 PM
New conjecture about primes ? Bogauss Number Theory 32 March 1st, 2012 06:30 AM





Copyright © 2018 My Math Forum. All rights reserved.