Believe it or not I received in the same week four proposals for puzzles-conjectures related to the old and noble Goldbach's Conjecture (GC):

"Every even integer greater than 3 is the sum of two prime numbers".

1. Sebastian Martín Ruiz found (see historical note below) that the GC is equivalent to the following statement involving the well known Euler's function φ:

For all n=>4 it always exists an integer k, 1<=k<=n-1 such that:

φ(n²-k²)=(n-1)²-k²

Q1. Can you display the equivalence between the GC and the SMR statement?
Q2. Can you prove the SMR statement without using the GC? (*)

2. Jon Perry sent the following conjecture with the same simple arithmetic structure than the GC:

Every sufficiently large even number is the sum of two co-prime odd composite integers.

After a little empirical verification of the conjecture, I suggested to Perry that the implicit "sufficiently even large number" might be the not so large but the nice number 210.

Q3. Can you prove or disapprove the Perry's Conjecture?
Q4. Is there a formal relationship between the GC and the Perry's Conjecture?

3. Luis Rodríguez sent two more conjectures with the same logic structure than the GC.

The first one is a very ingenious modification made by Rodríguez to another conjecture stated by Euler. I will call this one "the Euler-Rodríguez conjecture".

For any whole number N, there exists a triangular T=k(k+1)/2, k=>0, such that,  if  T is subtracted from N, the difference is multiplied by 4  and 1 is added to it, then a prime number results (P=4(N-T)+1).

Q5. Can you prove or disapprove the Euler-Rodríguez Conjecture?

4. The second one is original from Rodríguez and has been named by himself "The Ludovicous Conjecture - II"

For each natural number N, there always exists two positive integers k and j, such that:6*(N-k²)+1 and 6*(N-j²)-1 are, both, prime numbers.

Rodríguez has verified this conjecture up to N=5*10⁷. He also has studied the quotients k_max/(ln(N))² and j_max/(ln(N))².  And the questions are:

Q6. Verify if the quotients  k_max/(Ln(N))2  or  j_max/(Ln(N))2 approach to a limit when N  grows indefinitely.
Q7. Find the greatest value of each quotient.
Q8. Find an heuristic or probabilistic argument that reinforces the conjecture.

____
(*) Watch out carefully this question because its correct answer worth a lot of money and fame...

Historical note: SMR sent the 19/12/02 the following message to be added in these pages:

Phil Carmody and Joseph L. Pe demonstrated the equivalence asked in the Q.1, between the SMR statement and the GC:

Carmody wrote:

Joseph L. Pe wrote:

I'm able to prove that SMR is equivalent to something apparently stronger
than GC:
 
Every even integer >=  8 is the sum of two DISTINCT prime numbers.
 
I call this statement EGC ("extended Goldbach's Conjecture"). Note that GC
doesn't require that the two primes be distinct. Clearly, EGC implies GC,
but the converse is not necessarily valid.
 
I've verified that EGC holds for even n, 8<=n <= 7000 or so, and conjecture the validity of EGC. I learned that R. Zumkeller has conjectured
something that is essentially EGC in A071681 of the OEIS.
 
If the integer k, 1<=k<=n-1 in SMR is changed to k, 0<=k<=n-1, then
it's easy to modify the proof below to show the equivalence of SMR and GC.

...

Let SMR be the assertion:
If n>=4, then there exists an integer k, 1<=k<=n-1, such that phi(n^2-k^2)=(n-1)^2-k^2;and EGC be the assertion: Every even integer >= 8 is the sum of two distinct prime numbers. Then EGC is equivalent to SMR.
 
Proof.
(EGC implies SMR)
Let n>=4, so that 2n >= 8. using EGC, write 2n = p1 + p2 where p1 and p2 are distinct primes. One of p1, p2, say p1,  must be > n and the other < n. Hence, p1=n+k and p2=n-k with 1<=k<=n-1. [Note that the assumption that p1 and p2 are distinct is needed to conclude 1<=k.] Then phi(n^2-k^2)=phi((n+k)(n-k))=phi(p1*p2)
=(p1-1)*(p2-1)=(n+k-1)(n-k-1)=((n-1)+k)((n-1)-k)=(n-1)^2-k^2, proving SMR.
 
(SMR implies EGC)
Let 2n be an even integer >=8 (hence n>=4); we must show that 2n is the sum of two distinct primes. By SMR, since n>=4, there is an integer k, 1<=k<=n-1, such that phi(n^2-k^2)=(n-1)^2-k^2. That is, phi((n-k)(n+k))=(n-k-1)(n+k-1). It is easy to see (but tedious to write down) that if phi(pq)=(p-1)(q-1), then p, q are primes. Therefore, n-k and n+k are primes, and are distinct, since k>=1. It follows that 2n=(n+k)+(n-k), the sum of distinct primes.

***

Alexander Nicholson wrote (may 08):

Q3. Perry's Conjecture is true. Here is a proof:

If a and b are coprime odd numbers that add to x, then it must also be that gcd(a,x)=gcd(b,x)=1 since if gcd(a,x)=c then c|(x-a) so gcd(a,b)>=c. Similarly, any a<x with gcd(a,x)=1 will satisfy gcd(a,x-a)=1. If x is even, then every a coprime to x must be odd, so the number of ordered pairs (a,x-a) that are coprime with a<x is precisely the number of positive integers less than and coprime to x, or Euler's phi(x).

