mersenneforum.org Can you find another number like 2200?
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2018-12-05, 05:01   #23
uau

Jan 2017

79 Posts

Quote:
 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.
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[(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]

Last fiddled with by uau on 2018-12-05 at 05:43 Reason: Make list of primes actually maximal like claimed

 2018-12-05, 10:04 #24 goldbug     Dec 2018 1616 Posts 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 Last fiddled with by goldbug on 2018-12-05 at 10:06
 2018-12-05, 15:03 #25 goldbug     Dec 2018 101102 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 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
 2018-12-06, 01:50 #26 goldbug     Dec 2018 1616 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 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
2018-12-06, 14:49   #27
Dr Sardonicus

Feb 2017
Nowhere

2·7·277 Posts

Quote:
 Originally Posted by ATH If a,b has to be prime: 32 - 3 = 23 - 2 133 - 13 = 37 - 3 otherwise: 62 - 6 = 25 - 2 152 - 15 = 63 - 6 162 - 16 = 35 - 3 912 - 91 = 213 - 2 2802 - 280 = 57 - 5 49302 - 4930 = 305 - 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.

 2018-12-06, 18:52 #28 goldbug     Dec 2018 1616 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.
 2018-12-06, 18:59 #29 goldbug     Dec 2018 2×11 Posts Code to Search of k-order 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...oldbug-numbers
2018-12-07, 14:04   #30
Dr Sardonicus

Feb 2017
Nowhere

2×7×277 Posts

Quote:
 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).

Last fiddled with by Dr Sardonicus on 2018-12-07 at 14:07 Reason: Correcting awkward wording

 2018-12-07, 18:40 #31 goldbug     Dec 2018 101102 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 non-Goldbugs. Looks like there is also a way to extend to some Goldbugs? https://www.linkedin.com/in/craigbeisel//
 2018-12-08, 20:11 #32 goldbug     Dec 2018 268 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 MattcAnderson Puzzles 10 2017-05-21 01:52 allasc Math 0 2010-12-27 13:37 nibble4bits Puzzles 18 2006-01-07 10:40 Unregistered Math 11 2004-11-30 22:53 Fusion_power Puzzles 8 2003-11-18 19:36

All times are UTC. The time now is 14:49.

Tue Dec 1 14:49:50 UTC 2020 up 82 days, 12 hrs, 2 users, load averages: 1.72, 1.76, 1.91

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.