Beta

# Slashdot: News for Nerds

×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

### Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

# Finding the First Trillion Congruent Numbers

#### timothy posted more than 4 years ago | from the after-that-it's-easy dept.

94

eldavojohn writes "First stated by al-Karaji about a thousand years ago, the congruent number problem is simplified to finding positive whole numbers that are the area of a right triangle with rational number sides. Today, discovering these congruent numbers is limited only by the size of a computer's hard drive. An international team of mathematicians recently decided to push the limits on finding congruent numbers and came up with the first trillion. Their two approaches are outlined in detail, with pseudo-code, in their paper (PDF) as well as details on their hardware. For those of you familiar with this sort of work, the article provides links to solving this problem — from multiplying very large numbers to identifying square-free congruent numbers."

cancel ×

### No Comment Title Entered

#### Anonymous Coward 1 minute ago

No Comment Entered

### What do you mean? (0, Offtopic)

#### Anonymous Coward | more than 4 years ago | (#29504533)

An african or european congruent number?

### Re:What do you mean? (2, Insightful)

#### MrNaz (730548) | more than 4 years ago | (#29505137)

It's neither, turns out it's a Muslim [wikipedia.org] congruent number!

### Re:What do you mean? (0)

#### Anonymous Coward | more than 4 years ago | (#29506121)

Iranian actually :)

### Re:What do you mean? (0)

#### Anonymous Coward | more than 4 years ago | (#29507073)

a) 900 - odd years before Iran existed.
b) There are Muslims in Iran.

### Re:What do you mean? (1)

#### clone53421 (1310749) | more than 4 years ago | (#29507253)

"African" and "European" are in reference to locations. "Muslim" is a religion, not a region.

Africa and Europe are not countries. Iran is. "Iranian" isn't fitting either.

"Middle-eastern" is the closest fit.

### Re:What do you mean? (1)

#### Rip Dick (1207150) | more than 4 years ago | (#29508645)

Persian sounds cooler...

I concur.

### 1 2 4 8 16 32 64 128 256 680 (-1)

#### Anonymous Coward | more than 4 years ago | (#29504545)

How fucking hard was that?

I'll be at the bar.

680?

### Re:1 2 4 8 16 32 64 128 256 680 (0)

#### Anonymous Coward | more than 4 years ago | (#29516399)

Nobody should ever need more than 680.

### Re:1 2 4 8 16 32 64 128 256 680 (1)

#### clone53421 (1310749) | more than 4 years ago | (#29516639)

You misquoted that:

Nobody should ever need more than 640.

Hence my confusion. 680 is more than 640!

### Why? (4, Insightful)

#### Stuart Gibson (544632) | more than 4 years ago | (#29504565)

I'm so not a maths geek, but why is this useful other than being able to say "hey, we found the first trillion congruent numbers"?

I know that certain branches are useful for cryptography purposes, but what awesomeness does this let us do?

### Re:Why? (4, Informative)

#### immakiku (777365) | more than 4 years ago | (#29504749)

Well math is usually all for fun anyway. And it seems like they're having fun. But here's where someone found an application: [url]http://en.wikipedia.org/wiki/Congruent_number[/url]. Please don't ask us to explain why elliptic curves are useful.

### Re:Why? (1)

#### immakiku (777365) | more than 4 years ago | (#29504761)

Eh I thought this was a forum. Sorry it's this [wikipedia.org]

### Re:Why? (2, Insightful)

#### wastedlife (1319259) | more than 4 years ago | (#29506853)

I was going to remark that this is a forum, and not all forums need to use BBCode syntax.

Then I realized I was being pedantic.

Then I remembered this is /.

So:

Forum != BBCode

### Re:Why? (2, Funny)

#### Eudial (590661) | more than 4 years ago | (#29510097)

\section{Re:Why?}

Well \emph{of course} not...

### Re:Why? (2, Funny)

#### MacAnkka (1172589) | more than 4 years ago | (#29514143)

This isn't a TeX document either. That would be just wrong.

After all, If we had a way to post readable formulas and uncommon chararacters, this wouldn't be the Slashdot comments section ;)

### Re:Why? (1)

#### wastedlife (1319259) | more than 4 years ago | (#29515421)

