The best algorithm for finding Goldbug Numbers

Question

A Goldbug Number of order k is an even number 2n for which there exists some k order subset of the prime non-divisors of n $2 < p_1 < p_2 < p_3 < \cdots < p_k < n$ such that $(2n-p_1)(2n-p_2)(2n-p_3)\cdots (2n-p_k)$ only has $p_1,p_2,p_3,…,p_k$ as factors.

More information can be found at the related OEIS entry. https://oeis.org/A306746

Answer 1

I am posting the code from the forum written by UAU. This is the best implementation to date and identifies 6 Goldbug numbers under 100k. Keep in mind for speed this is searching for the maximal set and there can be subsets of the maximal set which satisfy the Goldbug property. I have run the code and verified it produces 6 Goldbugs under 100k (128,1718,1862,1928,2200,6142). For more details see the original post:

https://www.mersenneforum.org/showpost.php?p=501714&postcount=23

Thanks UAU!

#!/usr/bin/python3
import sys

def sieve(n):
    n //= 2
    r = [[] for _ in range(n)]
    for x in range(1, n):
        if r[x]:
            continue
        r[x] = None
        y = 3*x+1
        while y < n:
            r[y].append(2*x+1)
            y += x+x+1
    return r

def check(n, r):
    s = {}
    for i in range(3, n//2, 2):
        if r[i>>1] is not None or not n % i:
            continue
        for f in r[(n-i)>>1] or [n-i]:
            s.setdefault(f, []).append(i)
    bad = [x for x in s if x >= n//2]
    bad_seen = set(bad)
    ok = set(i for i in range(3, n // 2, 2) if r[i>>1] is None and n % i)
    while bad:
        x = s.get(bad.pop(), ())
        for p in x:
            if p not in bad_seen:
                bad.append(p)
                bad_seen.add(p)
                ok.discard(p)
    return ok

def search(lim):
    r = sieve(lim)
    for i in range(2, lim, 2):
        x = check(i, r)
        if x:
             print(i, sorted(x))

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