Problems & Puzzles: Puzzles

Puzzle 549.- 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

2+105=107
3+70=   73
5+42 = 47
6+35=41
7+30=37
10+21=31
14+15=29

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 question:

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, ?

***

Jan wrote:

Lets define 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 would be:

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 samethe same:

The first solution > 7 pairs is:

Number: 66378
Factor count: 32
Factors
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
Combinations: 15
2+33189=33191
3+22126=22129
6+11063=11069
13+5106=5119
23+2886=2909
26+2553=2579
37+1794=1831
39+1702=1741
46+1443=1489
69+962=1031
74+897=971
78+851=929
111+598=709
138+481=619
222+299=521

There are 4 more such solutions < 5000000, all with 32 factors ant 15 combinations. N+1 is prime.

Number: 186162
Number: 899970
Number: 1624462
Number: 3047410

***

Luis wrote:

Any primorial serves to construct a great deal of primes
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

***

Farideh wrote:

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 form 2^k.

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 yet.
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 + 210
= 211.

Let a(n) be the number of distinct primes of the form d + n/d, where d is a
divisor of n.  Then it is easy to see that for n > 1, we have a(n) > 0 only
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 Vandermast is
interested in finding n such that d + n/d is prime for every divisor d of
n.  In this case, n must be an even number that is the product of distinct
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 n
consisting of 5 primes is 186162 = 2*3*19*23*71, which produces 16 primes
of the form d + n/d.  An interesting question is whether there are numbers
n with a greater number of prime factors.

Kok Seng Chua has studied this question and posted his results as sequences
http://oeis.org/classic/A128276http://oeis.org/classic/A128277,
http://oeis.org/classic/A128278, and http://oeis.org/classic/A128279.  He
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 explain
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 use
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 32
linear polynomials:

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 polynomials.)
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 gives
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 that
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 prime sums.

***

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, primeCount=404978.
At pIndex=23, primorial=267064515689275851355624017992790, primeCount=853279.
At pIndex=24, primorial=23768741896345550770650537601358310, primeCount=1609502.
At pIndex=25, primorial=2305567963945518424753102147331756070,
primeCount=3008915.

***

Anton Vrba wrote:

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 10^11.

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

***

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

***

 Records   |  Conjectures  |  Problems  |  Puzzles