TouchÃ©, Slashdot handles uncommon characters just fine!

### Re:Why? (1)

#### Locke2005 (849178) | more than 4 years ago | (#29505751)

Can these congruent numbers be used to improve data compression? I seem to recall that IBM had patented a scheme using elliptical curves for data compression, but I don't remember the details.

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29506443)

I believe elliptical curves are also used in crypto. They are also are difficult to integrate iirc so this would also be a computational aid in some cases question mark?

### Re:Why? (2, Funny)

#### Hurricane78 (562437) | more than 4 years ago | (#29507647)

Can I then ask, what must have happened in one's life, that he considers that to be "fun"? ;)

### Re:Why? (1)

#### mdwh2 (535323) | more than 4 years ago | (#29510477)

Well math is usually all for fun anyway.

I think maths is fun, sure, but I do hope you're not suggesting that's all it's usually good for?

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29514559)

Please don't ask us to explain why elliptic curves are useful.

Elliptic curves might be useful since a lot of things move in a similar pattern. Like planets, comets, and spaceships.

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29530573)

Can you explain:

Why are elliptic curves useful?

### Re:Why? (3, Interesting)

#### BKX (5066) | more than 4 years ago | (#29504825)

According to TFA (I know, I know, we aren't supposed to do that, but I only skimmed it! I swear!!), this isn't particularly useful in itself, but the new techniques they had to develop to solve it are important. Specifically, they had to figure out news ways of multiplying numbers, since the numbers they wanted to multiply were larger than their hardware's main memory (OK, OK, a number that's trillions of bits long seems a bit far fetched to me too, but that's what TFA said.)

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29505215)

Specifically, they had to figure out news ways of multiplying numbers, since the numbers they wanted to multiply were larger than their hardware's main memory (OK, OK, a number that's trillions of bits long seems a bit far fetched to me too, but that's what TFA said.)

Maybe its more believable if you take into account the amount of memory taken by Windows Vista.

### Re:Why? (2, Informative)

#### Triela (773061) | more than 4 years ago | (#29505647)

> this isn't particularly useful in itself, but the new techniques they had to develop to solve it are important. Wiles' Fermat proof is a paramount example.

### Re:Why? (3, Informative)

#### Shaterri (253660) | more than 4 years ago | (#29506279)

Strictly speaking, there aren't any seriously new methods of multiplying numbers here; even the techniques they use for handling multiplicands larger than the computer's memory (sectional FFTs, using the Chinese Remainder Theorem to solve the problem by reducing modulo a lot of small primes) are pretty well-established from things like computations of pi, with this group offering a few improvements to the core ideas. What they did provide, and what sounds particularly promising, is a library (judging from the article, likely even open-source) for handling bignums like this that they've made available for general use. It'll be interesting to see if anyone else picks up this ball and runs with it.

### Re:Why? (2, Funny)

#### KingPin27 (1290730) | more than 4 years ago | (#29506687)

.... Specifically, they had to figure out news ways of multiplying numbers, since the numbers they wanted to multiply were larger than their hardware's main memory.....

Perhaps these are the guys that should have been working for Enron? I'm just sayin -- new ways of multiplying numbers...!

### Birch-Swinnerton-Dyer (5, Informative)

#### JoshuaZ (1134087) | more than 4 years ago | (#29504831)

Among other issues, which numbers are congruent numbers is deeply related to the Birch-Swinnerton-Dyer conjecture which is a major open problem http://en.wikipedia.org/wiki/Birch_and_Swinnerton-Dyer_conjecture [wikipedia.org] . This is due to a theorem which relates whether a number is a congruent number or not to the number of solutions of certain ternary quadratic forms.

