5
$\begingroup$

This a computational challenge, to find an efficient algorithm to discover a quadruple $(n,n+1,n+2,n+3)$ with the same sum of prime factors as described in the MO question, "Ruth-Aaron triples, etc." E.g., $$417,164 = 2^2 \cdot 11 \cdot 19 \cdot 499 \;;\; 2+2+11+19+499 = 533 \;.$$ The sum can be computed by multiplying the exponent in the prime factorization times the base prime:

SumFact[n_] := Apply[Plus, Map[#[[1]] #[[2]] &, FactorInteger[n]]];

Apparently no such quadruple is known, and I've checked through $n=10^7$, and am now trying to reach $10^8$ in the next day or so. But my computation is naive in terms of efficient computation. Also, I do not have easy access to significant computational resources.

As far as I can make out, there is no known such quadruple.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Oh, there is an indication that such a quadruple must lie beyond $10^{10}$, which is well beyond what resources I can muster. $\endgroup$ – Joseph O'Rourke Dec 24 '14 at 3:03
  • 2
    $\begingroup$ You need only search first every successive pairs of even numbers n to find adjacent even Ruth-Aaron numbers; if found, only then test the three additional adjacent (odd) numbers. This eliminates roughly half the computations in the naive method. Next, because in this first sieve search you're only searching even numbers, you could instead divide each by 2 (which subtracts the same increment in the R-A sum), and so instead search successive pair of "half" numbers. Finally, this search is highly parallelizable using Parallelize[]. $\endgroup$ – David G. Stork Dec 24 '14 at 17:58
6
$\begingroup$ 
SumFact[n_: Integer] := Apply[Plus, Map[#[[1]] #[[2]] &, FactorInteger[n]]];
A = {};
lastFac = SumFact[10^7 - 1];
Do[
  If[(z = SumFact[n]) == lastFac, AppendTo[A, n]];
  lastFac = z, 
  {n, 10^7 + 1, 10^8, 2}];
A

This took about 15 minutes on my MacPro and gave 417 candidates. There should be no problem parallelizing this code and getting up to n = 10^9 in an evening or so.

Then the full test:

fulltest[n_: Integer] := 
 If[SumFact[n - 2] == SumFact[n - 1] == SumFact[n] == SumFact[n + 1] || 
    SumFact[n - 3] == SumFact[n - 2] == SumFact[n - 1] == SumFact[n], 
  n];

Union@(fulltest[#] & /@ A)

{Null}

So there are no examples up to 10^8. I just completed the search: no examples up to 10^9. I'm running the search up to 10^10 over the holiday break.

Of the 7060 even Ruth-Aaron pairs between 10^ and 10^10, alas there are no Ruth-Aaron quadruplets.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Great, David! If you find a quadruple, it will be the first discovered, as far as I can discern from the literature. $\endgroup$ – Joseph O'Rourke Dec 25 '14 at 23:48
  • 1
    $\begingroup$ @JosephO'Rourke: I even checked between 10^9 and 10^10 for Ruth-Aaron TRIPLES (testing odd numbers between my found even pairs) and found no such triples. These must be rare indeed! $\endgroup$ – David G. Stork Jan 2 '15 at 16:42
  • $\begingroup$ Would it be feasible to search for the tulples using the GPU with its multitude of cores? e.g. via CUDALink or something like it? $\endgroup$ – QuantumDot Jan 3 '15 at 6:48
  • $\begingroup$ I believe so, yes. I've parallelized my code for my multi-core Mac Pro, and this speeds things up. I'm not a CUDA expert and have no immediate access to such a processor, but perhaps some ambitious computational number theorist would like to take up the challenge. $\endgroup$ – David G. Stork Jan 3 '15 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.