mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-12-04, 12:11   #12
goldbug
 
goldbug's Avatar
 
Dec 2018

2×11 Posts
Default 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...
goldbug is offline   Reply With Quote
Old 2018-12-04, 13:12   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26×131 Posts
Default

Quote:
Originally Posted by goldbug View Post
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.
science_man_88 is offline   Reply With Quote
Old 2018-12-04, 13:39   #14
goldbug
 
goldbug's Avatar
 
Dec 2018

2·11 Posts
Post 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 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:

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,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:

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,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()

Last fiddled with by goldbug on 2018-12-04 at 13:58 Reason: Adding Code Tags
goldbug is offline   Reply With Quote
Old 2018-12-04, 15:25   #15
goldbug
 
goldbug's Avatar
 
Dec 2018

268 Posts
Default Is Goldbach true for both non-Goldbug and Goldbug Numbers?

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.
goldbug is offline   Reply With Quote
Old 2018-12-04, 21:37   #16
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

937510 Posts
Default

Quote:
Originally Posted by goldbug View Post
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....)
chalsall is offline   Reply With Quote
Old 2018-12-05, 00:01   #17
goldbug
 
goldbug's Avatar
 
Dec 2018

2×11 Posts
Default

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 is offline   Reply With Quote
Old 2018-12-05, 01:52   #18
goldbug
 
goldbug's Avatar
 
Dec 2018

1616 Posts
Default 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 2018-12-05 at 01:58
goldbug is offline   Reply With Quote
Old 2018-12-05, 02:01   #19
uau
 
Jan 2017

7910 Posts
Default

Quote:
Originally Posted by chalsall View Post
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.
Quote:
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 is offline   Reply With Quote
Old 2018-12-05, 02:09   #20
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by goldbug View Post
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 is offline   Reply With Quote
Old 2018-12-05, 02:29   #21
uau
 
Jan 2017

79 Posts
Default

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.


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 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]))
uau is offline   Reply With Quote
Old 2018-12-05, 03:37   #22
goldbug
 
goldbug's Avatar
 
Dec 2018

2×11 Posts
Default

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

Last fiddled with by goldbug on 2018-12-05 at 03:44
goldbug is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
find the missing number MattcAnderson Puzzles 10 2017-05-21 01:52
Please help me find a composite number (test2) allasc Math 0 2010-12-27 13:37
What way would you find numbers with a set number of factors? nibble4bits Puzzles 18 2006-01-07 10:40
how do you find number of digits of a 2^n number? Unregistered Math 11 2004-11-30 22:53
Can you find the smallest number? Fusion_power Puzzles 8 2003-11-18 19:36

All times are UTC. The time now is 12:28.

Sat Dec 5 12:28:42 UTC 2020 up 2 days, 8:40, 0 users, load averages: 1.16, 1.28, 1.47

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.