The summary isn't quite accurate in that regard: The problem of finding congruent numbers is not completely solved. If BSD is proven then we can reasonably call the question solved. But it doesn't look like there's much hope for anyone resolving BSD in the foreseeable future. There's also hope that the data will give us further patterns and understanding of ternary quadratic forms and related issues which show up in quite a few natural contexts (such as Julia Robinson's proof that first order Q is undecidable).

### Re:Birch-Swinnerton-Dyer (4, Funny)

#### sconeu (64226) | more than 4 years ago | (#29505317)

But it doesn't look like there's much hope for anyone resolving BSD in the foreseeable future.

Of course not. Netcraft has already confirmed that BSD is dead.

### Re:Birch-Swinnerton-Dyer (1)

#### Netcraft Confirms It (1477201) | more than 4 years ago | (#29509599)

But it doesn't look like there's much hope for anyone resolving BSD in the foreseeable future.

Of course not. Netcraft has already confirmed that BSD is dead.

Yep.

### Re:Birch-Swinnerton-Dyer (0)

#### Anonymous Coward | more than 4 years ago | (#29505367)

Birch and Swinnerton-Dyer is dead. Netcraft confirms it.

### Re:Birch-Swinnerton-Dyer (1)

#### Hurricane78 (562437) | more than 4 years ago | (#29508085)

Ok then, but why is the Birch-Swinnerton-Dyer conjecture (whatever that is) in any way useful? (Honest question.)

### Re:Birch-Swinnerton-Dyer (2, Insightful)

#### Garridan (597129) | more than 4 years ago | (#29508897)

Caveat: I am not an expert on BSD, but my advisor is.

First place to look is here: http://www.claymath.org/millennium/Birch_and_Swinnerton-Dyer_Conjecture/ [claymath.org] . For one thing, the BSD conjecture implies that the title of this story is accurate. But, we don't even know that. Consider Fermat's last "theorem" -- the linchpin was a theorem "All Elliptic Curves are Modular" -- before that, we knew that modular elliptic curves behaved quite nicely, but we didn't know if there were other elliptic curves. To this day, we can prove remarkably little about very obvious-looking trends that we see in data about elliptic curves. Assuming BSD, many computations about elliptic curves are suddenly tractable.

Ok, but what does this have to do with the country's bottom line? Directly, I'd say "nothing". Indirectly, though, this is providing a lot of interest to American mathematicians. The current thinking is (hah) a bit of a trickle-down effect. As undergrads study, they gravitate towards the more interesting fields -- if math looks sexy, we get more mathematicians. The more mathematicians graduate, the more funding mathematics departments will get in a very direct way -- this gives us better teaching budgets, which should effect an increase in the number of good math teachers. The more good math teachers we have, the better our students will learn. That's the hope, anyway.

### Re:Birch-Swinnerton-Dyer (1)

#### JoshuaZ (1134087) | more than 4 years ago | (#29515871)

Well, it isn't directly useful but it contributes to our understanding of elliptic curves. Elliptic curves show up in a variety of useful applications, such as cryptography (this has been discussed on Slashdot before. See for example http://it.slashdot.org/story/09/07/12/1620240/New-Elliptic-Curve-Cryptography-Record [slashdot.org] ), and also for factoring large numbers (which is useful for both breaking crypto and for a variety of other purposes). Elliptic curves also represent a sort of border between the trivial and the impossible. The solution to Hilbert's Tenth Problem (http://en.wikipedia.org/wiki/Hilbert's_tenth_problem [wikipedia.org] ) implies that fourth degree or higher degree Diophantine equations are impossible to analyze in complete generality. Second degree equations have been well understood for at least a century. This leaves third degree equations as the interesting situation to resolve. In general, 3rd degree two variable Diophantine equations correspond to elliptic curves (glossing over some details here). So the study of elliptic curves helps us understand where exactly the border between tractable and completely not tractable lies.

### Re:Why? (1, Funny)

#### Anonymous Coward | more than 4 years ago | (#29504891)

It's how Derren Brown really predicted the lottery numbers.

### Re:Why? (1)

#### mdwh2 (535323) | more than 4 years ago | (#29510507)

In order to work out a trillion congruent numbers, they must be using some Very Deep Maths!

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29504935)

In the end it's all about world happiness. Actually this one seems more straightforward:

first trillion congruent numbers -> happiness.

vs

cryptography -> internet commerce -> buy a bean bag online -> nap in bean bag -> happiness.

### Re:Why? (1)

#### fifewiskey (1608023) | more than 4 years ago | (#29504967)

Haven't you seen the movie Pi?....math will allow us to predict the future of the stock market and give us a better understanding in regards to Kabbalah But in all seriousness, very interesting just don't see the practicality of this issue. But as someone already stated, I'm not a big math geek, I'm more of a wannabe and a poser.

### Re:Why? (0)

#### Anonymous Coward | more than 4 years ago | (#29505209)

yeah, god forbid someone does something out of sheer curiosity, nothing good can possibly come out of that.

### Re:Why? (1, Interesting)

#### Anonymous Coward | more than 4 years ago | (#29505487)

Statistical analysis of the prime numbers gave us the insight needed to find a formula describing an upper bound for their frequency.

Sometimes in order to make an important realization, you have to work through near-pointless crap for a long time, hoping it will pay off.

### Re:Why? (2, Interesting)

#### dcollins (135727) | more than 4 years ago | (#29505811)

"I'm so not a maths geek, but why is this useful other than being able to say 'hey, we found the first trillion congruent numbers'?"

I came here expecting to see this question, and was not disappointed.

The answer is: "For the same reason that people do crack."

Seriously. www.angrymath.com

### Re:Why? (1)

#### LandDolphin (1202876) | more than 4 years ago | (#29507169)

Math gives you a highly addictive mind/mood altering experience? Hmm... We must have tried different Math.

### Re:Why? (2, Funny)

#### jayspec462 (609781) | more than 4 years ago | (#29507613)

Math gives you a highly addictive mind/mood altering experience? Hmm... We must have tried different Math.

You are. The addictive one is called "Crystal Math."

### Re:Why? (1)

#### treeves (963993) | more than 4 years ago | (#29507703)

Math gives you a highly addictive mind/mood altering experience?

Yes, for certain values of "you". Apparently, you specifically are not a member of this set.

### Re:Why? (1)

#### gaspar ilom (859751) | more than 4 years ago | (#29506515)

Is it possible to create an algorithm that calculates the Nth "congruent number" in a tractable amount of time -- without having to calculate the intervening N-1 such numbers? (or having to do an exhaustive search up to the *value* of that number)

Is there another algorithm that given N and X (and a radix), can ascertain (yes/no) whether "X is the Nth congruent number"? Does the most efficient possible algorithm for this problem also necessitate calculating N congruent numbers, assuming the first one does?

That might be interesting.

### Re:Why? (2, Informative)

#### William Stein (259724) | more than 4 years ago | (#29508725)

It is an *open problem* to show that there exists algorithm at all to decide whether a given integer N is a congruent number. Full stop. It's not a question of speed, or even skipping previous integers. We simply don't even know that it is possible to decide whether or not integers are congruent numbers. However, if the Birch and Swinnerton-Dyer conjecture is true (which we don't know), then there is an algorithm.

### Re:Why? (2, Insightful)

#### Xest (935314) | more than 4 years ago | (#29513285)

The same reason you do any high level math like this, to figure out more, new math, because you might have to think up different ways of doing math to solve the problem at hand, or because when you do you might notice new patterns that are of relevance to solving other problems.

Ultimately any new techniques or patterns may be useful in themselves, or may go on to spawn other new techniques or patterns that are useful.

Math is a massive topic, and the more you explore it the more it grows, some of it is useful, some merely interesting to those with a mathematical mind, but it is experimentation with this practically useless math that often opens further doors to the practically useful. Sometimes the point is merely furthering math until the the point itself is found- that's how a fair bit of math has become useful overtime, the math came first, and then the application was realised after. Sometimes you need to stumble upon the solution first to know what problems it can fix!

### Finally, An Alternative To (-1, Offtopic)

#### Anonymous Coward | more than 4 years ago | (#29504911)

Listening to the whiners complain about Tom Delay [crooksandliars.com] . when there are bigger fish to fry IN Congress.

Yours In Astrakhan,
Kilgore Trout

### "outlined in detail" != "here's some pseudo code" (0)

#### NewbieProgrammerMan (558327) | more than 4 years ago | (#29504915)

Why don't they post their actual code? What good is it to tell me if you found the first trillion congruent numbers when you're hiding part of your methodology?

### Re:"outlined in detail" != "here's some pseudo cod (4, Insightful)

#### JoshuaZ (1134087) | more than 4 years ago | (#29504979)

They aren't hiding any part of their methodology. They've given more than enough details. Posting the actual code in the paper would be a distraction. When publishing new algorithms mathematicians generally outline it in pseudocode since this is a) easier to follow and b) much more useful for issues of proving formal correctness. I would not be at all surprised if you can find the code on the website of one of the authors and almost certainly the authors will provide the code details if you send them an email.

