Distributed Beal Conjecture Problem - Page 4

CRGreathouse · 2009-04-24, 18:04

An array of ints would probably be faster, if you were willing to use 4 times the memory. Of course going above the 2-4 GB watermark might cause things to slow down; I'm not sure.

A bitarray might actually be faster than an array of bytes, and it's easy to use in C#: System.Collections.BitArray. This would probably reduce memory use below 500 MB.

Joshua2 · 2009-04-25, 09:20

I was wondering if you did something like that to get my source. I will trim it up a bit and post it tomorrow I guess on the website. I am not just storing a 0 or 1, I am storing a 0-255, to signify which part of the space the collision is in. Just because a^x + b^y mod n1 and mod n2 are both in the hashtable isn't a real solution unless they are both equal to the same c^z (even then it still wouldn't have to be, because they are only equal mod n1 & n2).

I tried using a int array, but it was slower. I would think that on a 64 bit computer long would be the fastest, but it wasn't. Maybe I wasn't doing it right. I should try a BitArray collections as an additional presieve that is smaller and might be faster.

R. Gerbicz · 2009-04-25, 19:03

A "very" close hit:
(9^4280+7639^1052)/2471^1204 = 0.9999999999946931842701194196

Joshua2 · 2009-04-25, 20:04

How did you come up with that? That would be in a range that hasn't been searched before. It isn't likely to find a solution with such big exponents, thats why I'm concentrating on the smaller ones first.

R. Gerbicz · 2009-04-25, 21:02

Quote:

Originally Posted by Joshua2

How did you come up with that? That would be in a range that hasn't been searched before. It isn't likely to find a solution with such big exponents, thats why I'm concentrating on the smaller ones first.

See http://robert.gerbicz.googlepages.com/beal.c

This is using a new idea: sort the powers in increasing order (store only their logarithms) and use that if a^x+b^y=c^z, then 1/2*c^z<=b^y<c^z (if we assume that a^x<=b^y), if we fix c^z then there is not too much cases for b^y and then it is a simple math to get the logarithm of a^x. This is faster then the old mod tricks. By the built-in eps=1e-10 the code is good up to bound=10^4. I haven't checked this, only started, then stopped, it would take about a day. It prints the close values to ki.txt file in a,x,b,y,c,z order one number in each line (consecutive sets are sepearted by a blank line). Not tested too much.

