20181204, 12:11  #12 
Dec 2018
2×11 Posts 
Order 3 #GoldbugNumbers
My code is not finding any triples, can anyone confirm this? Hard to know if the code is correct with no counterexamples to check...

20181204, 13:12  #13 
"Forget I exist"
Jul 2009
Dumbassville
2^{6}×131 Posts 
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 2np for p one of the primes, unless it's 1. etc.

20181204, 13:39  #14 
Dec 2018
2·11 Posts 
Code to find order 2 and order 3 goldbug numbers
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 korder subsets of prime nondivisors. I have included the code for pairs and triples of primes. Enjoy!
Here is my code to find order 2 Goldbugs: Code:
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,n1,2): if p1<int(math.sqrt(2*n)) and is_prime(p1): for p2 in range(3,p12,2): if p2<int(math.sqrt(2*n)) and is_prime(p2): if (2*np1)%p2==0 and (2*np2)%p1==0: #Test that 2np1 is a perfect power of p2 test1=0 t=p2 while t<=(2*np1): if t==2*np1: test1=1 t=t*p2 #Test that 2np2 is a perfect power of p1 test2=0 t=p1 while t<=(2*np2): if t==2*np2: 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: Code:
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,n1,2): if p1<int(math.sqrt(2*n)) and is_prime(p1): for p2 in range(5,p12,2): if p2<int(math.sqrt(2*n)) and is_prime(p2): for p3 in range(3,p22,2): if p3<int(math.sqrt(2*n)) and is_prime(p3): if ((2*np1)%p2==0 or (2*np1)%p3==0) and ((2*np2)%p1==0 or (2*np2)%p3==0) and ((2*np3)%p1==0 or (2*np3)%p2==0): #Test that 2np1 is a perfect power of p2 and p3 test1=0 t1=1 while t1<=(2*np1): if t1==2*np1: test1=1 t2=t1*p3 while t2<=(2*np1): if t2==2*np1: test1=1 t2=t2*p3 t1=t1*p2 #Test that 2np2 is a perfect power of p1 and p3 test2=0 t1=1 while t1<=(2*np2): if t1==2*np2: test2=1 t2=t1*p3 while t2<=(2*np2): if t2==2*np2: test2=1 t2=t2*p3 t1=t1*p1 #Test that 2np3 is a perfect power of p1 and p2 test3=0 t1=1 while t1<=(2*np3): if t1==2*np3: test3=1 t2=t1*p2 while t2<=(2*np3): if t2==2*np3: test3=1 t2=t2*p2 t1=t1*p1 if test1==1 and test2==1 and test3==1: print(2*n, p1, p2, p3) print() Last fiddled with by goldbug on 20181204 at 13:58 Reason: Adding Code Tags 
20181204, 15:25  #15 
Dec 2018
26_{8} Posts 
Is Goldbach true for both nonGoldbug and Goldbug Numbers?
It seems Goldbach is true for nonGoldbugs since we are guaranteed a process for finding a Goldbach pair. Start with any prime nondivisor of n and look at 2np. If its prime you have a Goldbach pair and you are done. If not, it gives you info about another prime nondivisor of n. Add that to the list and look at the corresponding 2np, if they don't give you a Goldbach pair then they must contain information about other prime nondivisors (since they are nonGoldbug).
Keep repeating this process of adding prime nondivisors to your list until you find a Goldbach pair. The process has to stop since there are only a finite number of prime nondivisors. 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 nondivisors 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 nondivisors. n3=11003=1097 Goldbach Pair n13=110013=1087 Prime n+3=1100+3=1103 Goldbach Pair n+13=1100+13=3*7*53 (New prime nondivisors) So it would seem if we use 2np, np, and n+p to gather information about additional prime nondivisors we are guaranteed finding a Goldbach Pair for both Goldbug and nonGoldbug numbers. This is why it would be interesting to find another Goldbug Number, but so far no luck. 
20181204, 21:37  #16 
If I May
"Chris Halsall"
Sep 2002
Barbados
9375_{10} Posts 
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....) 
20181205, 00:01  #17 
Dec 2018
2×11 Posts 
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...

20181205, 01:52  #18 
Dec 2018
16_{16} Posts 
Problem with the code above
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): Last fiddled with by goldbug on 20181205 at 01:58 
20181205, 02:01  #19  
Jan 2017
79_{10} Posts 
Quote:
Quote:
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. 

20181205, 02:09  #20 
Jan 2017
79 Posts 
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. 
20181205, 02:29  #21 
Jan 2017
79 Posts 
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 Np always breaks into factors in the set. For example 6142. Code:
#!/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 maxsqrt(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])) 
20181205, 03:37  #22 
Dec 2018
2×11 Posts 
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. Code:
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 2np 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*nx)==0: g.add(x) # Generate all subsets of the primes gss=list(powerset(g)) #Calculate the product of the 2np's for x in gss: if len(x)>1: product=1; for y in x: product=product*(2*ny) #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) Last fiddled with by goldbug on 20181205 at 03:44 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
find the missing number  MattcAnderson  Puzzles  10  20170521 01:52 
Please help me find a composite number (test2)  allasc  Math  0  20101227 13:37 
What way would you find numbers with a set number of factors?  nibble4bits  Puzzles  18  20060107 10:40 
how do you find number of digits of a 2^n number?  Unregistered  Math  11  20041130 22:53 
Can you find the smallest number?  Fusion_power  Puzzles  8  20031118 19:36 