A Puzzle Involving Goldbug's Algorithm

[goldbug]

What is the expected run time for each 2n<=10,000, if the likelihood of selecting each prime non-divisor of n in Step 1 is uniform? Does this algorithm terminate for each 2n>6? If not, for which 2n does it always terminate?

Goldbug's Algorithm

1. Given 2n>6 there exists a prime by Bertrand’s Postulate that must be a prime non-divisor (PND) of n or a Goldbach Pair. If 2n mod 4=0 then there exists n/2<p1<n. If 2n mod 4<>0 then there exists (n+1)/2<p1<n+1. If p1=n then done since 2n=2p1=p1+p1. Else p1<n.

2. Consider 2n-p1. If prime then done since p1 and 2n-p1 are a Goldbach Pair. Else factors of 2n-p1 must be unknown PNDs of n by Lemmas 2 and 3. Add the new PNDs to list of known PNDs.

3. Consider the factors of (2n-p1)(2n-p2)...(2n-pk) corresponding to the list of known PNDs. If one of the 2n-p is prime then done. Else must contain unknown PNDs since non-Goldbug. Add the new PNDs to list of known PNDs.

4. Repeat step 3.

[goldbug]

To clarify, by run time I just mean how many loops need to be performed. Not looking for a theoretical answer here.

[Batalov]

First of all, that's not a puzzle. -- the poster doesn't know the answer.

Secondly, this is terribly written. It is impossible to read without eyes bleeding...

What lemmas 2 and 3?!
"...that must be a prime non-divisor (PND) of n or a Goldbach Pair."
What does 'or' refer to? Why 'must'?
Why does this 'Algorithm' assume that Goldbach's conjecture is true?
etc
etc
etc
Why is this a puzzle where part of the premise is supposed to be taken on belief: "if the likelihood of selecting each prime non-divisor of n in Step 1 is uniform". If that is not true (which it likely isn't), then why do the rest? (that seems like work - and we don't like wasteful work... if at least it looked fruitful, then maybe, but in the present form looks like a mess)

[Batalov]

Rewrite this without all confusing 'then', 'must', 'or', 'since'. Nothing at all about 'Goldbach pairs' seems relevant. 'Stop because <bla>' - we don't need to know why we need to stop.

By the way, how the hell p1 can be a non-divisor of n ...and then p1==n ??

Build something like this--
0. take n>3.
1. make a list of primes p <= n such that !(p|n) and select one uniformly randomly and denote p1. If p1 == n, stop.
2. if 2*n-p1 is prime, stop. Else: .......
3. ...

Explain your own current contradiction: if 2*n=12, can p1 = 3 be randomly chosen or not? and why. Does p1 have to be a "randomly chosen PND" or form a "Goldbach pair"? Then, for 2*n=10, can 5 be chosen? 5 divides 10. 5+5 == 10 is a "Goldbach pair".

[goldbug]

Step 1 is just complicated for existence purposes. Just run the algo for all PNDs of n between n/2 and n (or (n+1)/2 and (n+1) for non mod 4's) and count the number of loops for each PND. Then take the average of the number of loops needed across the PNDs. This is the expected number of loops for any given 2n selecting the PNDs with equal probability.


The algorithm does assume Goldbach, what numbers does it fail for?

[Batalov]

How can it fail if it is not yet even an algorithm? it is a pile of words.

Make it into an algorithm, then we can discuss it.

[goldbug]

You are no fun, I didn't want to give it away but... try leaving out the Goldbugs, then I think it's a valid algorithm. The n=p1 thing is weird, its just a special case that happens with non-mod 4s



https://www.linkedin.com/feed/update...0387417878528/

[goldbug]

This doesn't solve the puzzle but you should run it. I think you will find it interesting!

import sys
import math
from itertools import chain, combinations
# Python program to test Goldbug's Algorithm

#Test if a number is prime
def is_prime(test_num):
    result=1
    if test_num > 1:
           for i in range(2,test_num):
            if (test_num % i) == 0:
                       result=0
                       break
    else:
           result=0
    return(result)

def goldbugs_algorithm(n):
    pnds=[]
    #We can stop if n is prime GBP
    if is_prime(n)==1:
        return([n,n])
    else:
        #If it isn't we can start down looking for PNDs
        #Bertrand says we eventually hit a prime non-divisor of n
        #before we get to n/2 or (n+1)/2 depending on mod4ness
        for k in range(n-1,0,-1):
            #If k is a prime non-divisor of n
            if is_prime(k)==1 and n%k!=0:
                #If 2n-k is prime GBP
                if is_prime(2*n-k)==1:
                    return([k,2*n-k])
                else:
                    pnds.append(k)
                    #Add the factors of k to the list of PNDs
                    for i in range(3,2*n-k):
                        if is_prime(i)==1 and (2*n-k)%i==0:
                            if i not in pnds:
                                pnds.append(i)
                    break
        #Now we check 2n-p for each PNDs in the list 
        #If any 2n-p is prime GBP
        #Else add factors of 2n-p to the list of PNDs
        #Repeat until GBP
        #Must terminate else contradiction by infinite descent
        while(1==1):    
            for j in pnds:
                if is_prime(2*n-j)==1:
                    return([j,2*n-j])
                else:
                    for i in range(3,2*n-j):
                        if is_prime(i)==1 and (2*n-j)%i==0:
                            if i not in pnds:
                                pnds.append(i)
    return([0,0])

#Dont run the Goldbugs!
goldbugs=[128,1718,1862,1928,2200,6142]

for n in range(4,5000):
    if 2*n not in goldbugs:
        print(2*n,goldbugs_algorithm(n))

[LaurV]

we suggest moving it to misc math