Can you find another number like 2200?

[goldbug]

My code is not finding any triples, can anyone confirm this? Hard to know if the code is correct with no counterexamples to check...

[science_man_88]

Originally Posted by goldbug

My code is not finding any triples, can anyone confirm this? Hard to know if the code is correct with no counterexamples to check...

Share the code... maybe we can offer improvements or PARI/GP etc codes. In any triplet of primes greater than 3, by pigeonhole principle two are either of +1 or -1 from multiples of 6. we can skip triples with duplicates, which cuts checking by potentially 3 fold. another property is we don't check the same triplet in a different order without repeats these have 6 orderings. Only 1 of those needs checking. gcd of the separate primes minus 1 each will never divide 2n-p for p one of the primes, unless it's 1. etc.

[goldbug]

This code is very straightforward in order to be transparent (know what its doing) and is not the best approach clearly. It would be nice to code this up using sets/subsets in python to do k-order subsets of prime non-divisors. I have included the code for pairs and triples of primes. Enjoy!

Here is my code to find order 2 Goldbugs:

import sys
import math
from sympy import sieve 
# Python program to find order 2 Goldbug Numbers

def is_prime(test_num):
    result=1
    if test_num > 1:
           for i in range(3,int(math.sqrt(test_num)),2):
            if (test_num % i) == 0:
                       result=0
                       break
    else:
           result=0
    return(result)


for n in range(100,10000):
    sys.stdout.write("\033[F")
    print(2*n)
    for p1 in range(5,n-1,2):
        if p1<int(math.sqrt(2*n)) and is_prime(p1):
            for p2 in range(3,p1-2,2):
                if p2<int(math.sqrt(2*n)) and is_prime(p2):
                    if (2*n-p1)%p2==0 and (2*n-p2)%p1==0:
                        #Test that 2n-p1 is a perfect power of p2                        
                        test1=0
                        t=p2                        
                        while t<=(2*n-p1):
                            if t==2*n-p1:
                                test1=1
                            t=t*p2
                        #Test that 2n-p2 is a perfect power of p1
                        test2=0
                        t=p1                        
                        while t<=(2*n-p2):
                            if t==2*n-p2:
                                test2=1
                            t=t*p1
                        if test1==1 and test2==1: 
                            print(2*n, p1, p2)
                            print()

And here is similar code for order 3 Goldbug Numbers:

import sys
import math
from sympy import sieve 
# Python program to find order 3 Goldbug Numbers

def is_prime(test_num):
    result=1
    if test_num > 1:
           for i in range(3,int(math.sqrt(test_num)),2):
            if (test_num % i) == 0:
                       result=0
                       break
    else:
           result=0
    return(result)


for n in range(100,10000):
    sys.stdout.write("\033[F")
    print(2*n)
    for p1 in range(7,n-1,2):
        if p1<int(math.sqrt(2*n)) and is_prime(p1):
            for p2 in range(5,p1-2,2):
                if p2<int(math.sqrt(2*n)) and is_prime(p2):
                    for p3 in range(3,p2-2,2):
                        if p3<int(math.sqrt(2*n)) and is_prime(p3):
                            if ((2*n-p1)%p2==0 or (2*n-p1)%p3==0) and ((2*n-p2)%p1==0 or (2*n-p2)%p3==0) and ((2*n-p3)%p1==0 or (2*n-p3)%p2==0):
                                
                                #Test that 2n-p1 is a perfect power of p2 and p3
                                test1=0
                                t1=1
                                while t1<=(2*n-p1):
                                    if t1==2*n-p1:
                                        test1=1
                                    t2=t1*p3
                                    while t2<=(2*n-p1):
                                        if t2==2*n-p1:
                                            test1=1
                                        t2=t2*p3
                                    t1=t1*p2
                                #Test that 2n-p2 is a perfect power of p1 and p3
                                test2=0
                                t1=1
                                while t1<=(2*n-p2):
                                    if t1==2*n-p2:
                                        test2=1
                                    t2=t1*p3
                                    while t2<=(2*n-p2):
                                        if t2==2*n-p2:
                                            test2=1
                                        t2=t2*p3
                                    t1=t1*p1
                                #Test that 2n-p3 is a perfect power of p1 and p2
                                test3=0
                                t1=1
                                while t1<=(2*n-p3):
                                    if t1==2*n-p3:
                                        test3=1
                                    t2=t1*p2
                                    while t2<=(2*n-p3):
                                        if t2==2*n-p3:
                                            test3=1
                                        t2=t2*p2
                                    t1=t1*p1

                                if test1==1 and test2==1 and test3==1: 
                                    print(2*n, p1, p2, p3)
                                    print()

[goldbug]

It seems Goldbach is true for non-Goldbugs since we are guaranteed a process for finding a Goldbach pair. Start with any prime non-divisor of n and look at 2n-p. If its prime you have a Goldbach pair and you are done. If not, it gives you info about another prime non-divisor of n. Add that to the list and look at the corresponding 2n-p, if they don't give you a Goldbach pair then they must contain information about other prime non-divisors (since they are non-Goldbug).



Keep repeating this process of adding prime non-divisors to your list until you find a Goldbach pair. The process has to stop since there are only a finite number of prime non-divisors. Try it for any number, it works like a charm. Well for almost any number... Goldbug numbers are the exception, they contain dead ends in this process.



So can we show its true for Goldbugs as well? Unfortunately, this is what Goldbug numbers are, they are numbers which cause this process to not be guaranteed since they contain a subset of prime non-divisors which are "isolated", they are only composed of powers of themselves.



