Problems & Puzzles: Puzzles

Puzzle 482. Two Bergot questions JM Bergot sent two unrelated questions, perhaps nice to solve this week: Q1. The even number 62 cannot be expressed as the sum of two odd semiprimes.� Is there a 2n such that all 2m>2n can be expressed as the sum of two odd semiprimes? Q2. Using any two primes p,q one sees that for 3*13 - (3+13)=23 and 23 also equals 5*7-(5+7).� Can a prime be found in more than two ways using just two primes in this method [r=p.q-(p+q)]?

�

---

Carlos Rivera wrote for For Q1:

See A152483 from Donovan Johnson (Dec 2008)

***

Contributions came from F. Schneider, Jacques Tramu, JC Rosa, A. Verroken, Jan van Delden, Yao Jialin & M. Hasler, and Farideh Firoozbakht

From almost all of them I will show only their larger solution to Q2.

***

F. Schneider wrote:

It's quite easy to find multiple solutions, I checked through a million and found minimum match numbers from 1 to 17. Originally, I tried bit of a Chinese Remainder approach but the brute force method has better minimal yields:

...

453599: (2,453601) (11,45361) (17,28351) (31,15121) (37,12601) (61,7561) (71,6481) (73,6301) (109,4201) (113,4051) (163,2801) (181,2521) (211,2161) (281,1621) (379,1201) (433,1051) (601,757) [Total = 17]

***

J. Tramu wrote:

r= 7294860647687393919192467673189519224120291202428224581064143667199999
r+1 =2^116*3^7*5^5*7^4*11^2*13^2*17*19*23*29*31*37*41*43*47*53*59*61*67
pairs( (p,q) = 4555255

***

JC Rosa wrote:

r=735134399 ; number of ways=58
p=3;5;43;71;89;109;.....;26209

***

A. Verroken wrote:

Five ways : r = 1151,1259,1871

***

Jan wrote:

r=2^2.2^15.3^5.5^5.7^4.11.13.17.19.23-1 -> ways=1683

***

Yao wrote:

r=2^9*3^5*5^2*7^2*11^2*13*17*19*23*29-1 = 5164 9890 1446 5279 9, have ways=1013!!!!

***

W. Hasler wrote:

Obviously we have r=pq-(p+q) <=> r+1 = (p-1)(q-1), so one can simply
scan primes+1 for divisors d such that d+1 and the cofactor+1 both are
prime.

Doing so, one find the following "record primes" (i.e. such that the
number of decompositions is larger than for any smaller prime:

3, 59, 71, 1151, 2399, 7559, 42839, 110879, 181439, 241919, 262079,
453599, 665279, 1713599, 2827439, 6425999, 11309759, 12700799,
14137199, 16707599, 37837799, 45239039, 64864799, 82162079, 86486399,
93562559, 260124479, 410810399, 735134399, 950019839, 1074427199,
1470268799, 2205403199, 3223281599, 4108103999, 5967561599,
7524316799, 9945935999, 15437822399, ...

The number of respective decompositions is:

2, 3, 4, 5, 6, 9, 10, 11, 12, 14, 16, 17, 19, 20, 22, 23, 25, 26, 27,
31, 32, 33, 34, 37, 42, 45, 46, 54, 58, 61, 65, 70, 71, 73, 76,
77, 78, 87, 100, ...

***

Farideh wrote:

Answer to Q1:

I think 2n = 62, namely all even numbers greater than 62 can be expressed as
the sum of two odd semiprimes. Also I think all even numbers greater than 22 can
be expressed as the sum of two semiprimes.
I also guess that number of such representations of an even number n depends to
both largeness of n and it's factorizations to prime numbers.
Note that there exists a similar conjecture for number of representations of an even
number as a sum of two primes.

Answer to Q2:

Suppose that number of such representations for a prime r be f(r).

The smallest primes r such that f(r) = n for n < 55 are respectively :

5, 3, 59, 71, 1151, 2399, 9719, 19319, 7559, 42839, 110879, 181439, 347759,
241919, 385559, 262079, 453599, 1441439, 665279, 1713599, 4804799,
2827439, 6425999, 6652799, 9827999, 12700799, 14137199, 25280639,
46388159, 22276799, 16707599, 25945919, 45239039, 64864799, 77111999,
82882799, 82162079, 100900799, 256183199, 99459359, 158336639, 86486399,
240589439, 337296959, 93562559, 260124479, 415134719, 622702079,
432431999, 588107519, 791683199, 596756159, 1059458399, 410810399.


Jacques Tramu's idea :

" Primes of the form n -1 where all distinct prime factors of n are
exactly the first three (or more) primes seems to give good results. "

I used his idea and found many primes r with large quantities of representations
of the form p*q - (p+q).

The largest f(r) that I found is 187267 for r = 6934348041978206524156022661119999.

The interesting point is that there is no even one such representation for 29 prime
numbers before and 19 prime numbers after this nice prime.

I also found the following nice point.

If r is a prime of the form a*b*10^k -1 and all 2k+2 numbers
a*10^m+1, b*10^m+1 m = 0, 1, ..., k are prime then f(r) > k. ( * )

Proof of ( * ) : For m = 0, 1, ..., k we have,

r = a*b*10^k -1 = (a*10^m+1)*(b*10^(k-m)+1) - ( (a*10^m+1) + (b*10^(k-m)+1)
so for r there exist at least k+1 representations of the form p*q - (p+q), namely f(r) >k.

I searched for such primes r which f(r) be exactly k+1 (there is no other representation
for r) and found many of them.

The following table gives smallest such primes for k<4.


k a b r f(r)
---------------------------------------------------------------
0 1 6 5 1
---------------------------------------------------------------
1 1 102 1019 2
---------------------------------------------------------------
2 1 4506 450599 3
----------------------------------------------------------------
3 1 354666 1418663999 4
----------------------------------------------------------------

***

