20181205, 05:01  #23 
Jan 2017
79 Posts 
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 (np) always belong to the set. Code:
#!/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[(ni)>>1] or [ni]: 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])) 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] Last fiddled with by uau on 20181205 at 05:43 Reason: Make list of primes actually maximal like claimed 
20181205, 10:04  #24 
Dec 2018
16_{16} Posts 
This is so amazing uau!?! So interesting...
I was going to say, Goldbach is true for second order Goldbugs since the np's can't share a factor with p, n, or 2np. But no idea what to do with these. It is very interesting to look at these examples since many of the np are p's, and some of the np's give unknown p's It would be interesting to find a Goldbug where the np's also contain only the p's as factors. I think in this case the np's might have to equal the p's? Maybe in that case n has to be prime and we can stop there... ;^) 128 p 2np Np 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 Last fiddled with by goldbug on 20181205 at 10:06 
20181205, 15:03  #25 
Dec 2018
10110_{2} Posts 
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 nondivisors 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 
20181206, 01:50  #26 
Dec 2018
16_{16} Posts 
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 np's contain unknown prime nondivisors. An even number is a Double Goldbug Number of order k if there exists some k order subset of the prime nondivisors of n 2<p1<p2<...<pk<n such that (2np1)(2np2)...(2npk)(np1)(np2)...(npk) has only p1,p2,…,pk as factors Last fiddled with by goldbug on 20181206 at 01:51 
20181206, 14:49  #27  
Feb 2017
Nowhere
2·7·277 Posts 
Quote:
x^3  x = y^2  y. It suddenly occurred to me that this is an elliptic curve! So, I sicced PariGP on it. The group of rational points ("MordellWeil 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. 

20181206, 18:52  #28 
Dec 2018
16_{16} Posts 
Sorry Dr. S, what are the implications of what you discovered? I am extremely interested but don't have the background to understand completely.

20181206, 18:59  #29 
Dec 2018
2×11 Posts 
Code to Search of korder Goldbugs
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...oldbugnumbers 
20181207, 14:04  #30  
Feb 2017
Nowhere
2×7×277 Posts 
Quote:
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). Last fiddled with by Dr Sardonicus on 20181207 at 14:07 Reason: Correcting awkward wording 

20181207, 18:40  #31 
Dec 2018
10110_{2} Posts 
Partial Proof of the Goldbach Conjecture?!?
Has anyone seen this proof? If this was correct it wouldn't prove Goldbach for all numbers, just nonGoldbugs. Looks like there is also a way to extend to some Goldbugs?
https://www.linkedin.com/in/craigbeisel// 
20181208, 20:11  #32 
Dec 2018
26_{8} Posts 
Goldbug's Algorithm!
See the latest puzzle involving Goldbug's algorithm here:
https://www.mersenneforum.org/showth...097#post502097 Have fun! 
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 