Problems & Puzzles:
Better than 210
JM Bergot sent the following nice puzzle.
Take all nontrivial divisors for 210 and
form pairs such at each pair gives the product 210. The following pairs
added sum up to a prime
5+42 = 47
Q. Is there a number giving more than
seven such pairs?
Contributions came from: Jan van Delden, Torbjörn Alm,
Seiji Tomita, Luis Rodríguez, Farideh Firoozbakht, T. D. Noe, Carlos Rivera,
Fred Schalekamp& Fred Schneider.
First of all, I should say this puzzle was spoiled by the
elimination of the "trivial divisors" of n (1 & n). Letting them go inside &
due to the fact that 1+210 = prime, immediately arises a more powerful
Find a number n better than 210, such that for all
divisors d of n, d+n/d is prime.
It is not hard to see that this kind of numbers must be
even & free of square prime factors. And the quantity of prime sums are
2^(k-1) where k is the # of prime factors.
So, this is not only a better question but a harder too.
2, 6, 30 & 210 are those type of numbers, and the earliest
having 1, 2, 3 & 4 prime factors
The earliest having 5 prime factors is 186162 (and only 6
more cases are known: 899970, 1624462, 3047410 , 603843882, 3162524682 &
14581858930). The largest case was found only by Farideh Firoozbakht.
Up today no one single example having 6
prime factors & 32 prime sums is known
So the current challenge is this one:
Find the next smallest number having
2^(k-1) prime sums d+n/d for all divisors d of n, for k=1, 2, ... : 2, 6,
30, 210, 186162, ?
n as the product of 2 and k distinct primes. We can split n in 2^k-1
distinct ways as a product of an even number and a product of
primes. And in 2^k ways if we allow the split (1,n), which by the
way would lead to another solution 1+210=211 in the example
given. Not all these partitions will lead to a prime sum. But if
they do the maximum number would be 2^k (for simplicity).
If n is a general even number, products of 2 and
other primes (not all distinct), the number of splits are less
compared to the situation above, due to the primes with multiplicity
greater than 1.
So maybe a good way to measure the number of splits
log(# distinct sums prime)/ (log(2)* #prime factors
(besides 2), counted with multiplicity)
The maximum is 1, and is achieved by 2, 6, 30, 210
(if one allows the split (1,n)) and probably a whole bunch of other
numbers (for instance 10, 22, 42)
Torbjörn Alm & Seiji Tomita wrote more or less the
The first solution > 7 pairs is:
Factor count: 32
1 2 3 6 13 23 26 37 39 46 69 74 78 111 138 222 299 481 598 851 897 962
1443 1702 1794 2553 2886 5106 11063 22126 33189 66378
There are 4 more such solutions < 5000000, all with 32 factors ant 15
combinations. N+1 is prime.
Any primorial serves to construct a great deal of
with the sum of its two factors. This is a list:
Primorial Number of primes
7# = 210 7
11# = 2310 11
13# = 30030 21
17# = 510510 40
19# = 9699690 70
Note that for 210 we also have 1+210 is prime so
for each divisor d of 210 we have d+n/d is prime.
All such numbers are squarefree because if p^2
divides such number n then p divides p+n/p so it can't be prime.
Hence if n is a such number then number of divisors of n is of the
Smallest such numbers n for k = 1, 2, 3, 4 & 5 are
respectively 2, 6, 30, 210 & 186162. So for 186162 we get 16
primes, namely if d divides 186162 then d+186162/d is prime.
Next term of this sequence is greater than 2*10^10
I didn't find a number with 32 corresponding primes
But Next term of the sequence, 186162, 899970,
3047410, 603843982, 3162524682 , ... is 14581858930.
Tony D Noe wrote:
Instead of nontrivial divisors, it seems more natural
to include all the
divisors of a number. Then for 210 we obtain one additional prime: 1 +
Let a(n) be the number of distinct primes of the form d + n/d, where d
divisor of n. Then it is easy to see that for n > 1, we have a(n) > 0
if n is even. This function a(n) has been studied by several authors.
See sequence http://oeis.org/classic/A088627 for
a(2n). Mattias Engelhardt
has calculated this function for n up to 10^6. In sequence
http://oeis.org/classic/A091350 he tabulates the smallest k
such that a(k)
= n for n up to 29. I have extended the sequence up to n=90.
Let p# denote the primorial of p: p# = 2*3*5*7*11*...*p. Then a(p#)
appears to be an increasing function. The sequence a(prime(n)#) is
tabulated by Lei Zhou in http://oeis.org/classic/A103787.
In sequence http://oeis.org/classic/A080715 Matthew
interested in finding n such that d + n/d is prime for every divisor d
n. In this case, n must be an even number that is the product of
primes. It is easy to find n that are the product of 2, 3, or 4 primes.
In fact, 210 is the smallest example consisting of 4 primes. The first
consisting of 5 primes is 186162 = 2*3*19*23*71, which produces 16
of the form d + n/d. An interesting question is whether there are
n with a greater number of prime factors.
Kok Seng Chua has studied this question and posted his results as
http://oeis.org/classic/A128278, and http://oeis.org/classic/A128279.
correctly states that the prime k-tuple conjecture implies that r primes
can be found to produce 2^(r-1) primes of the form d + n/d. Let me
how this works for finding an n that is the product of r=6 primes.
The first 5 primes must be 2 and any four distinct odd primes. Let's
2,3,5,7,11. Let the sixth prime be p. So n=2*3*5*7*11*p. We form all
possible values of d + n/d for divisors d of n, obtaining the following
1 + 2310p, 2 + 1155p, 3 + 770p, 5 + 462p, 7 + 330p, 11 + 210p,
6 + 385p, 10 + 231p, 14 + 165p, 22 + 105p, 15 + 154p,
21 + 110p, 33 + 70p, 35 + 66p, 55 + 42p, 77 + 30p, 30 + 77p,
42 + 55p, 66 + 35p, 70 + 33p, 110 + 21p, 154 + 15p, 105 + 22p,
165 + 14p, 231 + 10p, 385 + 6p, 210 + 11p, 330 + 7p, 462 + 5p,
770 + 3p, 1155 + 2p, 2310 + p
(Because we also require p to be prime, there are actually 33
This is exactly the form that the prime k-tuple conjecture requires. If
the conjecture is true, then a prime p exists. The conjecture also
an estimate of the number of primes p < x that make the 33 linear
polynomials prime: C*x/(log x)^33 for some constant C. This implies
it could take a long time to find a solution to the 6-prime case.
Carlos Rivera wrote:
In the search for the smallest numbers having 32 prime
sums, my best shot was 95881258 = 2*11*17*19*103*131 which has 27/32
Fred Schalekamp wrote:
After 5 minutes I found for 2310 (=2*3*5*7*11): 11
prime sums...By testing 30030 = (2*3*5*7*11*13) I found 21 prime sums...
for 9699690 = 2*3*5*7*11*13*17*19 gives 70 prime sums.
Fred Schneider wrote:
I picked primorials (r=primorial(p)) because d + r/d
is clearly always
p unsmooth. You could I suppose use any squarefree number as d and
n/d are still always relatively prime.
At pIndex=4, primorial=210, primeCount=8.
At pIndex=5, primorial=2310, primeCount=11.
At pIndex=6, primorial=30030, primeCount=21.
At pIndex=7, primorial=510510, primeCount=41.
At pIndex=8, primorial=9699690, primeCount=71.
At pIndex=9, primorial=223092870, primeCount=118.
At pIndex=10, primorial=6469693230, primeCount=263.
At pIndex=11, primorial=200560490130, primeCount=449.
At pIndex=12, primorial=7420738134810, primeCount=703.
At pIndex=13, primorial=304250263527210, primeCount=1385.
At pIndex=14, primorial=13082761331670030, primeCount=2423.
At pIndex=15, primorial=614889782588491410, primeCount=5502.
At pIndex=16, primorial=32589158477190044730, primeCount=8617.
At pIndex=17, primorial=1922760350154212639070, primeCount=18250.
At pIndex=18, primorial=117288381359406970983270, primeCount=29353.
At pIndex=19, primorial=7858321551080267055879090, primeCount=61970.
At pIndex=20, primorial=557940830126698960967415390, primeCount=103568.
At pIndex=21, primorial=40729680599249024150621323470, primeCount=209309.
At pIndex=22, primorial=3217644767340672907899084554130,
At pIndex=23, primorial=267064515689275851355624017992790,
At pIndex=24, primorial=23768741896345550770650537601358310,
At pIndex=25, primorial=2305567963945518424753102147331756070,
A quick search yields 331170 has 29/32 prime.
Emmanuel Vantieghem wrote:
I found eigth numbers m with more than 16
divisors that have the property that for every divisor d of m,
the sum d+m/d is prime :
186162 , 899970, 3047410 , 603843982, 1798687522,
3162524682, 14581858930 and 24204307138.
They have 32 divisors. The one in bold is not mentioned in the
contribution of Farideh.
I could not find any more such numbers below 3x10^10.
For numbers with 64 divisors or more, I could not find any below
Maybe interesting to mention is the sequence A080715 in the OEIS
: it contains all the numbers m with the property that, if a
and b are positive integers such that a*b = m, the value of a+b
is prime. That sequence contains (among others) all the mentioned
Farideh reported more solutions with 16 prime sums,
totalizing 11 solutions up today:
50809032618, 54965915662 & 77323737562
So, the current challenge remains:
Up today no one single example having 6
prime factors & 32 prime sums is known