Note that i'm checking only gcd(a,b)=1, so it is possible that i'm printing a close hit for that gcd(a,c)>1 or gcd(b,c)>1 (obviously for a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1). And I excluded a,b,c=1 values (it is proven that those are not giving solutions, see Catalan's conjecture/theorem), because that are generating lots of errors in the code.

// needs about 1.5 GB Ram for n=10000

Joshua2 · 2009-04-26, 22:49

Nice. How long does it take to check all numbers a,b,c,x,y,z up to 1000? My program takes about an hour on my computer. When you talk about bound, is that checking all variables exactly up to the bound?

BTW this isn't a senior project, its a sophmore project for my AA at a community college. I think I get why a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1, but I read it works for a,c or b,c as well. It seems these two are the same case, but I wasn't exactly sure how this would be proved, and I wanted to double check.

R. Gerbicz · 2009-04-26, 23:05

Quote:

Originally Posted by Joshua2

Nice. How long does it take to check all numbers a,b,c,x,y,z up to 1000? My program takes about an hour on my computer. When you talk about bound, is that checking all variables exactly up to the bound?

BTW this isn't a senior project, its a sophmore project for my AA at a community college. I think I get why a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1, but I read it works for a,c or b,c as well. It seems these two are the same case, but I wasn't exactly sure how this would be proved, and I wanted to double check.

Yes, if you give bound then code is checking all 6 variables up to bound. For bound=1000 it takes about 1 minute on my Amd triple core, (it is using only one core). As I remember if you remove the gcd(a,b)==1 checking then you will get all false solutions also (for that gcd(a,b,c)>1), possibly multiple times, because the built-in log(1/2) value is only an approximation.

Joshua2 · 2009-05-02, 03:58

I got it to compile w/ Visual Studio 2008 c++, just had to make a (double) conversion explicit. So I don't really know c++; where does your program spend most of its time? Could you provide me a slightly more detailed explanation of what it does, because I would like to implement it in C#.

spkarra · 2009-07-15, 01:24

Quote:

Originally Posted by T.Rex

?? Java ?? When you want a very efficient program for Math, you use either C or/and assembler, I think. Not Java... Strange idea...

Hi,
I am tackling to get a counterexample in two ways. I wrote a JAVA program that gathers the data. Right now, I am gathering data upto 9999 integers on my laptop. Once its done, then I will run another JAVA code to review the data and find if there is atleast one set of numbers as a counter example.

-Sastry Karra

T.Rex · 2009-07-16, 19:12

Quote:

Originally Posted by spkarra

Hi,
I am tackling to get a counterexample in two ways. I wrote a JAVA program that gathers the data....

Hummm Since I know quite well both C and Java, since I wrote hundreds of thousands lines of code in C and Java, and since I knew very well how a Java Machine works, I'm sure the fastest language is C. However, using Java for managing the algorithms and C for coding them is fine. Just need to write JNI code.
T.

Joshua2 · 2009-10-18, 00:09

http://jjoshua2.googlepages.com/beal

I published the C# source code there towards the bottom of the page.

2009-04-25, 09:20	#35
Joshua2 Sep 2004 215₁₆ Posts	I was wondering if you did something like that to get my source. I will trim it up a bit and post it tomorrow I guess on the website. I am not just storing a 0 or 1, I am storing a 0-255, to signify which part of the space the collision is in. Just because a^x + b^y mod n1 and mod n2 are both in the hashtable isn't a real solution unless they are both equal to the same c^z (even then it still wouldn't have to be, because they are only equal mod n1 & n2). I tried using a int array, but it was slower. I would think that on a 64 bit computer long would be the fastest, but it wasn't. Maybe I wasn't doing it right. I should try a BitArray collections as an additional presieve that is smaller and might be faster. Last fiddled with by Joshua2 on 2009-04-25 at 09:21

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
The Beal Conjecture Proof	Arxenar	Miscellaneous Math	1	2013-09-07 09:59
Distributed NFS postprocessing	poily	Msieve	6	2012-12-05 12:45
New Beal Conjecture Search	Joshua2	Open Projects	0	2009-04-20 06:58
distributed.net completes OGR-25	ixfd64	Lounge	4	2008-11-22 01:59
distributed proofreading	adpowers	Lounge	10	2004-11-05 01:54

2009-04-24, 18:04	#34
CRGreathouse Aug 2006 5,987 Posts	An array of ints would probably be faster, if you were willing to use 4 times the memory. Of course going above the 2-4 GB watermark might cause things to slow down; I'm not sure. A bitarray might actually be faster than an array of bytes, and it's easy to use in C#: System.Collections.BitArray. This would probably reduce memory use below 500 MB.

2009-04-25, 19:03	#36
R. Gerbicz "Robert Gerbicz" Oct 2005 Hungary 3²·179 Posts	A "very" close hit: (9^4280+7639^1052)/2471^1204 = 0.9999999999946931842701194196

2009-04-25, 20:04	#37
Joshua2 Sep 2004 215₁₆ Posts	How did you come up with that? That would be in a range that hasn't been searched before. It isn't likely to find a solution with such big exponents, thats why I'm concentrating on the smaller ones first.

2009-04-26, 22:49	#39
Joshua2 Sep 2004 533₁₀ Posts	Nice. How long does it take to check all numbers a,b,c,x,y,z up to 1000? My program takes about an hour on my computer. When you talk about bound, is that checking all variables exactly up to the bound? BTW this isn't a senior project, its a sophmore project for my AA at a community college. I think I get why a solution gcd(a,b)=1 if and only if gcd(a,b,c)=1, but I read it works for a,c or b,c as well. It seems these two are the same case, but I wasn't exactly sure how this would be proved, and I wanted to double check.

2009-05-02, 03:58	#41
Joshua2 Sep 2004 215₁₆ Posts	I got it to compile w/ Visual Studio 2008 c++, just had to make a (double) conversion explicit. So I don't really know c++; where does your program spend most of its time? Could you provide me a slightly more detailed explanation of what it does, because I would like to implement it in C#.

2009-10-18, 00:09	#44
Joshua2 Sep 2004 1000010101₂ Posts	http://jjoshua2.googlepages.com/beal I published the C# source code there towards the bottom of the page.