Problems & Puzzles:
Puzzles
Puzzle 240. Consecutive
numbers and consecutive prime factors
Here we will ask for pairs of consecutive numbers (n,
n+1) such that each is composed only by consecutive prime
factors.
As a matter of fact I have found four examples:
(384,385)
(539,540)
(2430,2431)
(4199,4200)
Example: 4199=13*17*19,
4200=2^3*3*5^2*7
Questions:
1.
Can you find the next 3 examples?
2.
Can you find a moderate large example, let's say 20 digits?
3.
Can you find a pair of these where the primes involved are not repeated in
each number?
Solution:
Jon Wharf, Adam Stinchcombe, Enoch
Haga, Faride Firoozbakht, Eric Brier and J. K. Andersen solved
Q1.
Wharf, Firoozbakht, Brier and
Andersen observed the relation of these kind of asked pairs and the
twin primes as a basis to construct a smart approach in order to get
larger examples and, consequently, solved Q2 by far.
Nobody has found an example for the
case Q3, so probably there is not any one.
***
Q1:
Here are the first pairs below 100000, as reported by several of the
solvers of this puzzle.
(35, 36)
(143, 144)
(323, 324)
(384, 385)*
(539, 540)*
(899, 900)
(2430, 2431)*
(3599, 3600)
(4199, 4200)*
(4374, 4375)**
(5183, 5184)
(11663, 11664)
(22499, 22500)
(32399, 32400)
(36863, 36864)
(57599, 57600)
(72899, 72900)
* given as examples in
this puzzle
** found by the solvers
Q2:
What is the relation on the pairs (n, n+1) and the twin primes, mentioned
above?
Let p and p+2 twin primes; so if
n=p(p+2) then n+1=(p+1)^2. From start n is a product of consecutive primes
(because p & p+2 are twin and necessarily consecutive primes), so all we
need is that p+1 (an even and composite quantity) can be factorized as a
product of consecutive primes.
While not all the known solutions are
of this type (all pairs in the list above marked with an asterisk are not
of this type), this model provides a basis in order to hunt systematically
the asked (n , n+1) pairs of large size for this puzzle
Before presenting the large solutions
gotten I would like to say that Wharf and Andersen neatly
noticed that after (4374, 4375) they are all of the 'twinprime + square'
type (Why?... See at the bottom the new questions emerging of this)
Large solutions: In order to
get large solutions you should use the twinprime + square model. In order
to guarantee that (p+1) is a product of consecutive primes you have
several options as: p=k*q# 1 or p=kq!  1, and so on, all related with
the 'minus one" primorial or factorial functions, using a k multiplier
appropriate, that is to say a multiplier k
having its largest prime factor less that q.
J. K. Andersen sent the
largest one (5138 digits)
I made my own search with PrimeForm/GW which found
and proved the 2569digit twins 2379752375*6000#+/1. 6000# is the product
of all primes below 6000, and 2379752375 = 5^3*7^2*11^2*13^2*19. The
solution n=x^21 has 5138 digits.
Others sent by Andersen (I
checked Chris Caldwell's prime database and found two large twin
primes x+/1 satisfying the requirement for x)
were:
2846!4+/1 with 2151 digits was found in 1992
by Harvey Dubner. 2846!4 is the multifactorial 2846*2842*2838*...*2
which contains all prime factors <= 1423
5775*2^5907+/1 with 1782 digits was found in
1998 by Bradford Brown with Yves Gallot's Proth.exe.
5775 = 3*5^2*7*11 which is fine for our purpose.
Faride sent the following one:
2*3*5^995*7*11*...*541*547+/1. digits=1835
Jon Wharf sent this one:
Titanic pair: ( (950*1193#)^21,
(950*1193#)^2 ). Proved 950*1193#  1 and 950*1193# + 1 with PrimeForm.
Adam Stinchcombe wrote:
I just wanted to add that I found
some 200+ digit examples:
n=2^2*3^21*5^19*7^22*11^19*13^20*17^19, n^2 215 digits
n=2^8*3^11*5^20*7^22*(11*13817)^19, n^2 218 digits
Q3. In order to get this target
you should use the twinpair + square model together with the primorial
minus one option. This is what two solvers
wrote:
Faride:
Assume n & n+1 be product of consecutive primes and
be squarefree ,since one of them is even ,thus n or n+1 must be of the
form p#.
If n be even then n=p# and n+1=p#+1 ,but for n <
163, p#+1 isn't product of consecutive primes (I checked ).
If n is odd then n+1=p# and n=p#1 ,also for n < 163
, p#1 isn't product of consecutive primes.
Thus if such n exist n must be greater than
163#2.163#2=
5766152219975951659023630035336134306565384015606066319856068808.
I think there is no such n.
Andersen:
The even number of n,n+1 must be p# for some prime
p.
Then we need p#1 or p#+1 to have consecutive
distinct prime factors. It seems unlikely to me and a computer search to
3803# with 1624 digits gave no solutions.
My search used two methods to eliminate m=p#1 or
m=p#+1:
1) Trial factoring first searched for a small
factor. If the smallest prime factor of m is found then the following
prime must also be a factor to give us a chance. This never happened.
2) If m is assumed to be the product of k
consecutive primes then the next prime after the k'th root of m must
divide m to give us a chance. This was tried for k=2,3,... until the root
became below the trial factor limit from 1). A factor of m was never
found. The gmp library was used for prp testing to find the next prime.
The prime/prp was not proved so very theoretically a factor could have
been missed.
***
Rising questions
 Is
(4374, 4375)**
the last of a finite set
of solutions NOT
of the twinpair + square type?
 Can you
give a reason for this or find more examples?
 In
particular can you find one more example as
(4199, 4200) where n=4199
is a product of
three consecutive
primes?