If a is not prime or 1 and x-a is not prime or 1, then the pair is coprime and composite and satisfies the condition. Thus the number of coprime pairs that do not satisfy the condition is at most 2*(pi(x)+1), where pi(x) is the number of primes <= x.

Define C(x)=phi(x)-2*(pi(x)+1). Then the number of coprime composite pairs that sum to x is at least C(x). We can show that this C(x)>=1 for x sufficiently large.

Let f(x)=x/phi(x). Since phi(x)=x*\prod_{p|x}(1-1/p) where the product is over all primes p that divide x, then f(x)=\prod(p/(p-1))=2*\prod_{p odd}(p/(p-1)) since x is even.

Let g(x)=x/(2*(pi(x)+1)+1) > x/(pi(x)*11/5) when pi(x)>15 or for all x>=53. Using a bound due to Rosser (see http://en.wikipedia.org/wiki/Prime_number_theorem#Bounds_on_the_prime-counting_function), we can write pi(x)<x/(log(x)-4) for all x>=55 (here we use log(x) for the natural logarithm).
[1] Thus g(x) > 5*(log(x)-4)/11 when x>=55.

Let t(x) = f(x)/p0, where p0 is the largest prime that divides x.
[2] For prime q that divides x, f(q*x) = f(x).
[3] For any prime p1>p0 and n>=1: f(x*p1^n) = p1/(p1-1)*f(x) < p1/p0*f(x) <= t(x)*p1. We can add any increasing sequence of primes in order, for p2>p1 in a similar way f(x*p1^n1*p2^n2) < t(x)*p2, and for pj>p_{j-1}>...>p2>p1>p0 then f(x*p1^n1*p2^n2*...*pj^nj) < t(x)*pj.
[4] f(p1*x)-f(x) = p1/(p1-1)*f(x) - f(x) = 1/(p1-1)*f(x) <= t(x)*p0/(p1-1) <= t(x)

f(2) = 2 so t(2) = 1. Hence from [4]:
[5] If x is even and has exactly k distinct odd prime factors, then f(x) <= f(2) + k*t(2) = k+2.

Hereafter let k denote the number of distinct odd prime factors of x.
[6] From [1] if x > exp(4+(k+2)*11/5) for k>=0 then g(x) > k+2 (since for any k>=0 this requires x>55) and so [5] gives g(x) > f(x).
Denote by #(n) the primorial function, i.e. the product of the first n primes.
Then if x is even, x>=#(k+1) since x has k distinct odd prime factors, which must be at least as large as the first k odd primes.
If k>=3 then x>=#(4)=210 and the bound in [1] holds, hence g(x) > 5*(log(#(k+1))-4)/11.
Combined with [5] we have
f(x) <= k+2 and g(x) > 5*(log(#(k+1))-4)/11
We can check numerically that for k=13, we have
f(x) <= 15 < 5*(log(#(14))-4)/11 < g(x)
[7] Incrementing k increases the lower bound on g by log(pk)>1 and increases the upper bound on f by 1, so f(x)<g(x) for all k>=13.
For k<=12 then from [6] if x > exp(4+14*11/5) >= exp(4+(k+2)*11/5) then g(x)>f(x).
Hence for all x > exp(174/5) we have g(x)>f(x) from either [6] if k<13 or from [7] if k>=13.

f(x)<g(x)
=> x/phi(x) < x/(2*(pi(x)+1)+1)
=> phi(x) > 2*pi(x)+3
=> C(x) = phi(x)-2*(pi(x)+1) > 1

And hence for all x sufficiently large C(x)>1 and there exists a pair of coprime odd composite numbers that sum to x, and the conjecture is proved true.

Q4.
This is related to Goldbach's Conjecture at least in the following sense.
There are phi(x) ordered pairs (a,x-a) with gcd(a,x)=1 that sum to x. Two of them are (1,x-1) and (x-1,1).
The others are either two composite numbers, one prime and one composite, or two primes.
If the number of composite pairs is exactly C(x) as above, then the remainder must pair each prime with a composite number. If, however, the number of composite pairs is greater than C(x), then there must be some pair such that a and x-a are both prime.

---

I tried to keep the proof short, and as a result x "sufficiently large" is very large, exp(174/5)>10^15. I believe this could be improved fairly quickly by considering a few cases separately, e.g. assume that 3 and 5 do not divide x, then x>=#(k+3)/15 and we get a larger lower bound on g(x) as a function of k; then we need to consider separately the cases that x=2*3^n, x=2*5^n, x=30*n and x=2*3*p*r or x=2*5*p*r for some prime p>5. Starting with a larger x generally should allow a better bound on t(x)<=1 as well and hence on f(x). If we can improve the bounds enough so that [7] applies when k>=7, then I think the bound should be low enough to search all smaller even numbers by brute force to check whether in fact 210 is sufficiently large.

***

T. D. Noe added (May 08)

According page 190 of the book "Lure of the Integers" by Joe Roberts, Jon
Perry's conjecture was proved by A. M. Vaidya in 1980.

***