### Re:"outlined in detail" != "here's some pseudo cod (1)

#### NewbieProgrammerMan (558327) | more than 4 years ago | (#29505303)

Ok, so they do have this at the end of their paper:

A special thanks to David Farmer, Estelle Basor, Kent Morrison, Sally Koutsoliotas and Brian Conrey of AIMath for their careful preparation of a web page providing details of our computation for the general public.

which is refreshing. I'm guilty of assuming that most researchers are still adherents of the, "well I can't be bothered to make my code easily available for open scrutiny, even though all my paper's conclusions are based on numerics" mindset.

### Re:"outlined in detail" != "here's some pseudo cod (2, Insightful)

#### TheKidWho (705796) | more than 4 years ago | (#29505881)

That's because the programming itself is menial work. The algorithms are more important which the pseudo code describes well enough.

### Re:"outlined in detail" != "here's some pseudo cod (1, Insightful)

#### Anonymous Coward | more than 4 years ago | (#29506635)

I think programmers are prone to overestimating the value of actual code in scientific research, mostly because they know how much fun coding can be. Misunderstand me correctly here - I'm not saying how you implement something is irrelevant or not a matter of skill, but that when you are trying to write a scientific paper, the actual code you use to implement a specific algorithm is not all that interesting. It's sort of like the color of your shoes when you go to a job interview - it's really irrelevant to the goal you are trying to achieve unless you fsck it up completely and end up with iridescent footwear.

### Re:"outlined in detail" != "here's some pseudo cod (0)

#### Anonymous Coward | more than 4 years ago | (#29507025)

I believe your name actually speaks a lot about you now.

Pseudo-code is a trillion times more helpful to programmers than code in a language they potentially don't know.

### Re:"outlined in detail" != "here's some pseudo cod (1)

#### William Stein (259724) | more than 4 years ago | (#29508757)

I asked them before this came out, and they said they didn't want to post their code on the press release in order to avoid being slashdotted. Seriously. I think the code is certainly available upon request, and will be made available later when the hoopla dies down. Much of it is in FLINT [flintlib.org] , which is part of Sage [sagemath.org] .

### Re:"outlined in detail" != "here's some pseudo cod (1)

#### Garridan (597129) | more than 4 years ago | (#29509061)

Most of the code you'd want is in FLINT and MPIR. Every single author of the paper (with the possible exception of Mark Watkins) is a developer of open source software. You can find the disk-multiplication code here: http://sage.math.washington.edu/home/robertwb/disk_mul/ [washington.edu] , published under what looks like a BSD-like license. Their email addresses are public, and I'm sure they'd happily send you the source.

### Terrible summary (5, Informative)

#### theskov (556173) | more than 4 years ago | (#29504957)

They didn't find a trillion numbers - they found all numbers up to a trillion.

FtFP (From the F***ing Paper):

We report on a computation of congruent numbers, which subject to the Birch and Swinnerton-Dyer conjecture is an accurate list up to 10^12.

### Re:Terrible summary (2, Informative)

#### Intron (870560) | more than 4 years ago | (#29506037)

Although in the body it says they found 3,148,379,694 congruent numbers, the title is "A Trillion Triangles" and the web page is titled "The first 1 trillion coefficients of the congruent number curve" so I think you should let the lazy editors put their sandaled feet up and sip their lattes on this one. It's the article that's got it wrong.

### Re:Terrible summary (1)

#### camperdave (969942) | more than 4 years ago | (#29506517)

According to wikipedia [wikipedia.org] , a congruent number is a positive rational number that is the area of a right triangle with three rational number sides. Since there are an infinite number of positive rational numbers between every sequential pair of natural numbers, they could not possibly have found all the congruent numbers up to 1 trillion.

What they may have found is all of the congruent integers up to 1 trillion.

### Re:Terrible summary (1)

#### clone53421 (1310749) | more than 4 years ago | (#29506587)

According to wikipedia...

Maybe you should read it again...

In mathematics, a congruent number is a positive integer that is the area of a right triangle with three rational number sides.

### Re:Terrible summary (1)

#### camperdave (969942) | more than 4 years ago | (#29506705)

Someone just changed it then, because I copy/pasted.

### Re:Terrible summary (2, Informative)

#### clone53421 (1310749) | more than 4 years ago | (#29506921)

Hmm, that's correct. Today, in fact. I didn't realize.

However, this PDF [cms.math.ca] (the top result for Al-Karaji congruent -trillion [google.com] ) does support the edit:

A congruent number k is an integer for which there exists a square such that the sum and difference of that square with k are themselves squares.

### Slight correction (4, Informative)

#### mcg1969 (237263) | more than 4 years ago | (#29504993)

I don't believe they found the first trillion congruent numbers; rather, they tested the first trillion whole numbers for congruency.

### Not very impressive (-1, Offtopic)

#### Anonymous Coward | more than 4 years ago | (#29505053)

In soviet Russia, the first trillion congruent numbers find you

### 3,148,379,694 =/= Trillion (0)

#### Anonymous Coward | more than 4 years ago | (#29505055)

According to the article they found 3,148,379,694 numbers between 1 and a trillion that are congruent and not the first trillion numbers that are congruent like the summary suggests.

### Re:3,148,379,694 =/= Trillion (1)

#### LBArrettAnderson (655246) | more than 4 years ago | (#29505307)

That makes much more sense. With about 4TB of disk space between the two computers, it'd be difficult to store a trillion numbers (considering that they'd need to be more than 32 bit integers).

### Re:3,148,379,694 =/= Trillion (1)

#### Phurd Phlegm (241627) | more than 4 years ago | (#29505581)

That makes much more sense. With about 4TB of disk space between the two computers, it'd be difficult to store a trillion numbers (considering that they'd need to be more than 32 bit integers).

They might be stored as a bitmap. That would take only 10^12/8 = less than a terabyte of space. Or they might store them as successive differences, which would require only 3x10^9*8 = around 30 gigabytes. Of course, the latter would be a lot harder to work with. Depends on how you wanted to use the results, I guess.

### Hard Drive? (3, Interesting)

#### Diabolus Advocatus (1067604) | more than 4 years ago | (#29505095)

Today the limitations of discovering these congruent numbers is limited only by the size of a computer's hard drive.

Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?

### Re:Hard Drive? (4, Funny)

#### localman57 (1340533) | more than 4 years ago | (#29505265)

The rest was already full of pr0n. These guys don't get out much.

### Re:Hard Drive? (1)

#### localman57 (1340533) | more than 4 years ago | (#29505351)

Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?

Yeah. Cause I've already finished looking at the first 3 billion numbers...

### Re:Hard Drive? (2)

#### RobertB-DC (622190) | more than 4 years ago | (#29505361)

Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?

Yes, the explanation is simple. The non-technical writers who wrote "limited by the size of a computer's hard drive" have no freakin' clue how a computer actually works. Someone gave them a detailed explanation about the limits on multiplying large integers without resorting to "lossy" floating-point arithmetic, and the writer's head threw a fatal exception.

So by default, they said, "Some computer thing isn't big enough." And computers only have four parts: Screen (aka "computer"), keyboard, mouse, and Hard Drive. So it must have been the Hard Drive.

### Re:Hard Drive? (2, Funny)

#### wastedlife (1319259) | more than 4 years ago | (#29507171)

At least their Hard Drive works, mine wont turn on anymore after I spilled a little coffee in the cup-holder. Stupid foreign electronics.

Anyway, can't they just have the Geek Squad put in more Gigabytes?

### Re:Hard Drive? (2, Insightful)

#### pipoca (1142297) | more than 4 years ago | (#29511077)

Well, they are right in that it's bounded by memory. A number of languages let you do arithmetic on arbitrarily large integers. Rational numbers are basically 2 integers of random size, and if arithmetic functions for rationals aren't provided (as in e.g. common lisp or Haskell), they can be implemented. Sure, it might be slower (addition and subtraction is O(n)), but if you're a researcher and if you know the program is correct, you should be able to just leave the computer on for a week or two (or however long) to let it run.

More than that, this problem is embarrassingly parallel - each number doesn't change the result of any other, so you can very easily split up the work load on many computers, or write something that will run on GPU's or something. At a certain point, arithmetic will become too time expensive (because the number uses so many words of memory). So either you run out of memory first (unlikely) or things start to take to long. Possibly things will start to take to long when the numbers become larger then some cache, and the cache miss rate will drive your running time into the ground.

### Re:Hard Drive? (1)

#### KraftDinner (1273626) | more than 4 years ago | (#29505839)

I'm guessing it wasn't the Hard Drive, but actually the 128GB of RAM that is the bottleneck.

### virtual memory (-1)

#### Anonymous Coward | more than 4 years ago | (#29506021)

The 70's called. They want their unpagable memory architecture back.

### Re:virtual memory (1, Funny)

#### Anonymous Coward | more than 4 years ago | (#29506869)

The 80's called. They want their hacked paged memory architecture invented because of crappy small address buses back.

### Re:Hard Drive? (2, Interesting)

#### William Stein (259724) | more than 4 years ago | (#29508805)

I own the 128GB RAM, etc., computer that the second group did the computation on. I have a Sun X4550 24TB disk array (ZFS) connected to it, but I only allocated a few terabytes of space for a scratch disk. They were well into the calculation when I found out what they were up to (I was initially annoyed, since they were saturating the network). I think they were just being polite to me and the other users by not using a lot more disk.

### Re:Hard Drive? (0)

#### Anonymous Coward | more than 4 years ago | (#29509313)

Couldn't they just use a swap file?

### Re:Hard Drive? (1)

#### clone53421 (1310749) | more than 4 years ago | (#29506311)

Time was the limiting factor. They just didn't say that.

Given enough time, their algorithm would have been limited only by the size of the hard drive... but they didn't give it enough time to reach that limit. So, the hard drive was big enough.

### Re:Hard Drive? (0)

#### Anonymous Coward | more than 4 years ago | (#29506923)

Today the limitations of discovering these congruent numbers is limited only by the size of a computer's hard drive.

Can someone explain why they didn't use more than 2.7TB of HDD space if HDD space is the limiting factor?

The 2.7 TB hard drive was not the limiting factor. There were two teams and it was the 1.3TB drive that the other team had access to which was the limiting factor.

Of course we could have bought a bigger hard drive. But going twice as far would not have been as important as say going 1000 times as far, which it is our hope someone will take up the challenge to do.

### Re:Hard Drive? (1)

#### MooseTick (895855) | more than 4 years ago | (#29507351)

Maybe they only had a 2.7TB drive?

### Great work demonstrating important algorithms! (2, Informative)

#### onionman (975962) | more than 4 years ago | (#29505191)

This is a fantastic piece of work by some of the leading computational number theorists today. Most of the authors are involved in the Sage [sagemath.org] project in some form or another and their algorithms and code are driving the cutting edge of the field. Great work guys!!

### al-Karaji (-1, Troll)

#### Anonymous Coward | more than 4 years ago | (#29505259)

Wasn't he a suicide bomber?

Oh wait, no, he was one of the 19 9/11 hijackers.

### Misleading summary (1)

#### CrimsonAvenger (580665) | more than 4 years ago | (#29505673)

TFA says they have found all congruent numbers up to 1,000,000,000,000. It does NOT say that they found 1,000,000,000,000 congruent numbers.

### I feel so bad... (1)

#### FatdogHaiku (978357) | more than 4 years ago | (#29505851)

I read a headline saying "Finding the First Trillion Congruent Numbers" and I'm ashamed to admit I had no idea they were missing...

### For anybody who's curious... (2, Informative)

#### clone53421 (1310749) | more than 4 years ago | (#29506217)

I had to look up congruent numbers to make sense of the definition in TFS (I was thinking the "sides" of a right triangle meant only base and height, instead of all 3 sides of a triangle... needless to say this didn't make sense).

So, for the mathematically inclined, here's an explanation with as little English as possible.

Find all positive integers (1/2)bh where b, h, and sqrt(b^2 + h^2) are rational numbers.

They found all such integers = 10^16 (up to 1 trillion), not the first trillion such integers (as is incorrectly claimed). The reason for this error was that the article claims they used an algorithm to determine whether a number is congruent, then tested the first trillion numbers (some of them were congruent, some were not).

### Re:For anybody who's curious... (3, Insightful)

#### William Stein (259724) | more than 4 years ago | (#29508843)

That's a good explanation. I have to emphasize though, that they actually found all the congruent numbers up to a trillion only under the completely unproven hypothesis that the Birch and Swinnerton-Dyer conjecture is true. It's entirely possible that this conjecture is false, and some of the numbers they found are actually not congruent numbers. However, part of the conjecture is known (by work of Coates and Wiles -- the same Wiles who proved Fermat's Last Theorem), so we do know that all numbers they didn't list are definitely not congruent numbers.

### Re:For anybody who's curious... (1)

#### PingPongBoy (303994) | more than 4 years ago | (#29516479)

It's entirely possible that this conjecture is false, and some of the numbers they found are actually not congruent numbers

Surely a number less or equal to a trillion is testable for congruentness. The algorithm to test n would be find rational numbers x and y such that sqrt(x^2 + y^2) is rational and n = xy/2. It could be hard work for some of the numbers, but that's the whole point - to have done the work once and for all.

The claim is 3,148,379,694 congruent numbers were found - a finite number of numbers - so it would be just a matter of time to confirm them all. Would they even make the claim without checking every one of these?

### Re:For anybody who's curious... (0)

#### Anonymous Coward | more than 4 years ago | (#29529639)

There are some pretty big efforts underway to improve general algorithms which would be able to find explicit triangles for each of the numbers in the list. The current state of the art probably gets you to about 10^6 in some classes and 10^9 in other classes. The vast majority of numbers in the list are easy to prove congruent, unconditionally. But there are some numbers in the list which are quite hard. You need some very sophisticated algorithms indeed to even get you to 20. That's not 20 million or 20 thousand, but 20.

The interesting thing is, someone may well prove that an algorithm for deciding whether a number is congruent or not does not exist. No one is expecting that though because the BSD conjecture on which the list up to 1 trillion depends, has plenty of evidence for it, and is very likely true. If the BSD conjecture is proved, no further checking is necessary. The list to 1 trillion will be proved fully accurate. To put it another way, prove that any number in the list to 1 trillion is not a congruent number and BSD is proven false. The fact that mathematicians have not rushed out to try and find such a counterexample in this list demonstrates how confident mathematicians are that BSD is probably true.

Something important to note is that *if* a number is congruent, there is an algorithm to prove it is congruent. Simply search until you find a triangle. As the number is congruent, you will eventually find it, though the sun may die of heat death first. But the real question is, what happens if one of the numbers in the list is *not* a congruent number. Your algorithm will not ever finish. You might think, "oh, I searched and searched and didn't find a solution, so there probably isn't one". But how do you know if you didn't leave it running longer that one would turn up? You can't know that. The embarrassing thing is, we have no idea of an algorithm to decide. Even worse, we have no idea whether to expect that such a thing even exists. We can't prove that it does or doesn't!

### Misread one word (1)

#### jitterman (987991) | more than 4 years ago | (#29506459)

At first I read it as

An irrational team of mathematicians recently decided to push the limits on finding congruent numbers...

and thought, "I quite agree!"

### 1,000,000,000,000?? (1)

#### AmigaHeretic (991368) | more than 4 years ago | (#29507729)

...1,000,000,000,001 Ha ha!!

### can we finally outlaw irrational numbers now? (1)

#### peter303 (12292) | more than 4 years ago | (#29508035)

The ancient greek philosophers went into a tizzy when they discovered the hypotenuse of a unit square was not rational. The pythagorians incorrectly hoped the universe was rational. A trillion congruent numbers should be useful for any engineering purpose. You just normalize one side to unity.
Slashdot Account

Need an Account?

Don't worry, we never post anything without your permission.

# Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

• b
• i
• p
• br
• a
• ol
• ul
• li
• dl
• dt
• dd
• em
• strong
• tt
• blockquote
• div
• quote
• ecode

### "ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>