# efficient code to search for formulas for calculating primes

I had an idea for calculating primes using smaller primes given the following: p1=(p2-p3/p4)+(p5-p6/p7)

where p1>p5>p2 and p2>p3>p4 and p5>p6>p7 and p1 through p7 are all prime numbers.

For example, I found these manually but would like to find more:

19==(11-3/2)+(13-7/2)

23==(13-3/2)+(17-11/2)

29==(17-5/2)+(23-17/2)

31==(17-3/2)+(19-7/2)

41==(23-5/2)+(29-17/2)

43==(23-3/2)+(31-19/2)

I only found one formula for each of the primes 19,23,29,31,41,43, I think there would be more, so the sequence I'm interested in would be the count of distinct formulas for all p1. I'm not sure how to code this efficiently.

(*idea for calculating primes using smaller primes given the following:p1=(p2-p3/p4)+(p5-p6/p7) If[p1>p5>p2] If[p2>p3>p4] If[p5>p6>p7] If[(p2+p5)>p1]*)

lengthToCheck=9;

(*p1=(p2-p3/p4)+(p5-p6/p7) a=(b-c/d)+(e-f/g)*)

primesP1={};
primeIndexesOutput={};
primesOutput={};
nonTwoDenominatorCountd=0;
nonTwoDenominatorCountg=0;

For[a=1,a<lengthToCheck,a++,
Print[StringForm["loop  of ",a, lengthToCheck]];For[b=1,b<lengthToCheck,b++,For[c=1,c<lengthToCheck,c++,For[d=1,d<lengthToCheck,d++,For[e=1,e<lengthToCheck,e++,For[f=1,f<lengthToCheck,f++,For[g=1,g<lengthToCheck,g++,If[Prime[a]==(Prime[b]-Prime[c]/Prime[d])+(Prime[e]-Prime[f]/Prime[g]),If[PrimeQ[Prime[a]],If[Prime[a]>Prime[e]&&Prime[e]>Prime[b],(*If[p1>p5>p2]*)If[Prime[b]>Prime[c]&&Prime[c]>Prime[d],(*If[p2>p3>p4]*)
If[Prime[e]>Prime[f]&&Prime[f]>Prime[g],(*If[p5>p6>p7]*)
If[(Prime[b]+Prime[e])>Prime[a],(*If[(p2+p5)>p1]*)(*If[Prime[d]\[Equal]2&&Prime[g]\[Equal]2,*)(*p4 and p7 might always be 2*)AppendTo[primeIndexesOutput,{a,b,c,d,e,f,g}];
AppendTo[primesOutput,{Prime[a],Prime[b],Prime[c],Prime[d],Prime[e],Prime[f],Prime[g]}];
AppendTo[primesP1,Prime[a]];
If[Prime[d]!=2,(*p4 might always be 2*)nonTwoDenominatorCountd++;];
If[Prime[g]!=2,(*p7 might always be 2*)nonTwoDenominatorCountg++;]]]]]]]]]]]]]]
(*]*)(*(*If[Prime[d]\[Equal]2&&Prime[g]\[Equal]2,*)(*p4 and p7 might always be 2*)*)

Print["nonTwoDenominatorCountd"]
nonTwoDenominatorCountd
Print["nonTwoDenominatorCountg"]
nonTwoDenominatorCountg

primesP1;
Print["primeIndexesOutput"]
primeIndexesOutput;
Print["primesOutput"]
primesOutput
Print["tally of primes formulas"]
Tally[primesP1]


Code output:

During evaluation of In:= primesOutput
Out= {{13,5,3,2,11,3,2},{13,7,3,2,11,7,2},{13,7,5,2,11,5,2},{17,7,3,2,13,3,2},{17,11,3,2,13,11,2},{17,11,7,2,13,7,2},{19,5,3,2,17,3,2},{19,7,3,2,17,7,2},{19,7,5,2,17,5,2},{19,11,3,2,13,7,2},{19,11,5,2,13,5,2},{19,11,5,2,17,13,2},{19,11,7,2,13,3,2},{19,11,7,2,17,11,2},{19,13,11,2,17,11,2}}
During evaluation of In:= tally of primes formulas
Out= {{13,3},{17,3},{19,9}}


partial code output using "lengthToCheck = 24;" (code takes several hours)

tally of primes formulas
{{13,3},{17,3},{19,9},{23,13},{29,15},{31,29},{37,38},{41,41},{43,64},{47,74},{53,92},{59,106},{61,154},{67,185},{71,180},{73,253},{79,287},{83,310}}


From the tally, there are 38 formulas for prime 37, ie {37,11,3,2,29,3,2} corresponding to 37==(11-3/2)+(29-3/2). There is a lot of overlap in the formulas still, so the tallys should be lower.

Random result from the output: 83/2==43-3/2==47-11/2==53-23/2==71-59/2

cheers, Jamie

• additional info: p2+p5>p1 and p4 and p7 might always be 2? Jun 29, 2022 at 10:14
• This sounds more like a math problem and not a Mathematica problem. Jun 29, 2022 at 11:09
• For $p_3/p_4+p_6/p_7$ to be an integer, where $p_3>p_4$ and $p_6>p_7$ are primes, it is necessary that $p_4 = p_7$. Your formula then has the form $p_1=\text{(sum of two primes)}-\text{(sum of two primes)}/\text{(prime)}$. To get started, you could write a function SumOfTwoPrimesQ[n_] that determines if n is a sum of two primes (that may be as simple as Or[And[EvenQ[n],n>2],And[OddQ[n],PrimeQ[n-2],n>3]]) or that returns a list of all ordered pairs of primes whose sum is n. But your question is not (yet...) very Mathematica-l. Jun 29, 2022 at 13:11
• @JamieM I think you have to work harder to identify a clear question, there is too much to comment on here. Your approach is brute force with 7 nested For loops, which will give lengthToCheck^7 evaluations, which is not a good algorithm. You have an endless number of conditions such as Prime[c]>Prime[d] which you do not need if you replace d<lengthToCheck by d<c. Not to speak of PrimeQ[Prime[a]] which is always True, please drop. Of course For-loops are not idiomatic in Mathematica, use Map and friends instead. Jun 30, 2022 at 8:55
• @user293787 thanks for the feedback. I will implement some of that, currently I am collecting the valid formulas for each prime, ie: 149/2 == 83 - 17/2 == 89 - 29/2 == 101 - 53/2 == 131 - 113/2. There are 4 distinct formulas there for 149/2, so for each prime ie 149 I will find the number of distinct formulas, and maybe compare the formulas in a graph etc. Jun 30, 2022 at 9:08