Prime chains x-->Ax+B
- I wanted long chains of primes of the following kind.
Want P to be prime. Want Q=4P+1 to be prime. And continue:
R=4Q+1 prime, S=4R+1 prime, etc.
I also was interested in the same thing but with -1's instead of +1's.
+chainlength=3: 3, 13, 53
-chainlength=3: 3, 11, 43
But: There are no other 3-long-chains if the initial P is among the first 2000 primes.
This led me to prove the following easy once you see it THEOREM:
The above two examples are the unique 3-long 4x+1 and 4x-1
chains. There are no others.
f(x)=4x+1 always leads to a multiple of 3 after at most 2 iterations
(and ditto for 4x-1); this is seen by working mod 3; and this prevents 3 primes
in a chain unless one of the primes actually IS 3.
Similar proofs show that x-->Ax+B prime-chains are bounded in length
under various conditions:
* if B=0 then obviously not even 1 step is possible
* if B and A have a common divisor then obviously not even 1 step is possible
* if A and B have same parity then obviously not even 1 step is possible
starting from an odd prime
* otherwise if gcd(B,A-1)=1 then the linear congruential sequence generator
x-->Ax+B (mod M) will be full period M for any prime M dividing A-1
hence the chain length cannot be longer than M primes in a row...
THEOREM: the only possible unboundedly long x-->Ax+B prime chains must
have B a multiple of every prime divisor of A-1,
and B nonzero, gcd(A,B)=1, and the parities of A,B must differ.
For example 2x+1, 2x-1, 3x+2, 3x+4, 3x-2, 4x+3, and 4x-3:
Fairly long chains of these sorts:
2x+1: start with 89, get 6 primes.
2x-1: start with 1531 or 6841, get 5 primes. With 16651 get 7 primes.
3x+2: start with 1129, get 5 primes; or 10009, get 6 primes.
3x+4: start with 3203, get 5 primes.
3x-2: start with 61 or 761, get 5 primes.
4x+3: start with 17231, get 8 primes.
4x-3: start with 523, get 6 primes; start with 5869 to get 7 primes.
5x+2: start with 373 or 1171, get 5 primes.
5x+4: start with 263 or 1217, get 5 primes; with 5333 get 7 primes.
5x-2: start with 1229 to get 5 primes; or 4337 to get 8 primes.
5x-4: start with 367 or 463 to get 5 primes.
One might CONJECTURE that the necessary conditions of the theorem also
suffice. It would be better to make such a conjecture after getting rather more
numerical evidence than this, though.
Warren D. Smith
http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
- --- In email@example.com,
Kevin Acres <research@...> wrote:
> x=a*x+b either is a square or has a square as a major factor.Suppose that we want to start with a square and get a square.
Then we must solve the Diophantine equation
y^2 = a*x^2 + b
For any pair (a,b), Dario will tell us all the solutions: