Can you find another number like 2200?

[uau]

Originally Posted by goldbug

# and x is less than square root of 2n?

This is wrong, there is no need for all the factors to be less than the square root.


Below is a more efficient way to search. It finds the maximal set of primes < n/2 such that factors of (n-p) always belong to the set.

#!/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]))

Up to 100000 this finds (n, list of primes):
128 [3, 5, 7, 11, 13, 17, 23, 29, 37, 41, 43, 47, 53, 59]


1718 [3, 5, 7, 11, 13, 17, 29, 31, 37, 41, 43, 47, 53, 59, 67, 73, 79, 89, 101, 127, 137, 149, 163, 167, 181, 191, 197, 199, 211, 233, 239, 241, 251, 281, 283, 311, 313, 349, 353, 383, 389, 409, 431, 443, 449, 463, 479, 491, 503, 509, 523, 557, 563, 569, 571, 577, 587, 593, 607, 613, 643, 647, 659, 691, 719, 733, 739, 743, 757, 761, 769, 773, 809, 827, 829, 857]


1862 [3, 5, 11, 13, 17, 29, 41, 43, 47, 53, 59, 67, 83, 97, 101, 107, 113, 127, 131, 151, 167, 179, 181, 191, 211, 233, 251, 257, 263, 269, 307, 311, 347, 353, 359, 383, 401, 421, 431, 443, 487, 499, 503, 509, 547, 557, 569, 577, 587, 593, 599, 601, 607, 617, 619, 647, 659, 673, 683, 701, 719, 751, 757, 773, 787, 809, 821, 857, 859, 887, 907, 929]


1928 [3, 5, 7, 11, 13, 17, 29, 43, 53, 71, 73, 79, 101, 103, 113, 131, 163, 173, 179, 211, 227, 233, 239, 251, 269, 311, 317, 353, 373, 383, 401, 443, 449, 461, 467, 487, 509, 563, 599, 619, 641, 653, 673, 733, 743, 773, 787, 797, 809, 823, 839, 853, 857, 863, 911, 953]


2200 [3, 13]


6142 [3, 5, 7, 13, 17, 19, 31, 43, 67, 71, 73, 97, 107, 109, 157, 199, 227, 229, 233, 283, 311, 317, 337, 353, 409, 467, 541, 557, 613, 617, 647, 673, 727, 769, 787, 811, 827, 877, 947, 997, 1039, 1063, 1087, 1117, 1129, 1229, 1237, 1249, 1297, 1303, 1327, 1399, 1483, 1487, 1543, 1553, 1579, 1613, 1627, 1669, 1693, 1777, 1787, 1823, 1867, 2011, 2087, 2099, 2143, 2161, 2207, 2243, 2251, 2267, 2297, 2437, 2467, 2521, 2551, 2593, 2647, 2659, 2663, 2707, 2767, 2777, 2791, 2857, 2887, 2917, 2953, 2957]

[goldbug]

This is so amazing uau!?! So interesting...


I was going to say, Goldbach is true for second order Goldbugs since the n-p's can't share a factor with p, n, or 2n-p. But no idea what to do with these. It is very interesting to look at these examples since many of the n-p are p's, and some of the n-p's give unknown p's


It would be interesting to find a Goldbug where the n-p's also contain only the p's as factors. I think in this case the n-p's might have to equal the p's? Maybe in that case n has to be prime and we can stop there... ;^)

128
p 2n-p N-p
3 125 61
5 123 59
7 121 57
11 117 53
13 115 51
17 111 47
23 105 41
29 99 35
37 91 27
41 87 23
43 85 21
47 81 17
53 75 11
59 69 5

[goldbug]

Were these the only ones you found uau in 100k? Look at the prime factors, so interesting. Lots of big primes and powers of 2. This makes sense, it means being Goldbug is related to number of prime non-divisors of n. Suggests maybe an analytic approach might yield some kind of lower bound? It also suggests that looking at large powers of 2 and even number of the form 2^k*p where p is large prime might ease the hunt for Goldbugs?



128=2^7
1718=2*859
1862=2*7^2*19
1928=2^3*241
2200=2^3*5^2*11
6142=2*37*83

[goldbug]

UAU, It looks like you are returning the maximal isolated set for each Goldbug? I noticed 128 actually has some of the subsets of the maximal sets satisfying the property as well.

I checked each of these (not each isolated set) and none of them are double Goldbugs since the n-p's contain unknown prime non-divisors.

An even number is a Double Goldbug Number of order k if there exists some k order subset of the prime non-divisors of n 2<p1<p2<...<pk<n such that (2n-p1)(2n-p2)...(2n-pk)(n-p1)(n-p2)...(n-pk) has only p1,p2,…,pk as factors

[Dr Sardonicus]

Originally Posted by ATH

If a,b has to be prime:
3² - 3 = 2³ - 2
13³ - 13 = 3⁷ - 3

otherwise:
6² - 6 = 2⁵ - 2
15² - 15 = 6³ - 6
16² - 16 = 3⁵ - 3
91² - 91 = 2¹³ - 2
280² - 280 = 5⁷ - 5
4930² - 4930 = 30⁵ - 30

I couldn't help but notice the pairs giving solutions to

x^3 - x = y^2 - y.

It suddenly occurred to me that this is an elliptic curve! So, I sicced Pari-GP on it. The group of rational points ("Mordell-Weil group") is generated by the point [0,1]. I checked the rational points obtained by repeatedly (up to 1000 times) adding and subtracting this point from [0] on the curve. The only ones with integer coordinates were

[x,y] = [0, 1], [1, 1], [-1, 0], [2, -2], [6, 15], [0, 0], [1, 0], [-1, 1], [2, 3], and [6, -14].

Assuming these are the only points with integer coordinates on the curve, we can quit looking at the exponent pair (2,3). This would force one of the exponents to be at least 4.

I also note that, for a given a and b (both integers > 1, and neither a positive rational power of the other), the power of b closest to a^m is b^n, where n is one of the integers bracketing m*log(a)/log(b)).

If |a^m - b^n| is supposed to be as small as |a - b|, this indicates that the fractional part of m*log(a)/log(b) is extremely small. The best way to look for this that I know is, convergents to the simple continued fraction for log(a)/log(b) -- especially if the numerator and denominator are small, and the next "partial quotient" is very large. As an illustration, the first four partial quotients to the simple continued fraction for log(13)/log(3) are 2, 2, 1, and 79. The first three convergents are 2/1, 5/2, and 7/3. The next partial quotient of 79 means that 7/3 is an especially good approximation for such a small denominator. This helps explain why |3^7 - 13^3| is so small. In any solutions in which a and b are of any size, my guess is that the simple continued fraction for log(a)/log(b) has a very few small partial quotients, followed by a real whopper.

[goldbug]

Sorry Dr. S, what are the implications of what you discovered? I am extremely interested but don't have the background to understand completely.

[goldbug]

I wanted to cross post this related question from mathexchange. I have run UAU's code up to 300k with no sign of new Goldbugs... certainly not the elusive Double Goldbug!



https://math.stackexchange.com/quest...oldbug-numbers

[Dr Sardonicus]

Originally Posted by goldbug

Sorry Dr. S, what are the implications of what you discovered? I am extremely interested but don't have the background to understand completely.

About all I've "discovered" is, some of the integer solutions to x^m - x = y^n - y (those with m = 3, n = 2) are on an elliptic curve. And although the rational points on this curve are known, I lack the background and expertise to tell whether the list of integal points already found is complete.

If it is, the case of exponents m = 3, n = 2 is done. The idea of approaching the problem from the standpoint of exponent pairs may help, or it may not. I'm not sure about the exponent pair (2, 4) but I suspect it can be dealt with by elementary means. It might also be possible to dispose of all cases where gcd(m,n) > 1 by elementary means.

The exponent pair (3, 4) might possibly be treatable with elliptic curves. But I suspect that, if one of the exponents is at least 5 (and the exponents aren't equal), the curve

x^m - x = y^n - y

has only finitely many integer points, by Faltings's theorem.

I imagine that one could also dispose of cases where |x - y| < B, where B is a constant (say, 2).

The continued fraction idea may be of some theoretical interest. From the standpoint of doing a numerical search for examples up to a given bound, however, I think that simply slugging it out with integer arithmetic as already suggested is probably best (assuming the bound isn't ridiculously large).

I also suspect that all the integer solutions have been found already. Unfortunately, such questions, though easy to state, are difficult to answer. The "Catalan's problem" of proving that 8 and 9 are the only consecutive integer powers went unresolved for many years. The problem at hand strikes me as being somewhat similar. It seems more a curiosity or novelty than being of great theoretical interest. If I happened to notice an elementary approach that settled the question, I'd be modestly happy.

But I would be much happier if I could prove that every even number is the sum of two prime numbers (i.e. prove the Goldbach conjecture).

[goldbug]

Has anyone seen this proof? If this was correct it wouldn't prove Goldbach for all numbers, just non-Goldbugs. Looks like there is also a way to extend to some Goldbugs?



https://www.linkedin.com/in/craigbeisel//

[goldbug]

See the latest puzzle involving Goldbug's algorithm here:


https://www.mersenneforum.org/showth...097#post502097


Have fun!