Looking at the only known Goldbug 2n=2200 might provide a hint since 3 and 13 do contain information about other prime non-divisors.


n-3=1100-3=1097 Goldbach Pair

n-13=1100-13=1087 Prime
n+3=1100+3=1103 Goldbach Pair

n+13=1100+13=3*7*53 (New prime non-divisors)


So it would seem if we use 2n-p, n-p, and n+p to gather information about additional prime non-divisors we are guaranteed finding a Goldbach Pair for both Goldbug and non-Goldbug numbers. This is why it would be interesting to find another Goldbug Number, but so far no luck.

[chalsall]

Originally Posted by goldbug

Here is my code to find order 2 Goldbugs:

This is yet another example supporting my opinion as to why I dislike Python as a language.

Maybe I'm just old and crotchety... But using white space to define the logic just seems wrong to me.

What if I want to quickly remove a block of code with a quick conditional "(if 0) { ... }" to run an experiment? Not possible without the use of a IDE which will indent the code for me. Otherwise the compiler will refuse to compile the code because it's not "compliant".

What part of I'm sentient you're just a compiler isn't clear?

(And let's not even get into whether a tab == 3 spaces, or 8. Or 1....)

[goldbug]

I hear you about python, I have spent many hours chasing down indent issues. Not married to python just thought it would be accessible. One reason I posted here is I thought people would have suggestion for which is best package to use. Of course everyone would have their opinion...

[goldbug]

Here is a weird python thing, for some reason this doesn't check primes correctly, change it to "for i in range(3,test_num):". Doesnt' seem to impact the output. Sorry, cannot seem to change it in the previous post...



for i in range(3,int(math.sqrt(test_num)),2):

[uau]

Originally Posted by chalsall

This is yet another example supporting my opinion as to why I dislike Python as a language.

What about that is an example? You're just triggered by seeing any Python code in general? Your post looks like a low-intelligence low-content flame, enough so that I wonder whether you posted it as a deliberate trolling attempt.

What part of I'm sentient you're just a compiler isn't clear?

What does this have to do with whether blocks are indicated by indentation or by braces? Claiming that one method would be "the compiler trying to be sentient" is just ridiculous.



Overall, I think the best argument for indentation is that in practice braces are redundant unless the code is incorrectly indented, and deliberately supporting incorrect indentation is a rare enough use case that it's not worth forcing people to add redundant braces all the time in normal cases.

[uau]

Originally Posted by goldbug

for i in range(3,int(math.sqrt(test_num)),2):

The issue is that for example for 9 you test candidates 3 <= x < 3, which obviously doesn't find anything...

BTW doing primality testing one number at a time by trial division is horribly inefficient. You could use an existing package with a proper primality test, or if you don't want to do that for some reason, with about equivalent complexity as trial division you could write a sieve that finds all primes in the relevant range and then just test whether a number is one of those.

[uau]

Below is the code I used to check for pairs of p1^m - p1 = p2 ^ n - p2. It takes one argument which is the approximate maximum value of the equal value to check up to.


BTW regarding the more general question, there are other numbers N for which there is a set of primes, all less than N/2, for which N-p always breaks into factors in the set. For example 6142.

#!/usr/bin/python3

import sys
import array

# Using PARI for example to generate the primes would be faster
def sieve(n):
    n //= 2
    r = array.array('b', [1]) * n
    r[0] = 0
    for x in range(n):
        if not r[x]:
            continue
        y = 3*x+1
        while y < n:
            r[y] = 0
            y += x+x+1
    return [2*x+1 for x in range(n) if r[x]]

def search(lim):
    # The upper limit is approximate, largest second power is max-sqrt(max)
    primes = sieve(int(lim**.5))
    print('Number of primes:', len(primes))
    found = set()
    for p in primes:
        pp = p * p
        while pp < lim:
            k = pp - p
            if k in found:
                print(k)
            found.add(k)
            pp *= p

search(int(sys.argv[1]))

[goldbug]

Below is code I use to check for all order Goldbugs less than 5000. It only returns 2200. It explodes a bit running larger n, curious to see if anyone can suggest improvements. Agree with you uau that a sieve should be better and the way I am doing prime check is unforgivable, I tried one in python but it was actually slower (how?). I will try using what you provided.

The code can also check specific orders and up to a given order as well by modifying the comments.

import sys
import math
from itertools import chain, combinations
# Python program to find Goldbug Numbers

#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)

#Return subsets of a set
def powerset(iterable):
    xs = list(iterable)
    # note we return an iterator rather than a list
    #The following return statement checks all orders
    return chain.from_iterable(combinations(xs,n) for n in range(len(xs)+1))
    #Check up to order k instead
    #k=3
    #return chain.from_iterable(combinations(xs,n) for n in range(k+1))
    #Check only order k instead
    #k=3
    #return chain.from_iterable(combinations(xs,n) for n in range(k,k+1))

for n in range(10,2500):
    # Create set of all prime nondivisors of n less than n 
    # Where 2n-p is not prime
    # and x is less than square root of 2n?
    g=set()
    for x in range(3,n):
        if x<=int(math.sqrt(2*n)) and n%x!=0 and is_prime(x)==1 and is_prime(2*n-x)==0:
            g.add(x)

    # Generate all subsets of the primes
    gss=list(powerset(g))

    #Calculate the product of the 2n-p's
    for x in gss:
        if len(x)>1:
            product=1;
            for y in x:
                product=product*(2*n-y)
                #Mod reduction of the product to avoid big numbers        
                for z in x:
                    while(product%z==0):
                        product=product/z
            # Check if product contains only p's as factors for each subset        
            if product==1:
                print (2*n,x,product)