mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2018-12-05, 05:01   #23
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by goldbug View Post
# 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
uau is offline   Reply With Quote
Old 2018-12-05, 10:04   #24
goldbug
 
goldbug's Avatar
 
Dec 2018

1616 Posts
Default

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

101102 Posts
Default

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

1616 Posts
Default

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

Last fiddled with by goldbug on 2018-12-06 at 01:51
goldbug is offline   Reply With Quote
Old 2018-12-06, 14:49   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·277 Posts
Default

Quote:
Originally Posted by ATH View Post
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.
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-06, 18:52   #28
goldbug
 
goldbug's Avatar
 
Dec 2018

1616 Posts
Default

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

2×11 Posts
Default 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
goldbug is offline   Reply With Quote
Old 2018-12-07, 14:04   #30
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×7×277 Posts
Default

Quote:
Originally Posted by goldbug View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2018-12-07, 18:40   #31
goldbug
 
goldbug's Avatar
 
Dec 2018

101102 Posts
Default 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//
goldbug is offline   Reply With Quote
Old 2018-12-08, 20:11   #32
goldbug
 
goldbug's Avatar
 
Dec 2018

268 Posts
Default Goldbug's Algorithm!

See the latest puzzle involving Goldbug's algorithm here:


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


Have fun!
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 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.