Distributed.net Finds Optimal 25-Mark Golomb Ruler

kpearson writes "Distributed.net's 8-year-old OGR-25 distributed computing project has just proven conclusively that the predicted shortest 25-mark Golomb ruler is optimal. 'The total length of the ruler is 480, with marks at positions: 0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480. (This ruler may alternatively be expressed in terms of the distance between those positions, which is how dnetc displays them: 12-17-10-33-19-...).' 124,387 people participated in the project and two people found the shortest ruler, one on October 10, 2007 and the other on March 24, 2008."

Comments

What

[Anonymous Coward]

What

Re:What

[Arch24]

116 comments and none have yet explained what the article is actually talking about. Thanx for nothing /. All I want is a little clarity plz. =)

Not Bush?

[erroneus]

Does this mean the optimum ruler is not Bush?

Re:Not Bush?

[tepples]

It means the optimum ruler is Gollum.

wtf

[Anonymous Coward]

i know we're all supposed to be nerds here, but this is way left of field. dont supposed you could have included a LITTLE more info in the summary as to what the fuck you're talking about?

Re:wtf

[Anonymous Coward]

According to the wikipedia article that was linked, a Golomb ruler is a set of numbers where no two pairs of numbers have the same distance. The "order" is how many numbers are in it, and the "optimal" ruler for an order is the one that ends on the lowest number.

So what they've found which set of 25 numbers - where the distance between any possible pair among them is unique - ends on the lowest number.

Re:wtf

[kestasjk]

Pfff, 25-mark. Wake me up when they get the 26-mark.

Re:wtf

[Anonymous Coward]

take note editors. it would not have been difficult to include something along the lines of the OPs first paragraph to make the summary read like an article, instead of a steaming pile of shit

Re:wtf

[AbRASiON]

How the fuck did this get a +4? I've never even been to university, nor have I done well in maths but as a /. reader I thoguht we all knew about distributed.net? Times certainly have changed, soon we'll see "how is babby formed?" posts on this place,...

Re:wtf

[Moochman]

Minor correction: a set of integers.

Re:wtf

[kpearson]

Pfff, 25-mark. Wake me up when they get the 26-mark. </unimpressedslashdotuser>

Instead of sleeping, why not help them find it?

Re:wtf

[Permutation Citizen]

This is not "way left of field". Slashdot reader are supposed to be interested in distributed computing.

I'm sure many of us participates (or has participated in the past) in one of distributed.net projects. It's true that there was no recent news from them since quite a long time.

Re:wtf

[jcelko]

I just did an article in the December issue of GAMES magazine on Golomb Rulers. You ought to be able to get it at any newsstand now.

Re:proved?

[martin-boundary]

Did I fail math class?

Yes. Yes, you did.

Re:proved?

[Cyberax]

Yes.

Re:proved?

[gardyloo]

Apparently so.

Re:proved?

[gardyloo]

Mathematics may be defined
as the subject in which we
never know what we are talking
about,nor whether what we are
saying is true.
--Bertrand Russell

Re:proved?

[bunratty]

You're thinking of science. You can only disprove a hypothesis, never prove it true. In math, you can prove or disprove a conjecture.

whatcouldpossiblygowrong

[IceCreamGuy]

I like how this is tagged "whatcouldpossiblygowrong," as if building a better radio antenna is going to bring about the end of the world. Oh, wait, I forgot that the movie "Pulse" was a documentary...

Re:whatcouldpossiblygowrong

[philspear]

It's always a valid if stupid question. What could go wrong? In this case, the 25-mark Golomb ruler may NOT be optimal, in which case you would have people using the 25-mark Golomb ruler, with... gasp... SUB optimal results. You might be asking yourself what that would look like. I really haven't the slightest idea what any of this is about, so I couldn't say.

But the tag gets onto any and all biology related articles, along with it's brother "iamlegend." Usually when it has nothing to do with curing cancer with dangerous viruses. A finding that DNA sequences prefer to associate with similar sequences? Some bright person asked whatcouldpossiblygowrong. The answer there is: nothing.

Re:whatcouldpossiblygowrong

[whimmel]

That's a myth. There are plenty of stupid people to go around.

Re:proved?

[socsoc]

thanks for the one real answer.... /where's my beer

What will be their next project?

[Anonymous Coward]

distributed.net used to have a very vibrant community, with several projects on-going at one time. But lately, things haven't been going so well for them. The prize funds for their RC5-72 challenge were recently yanked. And the only other project they had on-going was this OGR-25 project.

Does anyone know if they'll offer further projects in the near future? Many people I know have moved on to BOINC-based distributed computing projects, instead of sticking with distributed.net.

Re:What will be their next project?

[Anonymous Coward]

They are still offering the prize money, just not from RSA.

And they are going to begin OGR-26 soon.

Re:What will be their next project?

[Scott Carnahan]

It would be nice if there were distributed projects that were more closely linked to modern mathematics than the Golomb ruler computations. ABC@home is a start, but I'd be more interested in seeing something like a distributed expansion of tables like these fed into SAGE in an automated way. Other computations that might be useful include homotopy groups of spaces like spheres, Groebner basis calculations for various geometric objects, and knot invariant calculations, but I don't know how well these can be distributed. At any rate, I think building a freely accessible database of some sort is a more constructive use of computer time than brute-forcing single instances of ciphertext. Those sorts of challenges were a good cause in the 1990s, when people were fighting laws banning strong cryptosystems, but the good guys seem to have won that particular war.

Re:What will be their next project?

[steevc]

I ran OGR25 again for the last few months in hope of seeing that project complete. RC5-72 just seems pointless to me. We already know it will take decades without some radical improvement in processing power.

I've been disappointed by the lack of updates to the dnet site. Even now the projects page still says that OGR25 is active.

I've moved to Folding@home now as I hope it will have tangible benefits. My contribution is pretty minor as I don't have the hardware for GPU processing.

Re:What will be their next project?

[jandrese]

RC5-72 was completely pointless because I've never seen anybody use it. RC5-64 was at least forced on people due to export restrictions and other such nonsense (lots of early 802.11b cards for instance). The next step people take is typically AES, but brute forcing the AES keyspace is completely impractical.

Re:What will be their next project?

[sketerpot]

I've moved to Folding@home now as I hope it will have tangible benefits. My contribution is pretty minor as I don't have the hardware for GPU processing.

If you just have a CPU, then your spare cycles would probably be spent on some BOINC-based projects. I'm especially a fan of Rosetta and uFluids. Rosetta is another protein folding program, but unlike Folding@home it focuses on predicting the final protein structure from the genetic code, rather than simulating the folding process itself. And if you think labs-on-a-chip are cool, uFluids is designing better microfluidic devices with some enormous genetic algorithm. Those are harder to speed up with GPUs, so you could do more good there. The clients are also pretty convenient.

Re:What will be their next project?

[kpearson]

Their next project is OGR-26, as they announced today.

Re:What will be their next project?

[megabeck42]

Uhh, wrong wrong wrong. WEP, the nonsense encryption in 802.11 cards you described, uses RC4, not RC5. RC4 is a stream cipher, RC5 is a block cipher. Further, the distributed.net RC5-* efforts are trying to win a challenge set forth by RSA Labs, described here: http://www.rsa.com/rsalabs/node.asp?id=2100

The banner on the above page indicates that the challenges are no longer active.

Re:What will be their next project?

[jandrese]

What difference does it make how the data was run through the cipher? Does chunking the data up into blocks improve the security somehow, despite using the same crypto algorithm with the same number of bits?

And I've still never seen anybody use 72 bit encryption for anything ever.

To be fair though, 802.11's encryption wasn't even 64 bits, since defects in the WEP algorithm reduced it do a laughably weak 40 bits before the out and out bugs made it even more trivial to break.

Re:What will be their next project?

[steevc]

Thanks for that. I didn't realise how friendly the BOINC software was. Much easier to use than F@H. I've set it up on a couple of PCs and will see how it goes.

It's always a wrench to leave a project where you have built up some points, but I didn't have a huge amount on F@H.

Re:What will be their next project?

[megabeck42]

The difference is not how the data is run through the cipher. The difference is that there are two completely different algorithms. Think of RC4 as a truck and RC5 as an airplane. Yes, they're both vehicles, but they operate quite differently. Incidentally, an RC2 also exists.

Read the wikipedia articles on stream and block ciphers if you'd like more details.

Furthermore, WEP had a 24bit initialization vector intended to make brute-forcing keys harder. It was, unfortunately, flawed. Furthermore, as you must well know, in addition to the 64 bit (40bit key, 24 bit IV) mode of operation, there was a 128 bit (104bit key, 24 bit IV) mode.

Lastly, the point of the challenges was to get a real measurement of how hard those algorithms were to break. Essentially, they were offered as an experiment. Surely you can understand the value of the results.

Re:Story

[philspear]

The type of OCD that makes one check /.

Re:proved?

[philspear]

But you can't prove that, which proves his point.

so we get cheaper, better antennas?

[ClioCJS]

The Wikipedia page says One practical use of Golomb rulers is in the design of phased array radio antennas such as radio telescopes. Antennas in an [0,1,4,6] Golomb ruler configuration can often be seen at cell sites. Does this mean we can now construct larger antennas with greater sensing power, using fewer materials, due to knowing a larger optimal configuration than previously?

Re:so we get cheaper, better antennas?

[Pinckney]

Probably not. The [0,1,4,6] ruler is only order 4; we've previously known optimal rulers up to order 23. If larger configurations can be practically used, I would expect to see order 5 and higher already in use.

Re:so we get cheaper, better antennas?

[mblase]

Does this mean we can now construct larger antennas with greater sensing power, using fewer materials, due to knowing a larger optimal configuration than previously?

Probably not, since (a) optimal rulers of order greater than four but less than twenty have been known for some time, and (b) the [0,1,4,6] ruler is proven to be the largest perfect optimal ruler (according to the Wikipedia article).

Re:so we get cheaper, better antennas?

[SQLGuru]

Partly yes and partly no. (disclaimer, I only know what I read on Wikipedia -- much like you)

It sounds like an optimal Golomb ruler allows you to find the shortest that works (which would imply less materials [towers?]) but in this case, it was merely confirming the one that was already assumed to be the shortest. So, yes but no.

Layne

Re:so we get cheaper, better antennas?

[ClioCJS]

Thank you. So being "perfect" helps more in this situation than anything else?

Re:so we get cheaper, better antennas?

[Jsprat23]

As a hypothesis, if the distance from 0 to 1 is half a wavelength, the distance from 1 to 4 is 3/2 wavelengths and the distance from 1 to 6 is 5/2 wavelengths. These distances represent the first 3 resonances of a resonant dipole antenna. In the case of an antenna, perfect would mean capturing all of the resonances and thus be optimal.

Re:so we get cheaper, better antennas?

[mabhatter654]

it's essentially defines a list of numbers such that if you pick any two segments that are not the same segment they will always have different lengths. This is useful for things that involve harmonics.. radio, buildings, ect. where you need to build "imperfect" shapes. With antennas this is so that they don't interfere with each other in close proximity. With bridges you might need to make each length of bridge section a slightly different length to keep the bridge from vibrating to pieces. It's a list, highly useful to engineers of various types. Not that exciting, unless you really needed to have 25 critical measurements when 24 just wouldn't do.

Re:so we get cheaper, better antennas?

[oljanx]

the [0,1,4,6] ruler is proven to be the largest perfect optimal ruler (according to the Wikipedia article)

I'm not seeing that on en.wikipepdia, anyone know where I can take a look at that proof? Is it simple enough for someone to explain quickly?

Re:so we get cheaper, better antennas?

[Free the Cowards]

Wikipedia says:

There is no requirement that a Golomb ruler can measure all distances up to its length, but if it does, it is called a perfect Golomb ruler. It has been proven that no perfect Golomb ruler exists for five or more marks.

And then links to a page which contains the proof.

Re:so we get cheaper, better antennas?

[Anonymous Coward]

Your lack of comprehension saddens me.
An OPTIMAL ruler has no duplicated distances between marks.
A PERFECT ruler has every possible distance represented.
The Wikipedia article is fine, it's your reading comprehension that needs looking at.

Re:so we get cheaper, better antennas?

[fbjon]

No.
A GOLOMB ruler has no duplicated distances between any two pairs of marks.
A PERFECT ruler can measure every possible distance up to its length.
An OPTIMAL ruler is the shortest possible for its order (number of marks).

The 4-order ruler 0, 100, 400, 600 is neither optimal (there is a shorter one in a previous comment) nor perfect (can't measure e.g. the distance 4), but it is a Golomb ruler.

Re:so we get cheaper, better antennas?

[wings]

The referenced Wikipedia article indicates the use at cell sites needs a reference. Many sites on the internet quote the exact same phrase without any justification and to me, that raises a red flag.

I was curious to know why Golomb spacing would be used for antennas and found this article: http://kevingong.com/Math/GracefulGraphs.html. Scroll down to the bottom to the 'Significance' section. In short, a receiver with Golomb spacing of the antenna elements maximizes the phase angle information in the output of the array allowing the angle of the sender to be extracted with an FFT.

I should be possible to use this capability to transmit along a particular angle, but I would expect a more practical antenna for transmitting would have elements with equidistant spacing at a fraction of the wavelength. See here http://en.wikipedia.org/wiki/Phased_array.

Cell antennas I'm familiar with are sector antennas http://en.wikipedia.org/wiki/Sector_antenna optimized for coverage in a particular pattern (i.e. 90, 120 degrees) and not for transmitting or receiving along a particular angle.

Re:so we get cheaper, better antennas?

[sketerpot]

But why do the measurements need to be integers?

Re:so we get cheaper, better antennas?

[Big Hairy Goofy Guy]

Well, if you could use rational numbers, it would be impossible to have any optimal ruler, you could always just scale it down by a factor of two.

so instead of
0 12 29 39 72 91 146 157 160 161 166 191 207 214 258 290 316 354 372 394 396 431 459 467 480

you could have
0 6 14.5 19.5 36 45.5 73 78.5 80 80.5 83 95.5 103.5 107 128 145 158 177 .... you get the idea. (I hope)

This new ruler (with rational numbers) has the same order (same number of ticks) and if it isn't a Golomb ruler then the original isn't either. Since it is shorter by half, the original ruler isn't optimal. But this one isn't either, because we can do it again:

0 3 7.25 9.75 ....

(Check my math(logic) -- I've never heard of Golomb rulers before today, so I could easily make a stupid mistake)

Re:proved?

[Anonymous Coward]

What most people don't realize is that all of mathematics is based on certain assumptions, alternatively called axioms, postulates or definitions. Do all triangles have interior angles that add up to 180 degrees? Yes, but only if you make certain assumptions. That's called Euclidean geometry. There is also non-Euclidean geometry which is equally valid and is used to describe some systems in reality. Is there no highest prime? Does 2 + 2 = 4? Do parallel lines never intersect? Are no circles square? Yes again on all counts, but only if you make certain assumptions. So when we say that "x is proven" in mathematics then that is really shorthand for "x is proven based on certain assumptions". That doesn't stop some overzealous mathematicians from acting a little bit smug. I would like to point all smug mathematicians to Kurt Godel's incompleteness theorems.

Re:Story

[Raenex]

why the hell is everything tagged "story"?

I have another question. What happened to the option to turn off tags?

And one more: Is there any forum to discuss Slashdot issues? Seems like the only way is to bitch off-topic in the articles.

Re:Story

[johanatan]

Umm... 6 * 12oz > 40oz

Are you saying Bush has helped wean you off alcohol? Maybe it's because he's been there himself and you feel some sort of mystical connection to the man? :-)

Re:proved?

[johanatan]

I would ask a man who makes a statement such as that to 'prove' it.

Shouldn't have to

[ArchieBunker]

Headlines or summaries should be self explanatory.

can someone please tell me which #s aren't incl?

[ClioCJS]

Every number I plugged in could be measured as a length between 2 numbers in that set. But according to wikipedia, no perfect ruler exists for over 5. And this has 25. So it's not perfect.

So does anyone have a list of numbers that can't be measured as distances between these? I'd rather not calculate it myself.

Re:proved?

[socsoc]

Yeah... I meant the one "hey drunk guy, I think this is what you meant" answer.

apologies to all the yes men and for the record, my TI-89 did all the math for me...

Re:proved?

[johanatan]

Awesome point! I went through a lengthy argument with some mathematicians on here recently about cardinalities of infinite sets (specifically N, Q and the set of all primes). Their proofs of the equalities of these cardinalities (in my [and the finitist] opinion) are based some rather dubious assumptions (although there are subtle distinctions between my position and that of the finitist).

Hello, context???

[schamberlin]

That's got to be the most incomprehensible story summary I've ever seen posted to Slashdot, and that's saying a lot. Seriously. The predicted shortest 25-mark Golomb ruler is optimal? What on earth are you talking about? How about giving us the barest minimum of a context, so we might have some tiny clue what that spew of buzzwords is getting at.

Re:Hello, context???

[Anonymous Coward]

You really can't get more specific than that. Just because you don't know what a Golomb ruler isn't doesn't make it a bad summary. A summary has to assume some understanding of the subject at hand. If a summary includes mention of a photon, for example, it doesn't necessarily require that it be defined what a photon is in the summary.

Re:Hello, context???

[Galactic Dominator]

A summary has to assume some understanding of the subject at hand. If a summary includes mention of a photon, for example, it doesn't necessarily require that it be defined what a photon is in the summary.

That's the point of the criticism. A large majority of the readers here would be familiar with a photon, but not with a Golomb ruler.

Re:Hello, context???

[Hal_Porter]

Hopefully DHS agents will decide it is terrorist code and waterboard the submitter whilst asking him questions like "WHO IS GOLLUM?!", "WHAT IS OCR24?!" and the ever popular "WHO ARE YOU WORKING FOR?"

Re:Hello, context???

[this great guy]

The words "Golomb ruler" are displayed in a dark green color by your browser. Placing the mouse pointer over them usually transforms it in a hand. This is called an "hyperlink", or more commonly, "link". By clicking on it, you are redirected to a page from a site called "Wikipedia", a free, multilingual online encyclopedia project. This page explains what a Golomb ruler is. HTH.

Re:Hello, context???

[frieko]

Sure, but since there's a Wikipedia link right in the summary that does a wonderful job explaining it, this is just a simple case of RTFA.

Re:Hello, context???

[DAldredge]

If you don't know what one is google the damn thing.

Re:Hello, context???

[roguetrick]

Trick is though, the summary kind of makes us decide to click the link. One sentence of the applications would've been enough. Still, it didn't really bother me, as I already knew what a Golomb ruler was.

Re:Hello, context???

[this great guy]

I was trying to be funny. I agree a 1 sentence description would have been better.

Re:Hello, context???

[glwtta]

Sure, but since there's a Wikipedia link right in the summary that does a wonderful job explaining it, this is just a simple case of RTFA.

So, to understand the summary, and therefore decide whether or not I want to RTFA, I need to RTFA? You see where that defeats the purpose of the summary?

Re:Hello, context???

[Toonol]

This is Slashdot, we're supposed to be intelligent here. This means that while we may not know what a Golomb ruler is, we should be eager to find out, and competent enough to take the simple step necessary to do so... not complain that we aren't being spoonfed gently enough (even though posting that complaint takes more effort than the required click to actually find out).

Re:Hello, context???

[glwtta]

we should be eager to find out, and competent enough to take the simple step necessary to do so

Oh get off it. It's not about being "spoonfed", it's about writing a decent summary. When mentioning a relatively obscure topic (yes, yes, all real geeks know what a Golomb ruler is, etc) it's pretty much common sense to throw in a one-sentence description (so we at least know the general context), instead of, say, a useless list of numbers. I don't need you to tell me what I'm supposed to be eager to do, thank you very much.

As far as complaining goes, given that:
- that was a bad summary
- it is the job of an editor to improve on bad summaries
- Slashdot does have editors

It is at least theoretically possible that complaining can accomplish something. Theoretically.

Re:Hello, context???

[rfunches]

I tend to scan /. through Google Reader, so I don't get any of the hyperlinks normally found in the summary. I shouldn't have to link to the /. story to link to a Wiki entry on what is clearly an obscure topic.

Re:Hello, context???

[Anynomous Coward]

To further help you out, the arcane (not widely known) acronym (a list of letters where each letter is the first letter of a word in a sentence or part of it) 'HTH' posted (published on an internet forum) by the parent (the author of the post this post is reponding to) means: 'Hope this helps'. Note that the subject of the sentence is implied (the subject 'I' is omitted, but it is supposed that the reader can fill it in for him/herself).

HTH.

Re:Hello, context???

[Leynos]

I would have thought most /. readers would be familiar with distributed.net (what with all the beowulf trolls an' all). I know fuck all about crystallography, but I know roughly what a Golomb Ruler is from my past visits to the d.net site (and occasional participation).

So I do not agree that it is an obscure subject, at least in the context of Slashdot readers.

Re:Hello, context???

[Ctrl-Z]

If you think the story is something you might care about, and you don't know what it is, then read the article and then comment. If that's too much work, just move on to the next story. If you're not sure, then flip a coin. Not reading the article and then complaining that you don't know anything about the article is just being lazy.

Re:Hello, context???

[timbck2]

You really can't get more specific than that. Just because you don't know what a Golomb ruler isn't doesn't make it a bad summary. A summary has to assume some understanding of the subject at hand.

However, for anything written (summary, abstract, article, etc.) the audience should be considered, and the appropriate degree of explanation presented.

Re:Hello, context???

[cetan]

Why is it so difficult for people to click on a single link? Why do you need to be spoon fed everything? How about trying to think for yoursel for a change?

Re:proved?

[blue l0g1c]

Ah yes, the aptly-named "proof."

Re:proved?

[sunami]

But you can't prove that, which proves his point.

*HEAD ASPLODE*

Re:Story

[philspear]

Umm... 6 * 12oz > 40oz

That's true not only in terms of volume, but also price (it's an economy joke).

I would really like to understand this.

[ArbitraryDescriptor]

I read the article on OGR-25. I read the wikipedia article. The Fine article is sadly slashdotted, and I am still at a loss as to why this is useful, or.. difficult? I'm kind of at a total loss, if you want to get down to it.

Could a valid and perfect ruler not be made in the form of 0,1,3,6,10,15,21,28,36,etc to infinity?
Would it not be shorter than 480?
I'm clearly misunderstanding both requisite criteria and ultimate application; any help there would be appreciated.

Re:I would really like to understand this.

[Paco103]

no two pairs of marks are the same distance apart

0,3 -> Distance 3
3,6 -> Distance 3

0,6 -> Distance 6
15,21 -> Distance 6

That's where the problem comes. As you ad more numbers, sequences that were previously valid Golumb rulers are no longer because distances are repeates. It's not just the length between any adjacent pairs that cannot be repeated.

That being said, it's still hard to understand why we care. As has been pointed out above, we haven't found any practical use for any sequences above 5. Maybe someday we will though.

Re:I would really like to understand this.

[mabhatter654]

the application has to do with harmonics. For example the classic problem is that bridge that collapsed under wind load in the 40's. It collapsed partly because harmonics from the wind, just like a whistle, built up. Part of breaking harmonics is having a quick list of numbers that you can be sure won't duplicate. In a bridge you might pick your structural members to be just a little "off" using proportions from this list so that no two pieces were identical, one way of reducing vibrations in the structure.

Each length appears exactly once on the list and they can never be repeated unless you pick the exact same line segment.

Re:I would really like to understand this.

[Fex303]

Could a valid and perfect ruler not be made in the form of 0,1,3,6,10,15,21,28,36,etc to infinity?

No. Because the ruler looks at the distances between ALL the various makes on it. So in your example, it's invalid because the distance between 0 and 3 is 3 and the distance between 3 and 6 is 3. (Same issues with 0,6 and 15,21, etc.) You're aiming to find something where no two points are the same distance apart, not just adjacent points.

That said, I'm just going off the wikipedia article myself too, so if someone who knows better than me cares to comment, feel free to jump in.

Re:I would really like to understand this.

[Tomfrh]

It is a myth that harmonic resonance destroyed the Tacoma Narrows Bridge. A different phenomena was at work.

Re:I would really like to understand this.

[ArbitraryDescriptor]

Oooh. Ok, that's actually pretty interesting.
Thanks!

Re:I would really like to understand this.

[fbjon]

AFAIK, the cause was that it caught the wind too well, but that made it vibrate and resonate over the center span. Looking at videos of it, it's certainly not inharmonic resonance, since there's a fairly stable node right in the middle.

Re:I would really like to understand this.

[jc42]

the application has to do with harmonics. For example the classic problem is that bridge that collapsed under wind load in the 40's. It collapsed partly because harmonics from the wind, ...

People keep saying things like this, but the example doesn't make sense. If you look at the wikipedia article, the first 6-length optimal Golomb sequence is (0 1 4 10 12 17). We can see by inspection there are two adjacent segments, 4-10 and 10-12, whose lengths are in a 3:1 ratio. Thus, the latter's fundamental resonant frequency is equal to the second harmonic of the former's. Having one segment vibrating at a harmonic of another segment is what you're trying to avoid, and in this case, a Golumb sequence produces exactly that resonance.

So either you (and others) are wrong about this application, or I'm badly misinterpreting something. Which is it? How would using a Golumb Ruler help you avoid what it obviously produces in this case?

Now, I did notice that you wrote "pick your structural members to be just a little "off" using proportions from this list". But you could do that using pretty much any sequence, and get incommensurable results just as easily. For example, start with segments all the same length, and vary each length by a different amount. Or, using the properties of irrational numbers, you could make six segments have lengths proportional to the square roots of 31, 32, 33, 34, 35 and 36, thus guaranteeing no common harmonics to the limit of the precision of your measurements. It's not obvious that using a Golomb sequence instead of a list of integers gives you any advantage here.

What am I missing?

Re:I would really like to understand this.

[Tomfrh]

Yes it did vibrate due to the wind, but that isn't to say it was resonance.

The destruction frequency was not one of the bridges harmonic frequencies, nor was it the excitation frequency of the wind.

Also note that the bridge vibrated strongly across all wind velocities/frequencies, not just one or two special frequencies.

The phenomena that occurred was flutter, not resonance.

Re:I would really like to understand this.

[Big Hairy Goofy Guy]

You could build an Golomb ruler of any length you want pretty easily in a different way. Put ticks at 0,1,3,5,7,15,...2^{n}-1

(I think)
This is a Golomb ruler of order n with length 2^{n)-1. Proof: We need to show if we pick four tick marks, and the distance between the first two equals the distance between the second two then the points are equal.

Pick points nm and pq. Let's also assume that np.
I can assume nm because I measure distances between different points, and I can assume np because the pairs of points are different. (If n=p, and m!=q, then I'll have to renumber my ruler from the other end)

if (2^{m}-1) - (2^{n}-1) = (2^{q}-1) - (2^{p}-1) then

2^m - 2^n = 2^q -2^p, and then factor out the largest common power of 2, which is 2^n

(2^{m-n} -1} = (2^{q-n} - 2^{p-n}

m-n != 0, so the left hand side is odd. But q-n!=0 and p-n!=0 so the number on the right is even.

(2^{m-n} -1} =2^{p-n} * (2^{q-p} -1)

m-n != 0 (because nm) so the number on the left is odd.

p-n != 0, so the number on the right is even. This is a contradiction, showing that my n,m, and p,q cannot measure the same distance.

QED.

The problem is to get the order high, you have to have an exponentially longer ruler. Instead of length 480 for order 25, my ruler is 2^25 - 1 = 33_554_431

no two pairs can be the same distance apart

[schamberlin]

In your example, the distance between 0 and 3 is the same as between 3 and 6. Not a Golomb ruler.

I can do better than that...

[pottymouth]

My new yumiz ruler is perfectly calibrated in emh's and is 14.667 long. Now I'm going to go measure something like the how many pins can fit on one you guy's heads...

Re:can someone please tell me which #s aren't incl

[Anonymous Coward]

A few lines of Python suggests that there are 180 numbers that can't be measured, starting with 81, 90, 93, 103, 110...

Obviously the 11 numbers preceding 480 can't be measured, for example.

Re:can someone please tell me which #s aren't incl

[Pretzalzz]

Well, 25 choose 2 is 300 so presumably 180 numbers must be missing.

Re:can someone please tell me which #s aren't incl

[cavePrisoner]

479 is one if I understand the problem correctly

Re:proved?

[Merls the Sneaky]

You just reminded me of......

Ah, Kryten; just thinking. [Rapidly] Assuming of course we're not dealing with five-dimensional objects in a basic Euclidean geometric universe and given the essential premise that all geo-mathematics is based on the hideously limiting notion that one plus one equals two, and not as Astemeyer correctly postulates that one and two are in fact the same thing observed from different precepts, (Pulls a "nerdy" grimace, and loudly exhales through his nose.) the theoretical shape described by Siddus must therefore be a poly-dri-doc-deca-wee-hedron-a-hexa-sexa-hedro-adicon-a-di-bi-dolly-he-deca-dodron. (Pulls the same face, exhales a second time.) Everything else is poppycock. Isn't that so?

Re:can someone please tell me which #s aren't incl

[interiot]

Missing are: 81, 90, 93, 103, ... 476, 477, 478, 479 (180 different numbers missing total). The fact that it can measure all distances from 1 to 25 doesn't make it perfect, it has to measure all distances up to its length (480).

Re:can someone please tell me which #s aren't incl

[TBoon]

For starters, with 25 stops, there is 300 distances, so there has to be some numbers missing. To find which ones, I filled all the numbers into a spreadsheet, calculated the length/difference between all numbers, and then put that all together and sorted them. The lowest missing number is 81.

If you tried starting at the other end, you would have gotten results much quicker. Everything from 469 to 479 is missing. (Quite obvious actually, as the second and second-last numbers are 12/13 away from the ends.)

Re:proved?

[msuarezalvarez]

And pretty much everyone who gets the fact that Russel was making what amounts to essentially a joke in this context would ignore you...

Re:It hasn't been proven, it has been shown.

[gardyloo]

Yes, people routinely get this wrong. They're not wrong this time.

  In this case, the distinction between "it was proven" and "it was shown" is a distinction without a difference. In math, you can "show" something within a restricted domain; for example, that a postulated solution to a given equation really is a solution, without giving a complete family of solutions. One can show it numerically, or show it analytically. Here, a restricted set of postulated solutions over the only available domain (the positive integers) was exhaustively searched for actual solutions, and the set that satisfied the postulates was also shown to be optimal (in a well-defined sense for the problem).

    This is no more a "non-proof" than the proof of the 4-color map theorem in two dimensions, which was also "shown" using an exhaustive search.

Re:proved?

[panda cakes]

You are confused - there are no assumptions in mathematics because mathematics does not deal with any real entities. There are only definitions and what you are talking about applies to them: depending on your definitions properties of defined entities will differ. Quite a trivial conclusion most sane people already realize.

Re:proved?

[msuarezalvarez]

Assumptions cannot be dubious.

They may be not of your liking, but that hardly makes them dubious.

Bah, Humbug!

[Main Gauche]

There is a BIG difference between [proven and shown] as anyone within the Maths and the Sciences can tell you. I'm sorry, but people routinely get this wrong and it gets quite aggravating.

First, there is such a thing as proof by inspection. It may be considered inelegant by certain folks, but it's there nonetheless.

Second, it's just as aggravating (for those in certain fields) that computational results are not more valued. Sure, analytical results provide insight that computational results do not. But if you simply want to know the answer, why not accept a computational result?

Third, anticipating the old "how do we know the computer didn't make a mistake" comment: Theoretical proofs need to be proofread just as code does. So why not accept a computer program (and its verified output, as in the summary) as proof?

Re:cool!

[Dermah]

I was expecting you to measure the shit with a Golomb ruler. Oh well.

wut?

[slyborg]

parser: no such token "yumiz"
parser: no such token "emh's"
parser: all you pins are like the belong to us

very interesting

[ClioCJS]

I don't get how they know which resonances are the perfect ones to capture, though... Did someone just arbitrarily decide that? Does this coincide with music theory at all (octaves, harmonics, etc)?

Re:very interesting

[RealBothersome]

Think of the old police scanners that people used to use to monitor official business with. They needed an antenna that would be optimal at receiving a wide range of frequencies. If you could build a ground plane (omni-directional) that had a large numbers "stingers" that were optimal length, then you could have greater reception across a wide range of frequencies. In the example given above, you'd have one stinger at 1 measured distance for the high frequencies and half that frequency and 1/4 that frequency. Then, the second stinger at measured at the 1,4 measurement for another band of frequencies that has the 1, 1/2, 1/4 wavelengths. Then lastly, a third stinger that does the same for it's proper length. The triple stinger antenna could range 9 different bands optimally, and a 4 stinger antenna could range 12.

Re:proved?

[Futile Rhetoric]

Hasn't GÃdel done pretty much exactly that?

Re:proved?

[e9th]

Hey Bert, we need to talk about that Principia Mathematica thing.
Your pal, Kurt Godel.

Re:Story

[larry bagina]

after 8 years of Obama, will you be Joe MD 20-20 or Joe Colt 45?

That's enough of a proof

[khchung]

I am sorry, but listing out all possibilities (assuming that's what they did) and showing one is the minimum IS a valid proof for that minimum in that particular case.

For example, to prove "7 is a prime number", listing out 1,2,3,4,5,6 and then showing all are not a factor of 7 is a valid proof that "7 is a prime number". If you think this is not a proof, tell me which step in the proof is wrong.

Of course, whether the proof of Distributed.net is correct depends on how strongly they can prove their program actually covered all possibilities.

Re:That's enough of a proof

[stinerman]

Certainly.

The proof, however, is not very elegant. Unfortunately, brute force is the best tool we have for certain "hard" problems.

Re:That's enough of a proof

[Anonymous Coward]

It is an NP problem, so as long as they tried all possibilities, it should be correct.

Re:That's enough of a proof

[excelblue]

Two minor mistakes.

1.) 1 does indeed divide 7. So, you should only show that 2, 3, 4, 5, 6 does not divide 7.

2.) You need to state that numbers larger than 7 do not divide 7.

Re:That's enough of a proof

[PunkOfLinux]

Actually, I think you only need to go up to the halfway point. After that, if it were evenly divisible, it would have already been taken care of by something smaller.

Re:That's enough of a proof

[adavies42]

I am sorry, but listing out all possibilities (assuming that's what they did) and showing one is the minimum IS a valid proof for that minimum in that particular case.

For example, to prove "7 is a prime number", listing out 1,2,3,4,5,6 and then showing all are not a factor of 7 is a valid proof that "7 is a prime number". If you think this is not a proof, tell me which step in the proof is wrong.

The one where you claim 1 is not a factor of 7....

Re:That's enough of a proof

[martin-boundary]

2.) You need to state that numbers larger than 7 do not divide 7.

2. is a tautology and doesn't need to be stated.

No it's not. There are some number systems where this is false. So if you don't state 2., you'll have to state something which restricts you anyway.

Re:That's enough of a proof

[khchung]

Heh, I had a good laugh out of this stupidity myself...

Re:That's enough of a proof

[mangu]

The proof, however, is not very elegant.

Define "elegant".

Unfortunately, brute force is the best tool we have for certain "hard" problems.

Fortunately we do have more and more powerful brute force systems these days.

I don't agree with the definition that any brute force tool is "inelegant", or lacks "mathematical beauty". In those cases, one should try to find elegant brute force algorithms. For instance, I think the fast Fourier transform is a very elegant algorithm, because it's rather simple yet ingenuous and can bring a lot of acceleration in computing.

In the end, what is simpler, more elegant, and easier to verify: a few pages of computer program that find some result by computation, or several hundred pages of theoretical analysis proving that same result?

Re:That's enough of a proof

[martin-boundary]

In the field of integers modulo 103, the number 7 equals 10 * 11, since 10*11 (mod 103) = 110 (mod 103) = 7 (mod 103).

These kinds of number fields occur in lots of applications, eg in cryptography: fast factorization is the key to eavesdropping and will make you rich. Enough motivation for you? ;-)

Re:That's enough of a proof

[pla]

The proof, however, is not very elegant. Unfortunately, brute force is the best tool we have for certain "hard" problems.

I find a certain irony in that, however...

If you submitted an exhaustive proof (excluding pigeonholing) for an exam in a number/proof theory class, you'd most likely receive a rather poor grade for the lack of elegance, even if technically a valid proof.

Yet, the entire concept of a mathematical "proof" has no more noble underpinning than the more common meaning of the word - "An argument designed to convince someone else of the validity of my conclusion". We generally accept that, as long as you obey certain trivial and nearly-mechanical steps along the way, you have constructed a valid proof an any reader will accept it.

Yet, with some of the more complex proofs from the past few decades (particularly computer generated ones), a reasonable person can look at the 690 page printout of accepted operations and still not feel comfortable accepting the validity of the proof. OTOH, even an amateur can glance at an exhaustive proof and decide "yes, I accept this reasoning"

So overall, I'd have to call the idea of "elegance" (as applied to a specific proof) a load of donkey biscuits.

Re:That's enough of a proof

[kasperd]

Of course, whether the proof of Distributed.net is correct depends on how strongly they can prove their program actually covered all possibilities.

Interesting question. What if somebody were cheating? Maybe somebody wanted to give the impression that they did a large amount of computation, and modified the code to skip large parts of the solution space and report back no solution was found.

Re:That's enough of a proof

[martin-boundary]

You clearly have no clue what you're talking about. Try trolling somewhere else. Oops, I bit.

Re:That's enough of a proof

[Cowculator]

No, that AC is right. You can order a finite field (say Z/pZ) in some trivial way. But if c is the minimal element in this ordering, then any time you have an inequality a<b it won't be true that a+(c-b) < b+(c-b), so it's not an ordered field (which is an actual meaningful term). You clearly have no clue what you're talking about.

Re:That's enough of a proof

[jc42]

Actually, I think you only need to go up to the halfway point.

You're still working too hard. You only need go up to the square root. Your reasoning works just fine at that point.

Of course, as someone else pointed out already, this is assuming you're talking about the ordinary integers. If the data set is something like integers mod 2^N, for some N, the an integer may well have divisors that are greater than itself (for the obvious definition of "greater than").

Re:That's enough of a proof

[Zarel]

Two minor mistakes.

1.) 1 does indeed divide 7. So, you should only show that 2, 3, 4, 5, 6 does not divide 7.

2.) You need to state that numbers larger than 7 do not divide 7.

2. is a tautology and doesn't need to be stated.

Tautologies need to be stated; they simply don't need to be proven.

Re:That's enough of a proof

[Zarel]

Actually, I think you only need to go up to the halfway point.

You're still working too hard. You only need go up to the square root. Your reasoning works just fine at that point.

He was listing all the possibilities, i.e. a proof by exhaustive search. Sure, he could count up to the square root, then prove that all larger numbers cannot be a factor, but that wouldn't be "listing all the possibilities" anymore.

Re:That's enough of a proof

[martin-boundary]

No, the AC is wrong, and you're being too sloppy to see it. If for example you take Z/pZ with p prime, then all finite fields of order p are isomorphic to it, and Z/pZ has a natural order which is highly meaningful - it's just not fully compatible with the field operations, but that requirement is only in your mind, viz

In addition to what the AC above me said, you cannot order any finite field in a meaningful way, so your example is bullshit.

Don't read into his statement what isn't there, or presume things left unsaid. In mathematics, that's a recipe for a lot of grief.

If the AC wanted a point, he should have written things out carefully. But if he had taken the time to do so, he would have noticed that an ordering which preserves the operations is unnecessary to the factorization question in the first place, since it's merely a device for listing potential factors which can then be ignored. Any clever enumeration (oops, implied ordering) of the integers works too, for proving that result. And that makes his rationale pretty silly.

Ok, I'm bored now.

Re:That's enough of a proof

[jeek]

For example, to prove "7 is a prime number", listing out 1,2,3,4,5,6 and then showing all are not a factor of 7 is a valid proof that "7 is a prime number".

1 isn't a factor of 7? *THIS* gets modded "Informative"?

Re:That's enough of a proof

[stinerman]

If you submitted an exhaustive proof (excluding pigeonholing) for an exam in a number/proof theory class, you'd most likely receive a rather poor grade for the lack of elegance, even if technically a valid proof.

Indeed you would. I had a professor for Advanced Linear Algebra who was fond of docking points for proofs that were overly wordy albeit technically correct.

Why the hell does Gollum need a ruler anyway?

[unassimilatible]

The sumbitch spends most of his time in a dark cave.

And what the hell would he measure anyway? Not like he has any windows for drapes, my precious.

Re:Why the hell does Gollum need a ruler anyway?

[Bruce Perens]

They should call them Precious Gollum Rulers.

Re:Why the hell does Gollum need a ruler anyway?

[StarfishOne]

One needed to rule them all. :)

Re:Story

[Todd Fisher]

A forum!? You can take your fancy Web 2.0 "community" fad elsewhere. We've got Golomb rulers to discuss here!

Re:Story

[_xeno_]

why the hell is everything tagged "story"?

If you mouse over it (and have JavaScript enabled), you'll be informed that it's the "type tag." I assume the concept is that it differentiates between journals, comments, bookmarks, feed entries, and other types of nodes that could, conceptually, appear in the firehose.

I have no idea why Slashdot feels the need to show these on the main page, though, considering that everything that currently shows on the main page is a story. But if you play with the firehose, it's what tells you what "thing" the entry is.

Mathematically, this sounds like an excellent

[mmell]

candidate for use in an encryption scheme. Problems of class NP are especially useful in this area.

Re:Mathematically, this sounds like an excellent

[pjt33]

Not really. You need a function which is in P but whose inverse is NP-hard.

Re:Mathematically, this sounds like an excellent

[fatphil]

The knapsack problem wasn't. That was one of the biggest and most embarassing crypto flops since VENONA.

Re:Story

[Zadaz]

Is there any forum to discuss Slashdot issues? Seems like the only way is to bitch off-topic in the articles.

No, you can directly email them but of course they will only use that as ammunition to be taken out of context and savaged via the poorly conceived "Disagree Mail" "Feature".

I'd leave, but there isn't really an alternative that's better. Instead I use adblock and suck off this teat without providing benefit to the site. (Unless you include this post as "providing benefit" which is dubious since it will almost certainly get modded down.)

Re:proved?

[Dzimas]

LISTER: "Don't give me any of that 'Star Trek' crap. It's too early in the morning."

Pigeon

[Whiteox]

You don't need 8 years to design a ruler to measure a pigeon. That's just plain dumb.

yes!

[Dgawld]

Finally, Now I can sleep.

Re:proved?

[7 digits]

> You are confused - there are no assumptions in mathematics because mathematics does not deal with any real entities. There are only definitions and what you are talking about applies to them: depending on your definitions properties of defined entities will differ. Quite a trivial conclusion most sane people already realize.

*You* are confused and are mixing definitions and axioms. There are assumptions in mathematics, they are called axioms.

http://en.wikipedia.org/wiki/Axiom

Re:proved?

[panda cakes]

Even though the term "mathematical logic" contains the substring "math" it does not apply to the mathematics as the whole. Care to point at any assumptions in the mathematics, a single one would suffice.

Re:Story

[_xeno_]

i think posts of the "ask slashdot" "type" also currently appear.

There's an Ask Slashdot story on the main page, so, nope. "askslashdot" is a "system tag" and the "type tag" is still "story."

In fact, the only time I've ever seen anything not tagged "story" is in the Firehose.

RC5-72

[epine]

It's worth calculating the number of gigawatt-hours of electricity is expended on these toy problems. The original goal was to make a political point: we can't assume some of these codes are out of range with present technology. Having made your point, you're just boiling water to arbitrarily make the problem another order of magnitude more expensive to crack.

When did we decide that the major problem facing planet earth was a surplus of electricity we must burn off by any available method?

Re:RC5-72

[Anonymous Coward]

When did we decide that the major problem facing planet earth was a surplus of electricity we must burn off by any available method?

Oh, turn off your computer and go bug your neighbors about recycling, or something! God, these sanctimonious "think of the environment" pricks are annoying.

Re:can someone please tell me which #s aren't incl

[JustOK]

a few lines from Python would say

Then shalt thou count to three, no more, no less. Three shall be the number thou shalt count, and the number of the counting shall be three. Four shalt thou not count, neither count thou two, excepting that thou then proceed to three. Five is right out.

Re:cool!

[Anpheus]

Oh good, I wasn't the only one who read the entire thing waiting for a reference to (the) TFA.

Re:proved?

[Anpheus]

Completely unrelated, but I think the coolest shape name is the disdyakis triacontahedron.

http://en.wikipedia.org/wiki/Disdyakis_triacontahedron

Re:can someone please tell me which #s aren't incl

[fatphil]

Dammit! I had mod-points only 4 hours ago, but alas no more.

Re:Story

[glwtta]

If you mouse over it (and have JavaScript enabled), you'll be informed that it's the "type tag."

Actually, when I mouse over tags I get an incomprehensible mess of overlapping elements. It's probably my fault for using something as obscure as Firefox, though; I'm sure it works perfectly on IE6.

Re:Story

[philspear]

Not going to take the political bait, but I have to say I would be Joe Dead before I was Joe Colt 45.

Re:Story

[Anonymous Coward]

It works on Firefox 3 for me...

Re:proved?

[AikonMGB]

From XKCD: Certainty

Aikon-

You mean "angels"?

[Joce640k]

If you're trying to call us pinheads your ruler needs to be calibrated in angels.

Re:proved?

[7 digits]

One that easily comes to mind is the axiom of choice ( http://en.wikipedia.org/wiki/Axiom_of_choice ). I remember, during my math topology studies, having to actually assume the axiom of choice for certain demonstrations (ie: the demonstration would be invalid if you don't consider the axiom of choice true).

Such an axiom, can be chosen as true or false, but cannot be demonstrated. Nowadays, the axiom of choice is generally assumed (ie: the mathematics branches that we generally studies include that axiom), because there are so many results that depends on it.

Another classic is the parallel postulate ( http://en.wikipedia.org/wiki/Parallel_postulate ). It took hundred and hundred of years to finally prove that if you assume it as false you don't have any contradictions (just a different geometry).

Old news.

[leuk_he]

from the wikipedia hisotry:

The search for optimal Golomb rulers of order 25 currently underway by distributed.net (as of 2006) is predicted to confirm the following ruler, which was discovered in 1984 by M. D. Atkinson and A. Hassenklover.

1984... that is a lot of computer power for somethig that was already known... but just had to be proven

Re:Old news.

[Ilgaz]

In theory HIGGS particle should exist and standard model is true but dozens of countries and thousands of scientists have built the biggest machine ever known to prove it exists or not. If it doesn't exist, it will also serve to science too.

http://en.wikipedia.org/wiki/Large_Hadron_Collider

Re:Old news.

[leuk_he]

well, if it exists no anomalies are found then the LHC only is oldnews.

  But in the summary it looks like they found the optimal ruler, in reality they did just prove that the one discovered in 1984 was the most optimal.

Re:proved?

[panda cakes]

You are talking about definitions. The modern set theory deals with the sets for which the axiom of choice is true by definition (and thus it's called "axiomatic" vs "naive" theory which was trying to get away without definitions). Any field of mathematics deals with objects, properties of which are defined by such axioms. No other objects exist in mathematics. You can use different definitions to get different objects but you don't doubt your definitions. This was my point of objection vs. popular belief "oh you know, they thought parallel lines do not intersect but then discovered they do!". Nope, parallel lines as defined in Euclidean geometry still do not intersect however you are welcome to build another theory and define some other objects and call them "parallel lines" and define the property of intersection in such a way those objects of yours will always intersect but it will has nothing to do with the Euclidean geometry.

Re:proved?

[Lost Race]

Assumptions that seem to contradict each other might well be called dubious until proven otherwise.

Playing Cards Puzzle

[Skiron]

Years ago I saw a puzzle that is obviously based on this - get two suits, say Diamonds & Clubs. The idea is to arrange the cards in a horizontal line so the the aces are one card away from each other, the deuces two cards away from each other..., the 10's ten cards away from each other..., the kings 13 cards away from each other etc.

e.g. for starters:

3 1 2 1 3 2

It can be done with all 13 cards.

Re:can someone please tell me which #s aren't incl

[jonaskoelker]

#!/usr/bin/python
marks = [0, 12, 29, 39, 72, 91, 146, 157, 160, 161, 166, 191, 207,
                  214, 258, 290, 316, 354, 372, 394, 396, 431, 459, 467, 480]
unmeasurable = set(range(1, 481))
for i in range(1, len(marks)):
        for j in range(i):
                unmeasurable.discard(marks[i] - marks[j])
print sorted(unmeasurable)

Output:
[81, 90, 93, 103, 110, 111, 120, 139, 153, 171, 172, 174, 176, 183, 184, 192, 196, 198, 200, 204, 210, 213, 216, 220, 221, 223, 227, 231, 232, 238, 241, 242, 243, 247, 249, 254, 255, 256, 257, 259, 262, 264, 267, 269, 272, 275, 279, 280, 283, 284, 286, 288, 291, 292, 294, 295, 296, 297, 308, 309, 311, 312, 317, 318, 326, 327, 328, 329, 330, 331, 332, 335, 336, 337, 338, 339, 341, 344, 345, 346, 347, 348, 349, 350, 351, 352, 353, 356, 358, 361, 362, 363, 364, 366, 369, 370, 371, 373, 374, 375, 377, 378, 379, 380, 381, 383, 385, 386, 388, 390, 391, 393, 397, 398, 399, 400, 401, 403, 404, 405, 406, 407, 409, 410, 411, 412, 413, 414, 415, 416, 417, 418, 421, 422, 423, 424, 425, 426, 427, 429, 432, 433, 434, 435, 436, 437, 439, 440, 442, 443, 444, 445, 446, 448, 449, 450, 452, 453, 454, 456, 457, 458, 460, 461, 462, 463, 464, 465, 466, 469, 470, 471, 472, 473, 474, 475, 476, 477, 478, 479]

RTFL

[achurch]

Read The Fine Link from "Golomb ruler", and be enlightened. If you can make the summary more concise by moving some of it to a separate layer, then why not? The web is all about three-dimensional text, after all.

Precisely!

[rbarreira]

Exactly... I participated in RC5-64, but RC5-72 just seems pointless to me. It's the exact same problem, just 256 times harder.

Furthermore, these encryption challenges are not actually discovering anything. They're essentially brute-forcing a random number which another computer chose.

Contrast this with distributed computing challenges about mathematics (such as OGR-25 which is being discussed here), health or other issues where the result is something meaningful and potentially useful about the world.

Re:proved?

[chthonicdaemon]

Axioms are a lot more like rules than assumptions. You wouldn't say that an intricate forcing mate in chess is 'based on the assumptions of the game', it's the rules. So the axioms of Euclidean geometry are the rules of the game, and the game is finding consistent steps from one set of statements to another.

Unlike science, math has no reality connection. There is no requirement for math to portray reality or hold up to experiments or anything like that. Valid math is math that stays within the rules. The axioms define where we start, but there is no 'assumption' about the correctness of the axioms.

OK, here is a calculation

[rbarreira]

Let's assume the project will terminate when 50% of the keyspace has been searched. That's 2^71 keys to search.

A E6600 Core 2 Duo PC calculates about 17M keys per second according to a quick google search. This means around 1.4e14 computer-seconds to search 50% of the keyspace, or 3.85e10 hours.

A PC like this one uses around 150 watts, so it would consume 5,775,000,000 KWh of energy to search that keyspace.

Some different ways of visualizing this amount of energy:

• At $0.10 dollars per KWh, that's almost $600 million worth of electricity
• It's the energy contained in 600 million liters of gasoline (157 million gallons)

This of course doesn't take into account future improvements in CPU efficiency.

Re:OK, here is a calculation

[ari_j]

Your numbers are not quite useful. The question is how much more energy is used by running such programs than would be used without running them. Most people who run the clients for distributed computing projects leave their computers on 24/7. How much more energy does it take to run a whole lot of integer math versus to idle or run a screen saver?

Re:OK, here is a calculation

[rbarreira]

According to this page, the same PC I mentioned before uses up 40 more watts when under full load than when idling. That's about 27% of the 150 watts I mentioned before.

These figures are just ballpark numbers which give a rough idea. There are all kinds of people running these programs... Some make computer farms specifically to run them, some others don't buy new computers but leave theirs when they otherwise wouldn't, and then there's those who don't change their habits because of distributed computing. There's everything in between as well, making it very hard to estimate the real impact.

Re:proved?

[howlingfrog]

I thought you could only disprove, not prove math stuff...

Hypotheses in the empirical sciences can be disproven but not proven because they rely on observation--they make predictions, and the more you observe those predictions coming to pass, the more likely the hypothesis seems. But you can never know the difference between a hypothesis that never makes incorrect predictions and one that simply hasn't made any yet.

Mathematics, however, deals with statements that can be verified through rigorous deductive logic: a step-by-step reasoning process in which it is absolutely certain that each step leads to the next. That means that if your starting point is indisputable, your result is too.

Re:can someone please tell me which #s aren't incl

[whimmel]

The owl, too, only counted to three before reaching the Tootsie-roll center.

Re:Story

[Leynos]

I'm not very up on American beer (although I hear it's akin to sex in a canoe *baddum tish*), but here are my calculations:

For the six pack, I'm going to assume 4% abv. This would be a moderate strength lager in the UK. Therefore:

12oz * 4% * 6 cans = 2.88oz of ethanol

Now Wikipedia informs me that the median strengh of malt liquor in the US is 8% abv. Therefore:

40oz * 8% = 3.2oz of ethanol

Surely then the 40oz drinker is getting more bang for their buck?

As I say, I'm not too up on American drinking culture here, so please correct any mis-understandings or false assumptions I have made here.

Regards,

Leynos

-1, Misinformative

[howlingfrog]

Yes, the choice of axioms is somewhat arbitrary. But all the words you're using in your rhetorical questions are defined in terms of those axioms. The set-theoretic axioms (except for the axiom of choice) are all on the level of obviousness of "not (P or Q) means the same as ((not P) and (not Q))". They're as indisputable as indisputability gets. The words "prime", "two", "plus", etc., are defined in terms of those axioms, and the axioms demonstrate with absolute certainty that two plus two does equal four and there is not highest prime. Geometry is an unusual case where there are several non-equivalent choices of axioms in which you can define things like "parallel" and "triangle", but the definitions are not the same from one axiomization to another. A Euclidean-triangle is a fundamentally different object from a Riemannian-triangle. In either case, set theory or geometry, disagreeing with a proven statement requires redefining the words used in that statement. In other words, disagreeing with a fundamentally different statement, or, not actually disagreeing at all.

Furthermore, to the extremely limited extent that Godel's incompleteness theorem is related to your post at all, it contradicts you. It states that any sufficiently powerful (basically anything you can do number theory in) axiomatic system is either inconsistent (able to prove both P and not-P) or incomplete (able to express statements which cannot be proven or disproven within the system). It is possible to determine which a given system is. Set theory, for example, is consistent but not complete--same for Euclidean geometry and Riemannian geometry. You can also (at least sometimes) identify which statements are undecidable. So if a known-undecidable statement claims that no set can have a certain property, then the fact of its undecidability tells us that we'll never find a counterexample: that there is no such set. In other words, the nonexistence of that kind of set is true but not provable. Godel formally proved that there is such a thing as mathematical truth beyond mere provability. He proved Platonism: the claim that mathematics is (in some sense) real, not just a game that mathematicians play with symbols on paper.

Bah.

[Evets]

You can't measure anything larger than 467 with this thing.

Some clarity

[azav]

This says what a Golomb ruler is.

http://www.distributed.net/ogr/

Yet nothing in this article or link says "why should we care what it is?" Who uses Golomb rulers? What are they used for?

Re:Some clarity

[john83]

This sort of construct has idea autoambiguity properties, which means that it doesn't look like shifts of itself. There are lots of communications and sensing applications where that sort of thing is useful. I've published on a related topic called Costas arrays, on which Golomb also did the key work. The advantage of having the extra data point probably isn't all that practical for people using these things in applications, but for mathematicians working on their properties, it could help them find a new pattern which might lead to a new algebraic construction method, or a new constraint which might make searching for these things more efficient, or just provide some insights in pure mathematics.

Re:proved?

[7 digits]

> Any field of mathematics deals with objects, properties of which are defined by such axioms. No other objects exist in mathematics

I welcome you to study Kurt Godel

> "oh you know, they thought parallel lines do not intersect but then discovered they do!". Nope, parallel lines as defined in Euclidean geometry still do not intersect

That is a strawman. The controversy was that the // axiom was believed to be a consequence of the other 4 postulates/axioms. In the 19th century it was proven that it wasn't the case, and that it really was an independant axiom. So, in Euclidian geometry, there is the assumption that // don't cross.

I am not going to pursue this discussion, as you'll obviously keep playing on words.

Furthermore, as you believe that axioms are definitions, you should go straight to wikipedia and update the axiom page (oh, and do the postulates, propositions and theorems pages too). Let us know how well it goes.

had to be said

[waltlaw]

I for one welcome our new Golomb Ruler!

Re:proved?

[7 digits]

> Axioms are a lot more like rules than assumptions

When you are "in the system", you view your axioms as the kernel of truth.

You chess example doesn't really relate to the discussion, as chess is much simpler than math, and all truth can be deduced from the rules + a gigantic computer. Godel proved that it wasn't the case in math -- to Russell dismay...

But I can't resist a chess analogy :-)

> You wouldn't say that an intricate forcing mate in chess is 'based on the assumptions of the game', it's the rules

but nobody plays like that. The bishop sacrifice on h7, for instance, is based on the assumptions of the game (if you have your Nf3 and the castled rook is on f8, and a few other things, you just sacrifice without calculating -- an axiom of chess will tell you that it'll gain you something).

And then, you'll have a lot of additional axioms, controlling the 7th rank with two rooks, as a key to victory, good bishop vs bad bishop, bishop pair, control of files, etc, etc...

Those are not in the rules, but are truth nonetheless. And if you look at, for instance the hypermodern chess players (Reti, Nimzowitch) against the classical ones (like Tarrasch), you'll see that they really play with different assumptions.

OGR-26 already begun!

[TeknoHog]

They have just started OGR-NG which will search for 26-mark and higher-order rulers. For now you will have to use a prerelease client.

http://n0cgi.distributed.net/cgi/dnet-finger.cgi?user=bovine

http://www.distributed.net/download/prerelease.php

The shortest ruler wins?

[Brad1138]

Farquaad?

I'm impressed ...

[ScrewMaster]

Distributed.net Finds Optimal 25-Mark Golomb Ruler

that this summary managed to garner 208 comments.

Re:proved?

[Ann Coulter]

Definitions are essentially shorthands for saying something that would expand textbooks by a considerable amount. Axioms are true statements within a theory. Here are some examples:

Definition.
A prime number is an integer $p > 1$ such that if there exists positive integers $a,b$ such that $p = a b$, then $a=1$ or $b=1$.

Axiom.
If a subset $K$ of the natural numbers contains $0$ and if a natural number $n \in K$ and the proposition $S(n)$ being true implies $n + 1 \in K$ then $K$ contains all natural numbers.

If one were to use an theory such as Peano arithmetic with the construction of the integers, then the definition of prime numbers makes no statement. It is entirely valid to negate the definition by saying that a prime number is not what was defined and still every theorem in the theory will be valid.

If one were to negate the axiom of mathematical induction within the theory of Peano arithmetic then conceivably either many theorems will be invalid or the entire theory will be inconsistent.

Re:proved?

[ari_j]

Prove it.

LOGIC COMPILER ERROR: Out of pronouns. Reverting to proper nouns.

Disprove the hypothesis that martin-boundary can prove that socsoc failed math class.

Not at all (and /., get on with UTF-8)

[Nicolas MONNET]

Goedel has proven that there are some statements that are not provable as either true or false. Doesn't mean that everything is unprovable, obviously.

Re:proved?

[mindstrm]

Wait, wait.. so math is not science?

Thanks...

[hansendw]

Thanks, for posting an interesting article about something I knew nothing about. I was happy to follow the link and learn something new. Which.....is why I lurk here.

Re:Thanks...

[kpearson]

Thanks, for posting an interesting article about something I knew nothing about. I was happy to follow the link and learn something new. Which.....is why I lurk here.

Thanks for un-lurking and giving your positive feedback!

Compression of a ruler?

[memco]

Basically this thing contains the fewest number of marks that can be etched onto a ruler and still allow you measure all shorter (integer distances)? This is the kind of efficiency that most people would call stupid or way more complicated than it needs to be. Worst ruler ever!

A primer on corporations

[unassimilatible]

The difference is of course, that Apple and MS are not people.

Corporations are investment vehicles for people. They represent the interests of people. These people are called "stockholders." This is how the average Joe (70% of US equities are held by the small investor) can pool his resources with other people and get part of the Dream. Like my parents. My dad is a former middle class salesman who was "retired" early due to an on-the-job disability. Thankfully, my parents got into Apple at a good price, and the stock has been a stellar performer for their golden years.

Although personally, I'm not particularly statist about Apple and Microsoft. I just wish they would stop being cunts.

Now, if only other people like yourself would understand that corporations are not, in fact, entities in and of themselves, but represent the interests of stockholders. Not employees, not customers, not Slashdotters who don't believe in patent or copyright, but the interests of those who entrusted their money to the corporation. So keep your hands and laws and regulations off of other peoples' money, if you please. If you don't like the iTunes DRM, don't buy an iPod.

You are entitled to your opinion, but at least understand why Apple does the things it does - to increase shareholder value. And they do it well. So please don't tell other people how their business should be run. Go invest your money with Red Hat or something, or buy an open-source media player. But disparaging Apple because it doesn't do what you want is like being mad at your neighbor's wife because she doesn't make you dinner at night. It's not her job. And if she makes your neighbor great dinners that you have to smell every night, don't be a hater; congratulate your neighbor on finding a great wife. Then go find one that meets your needs. Because the relationship between your neighbor and his wife is none of your goddamned business!

Re:A primer on corporations

[Leynos]

I fully understand that corporations are composed of people and they act in the interests of shareholders. But that doesn't make a corporation a person (despite what the legal definition states).

A person who makes an informed decision to be a greedy bastard is fair enough (though they don't have my respect).

A corporation on the other hand, having a contractual obligation to maximize shareholder profits, is acting blindly in the interests of greed. It cannot see the consequences of its own actions.

There are a lot of things Microsoft does, but I can't really argue with. Similarly with Apple.

I don't own an iPod, and I have no interest in buying an iPhone. Someone who enters into a contract with Apple and gets fucked over as a consequence of the document they signed and didn't read deserves everything they get.

Someone who buys a copy of Windows shouldn't bitch about the consequences. (Oh well, I do, but I have no real right to. If I didn't want the consequences, I shouldn't have bought Windows.)

I like to think I invest ethically and make informed purchasing decisions.

I just think that blind free market capitalism, with little or no incentive to "be nice" is dangerous at the present point in time.

Re:proved?

[panda cakes]

18th century called - they wanted their naive mathematics back. If you negate a definition then every theorem dealing with this definition becomes invalid. This is how modern mathematics works.

Re:proved?

[Ann Coulter]

If a prime number is defined to be any integer that is either equal to $0$ or $1$, then every theorem that deals with integers, $p>1$ such that if there exists positive integers $a,b$ such that $p = a b$, then $a=1$ or $b=1$, will still be perfectly valid.

Re:proved?

[panda cakes]

Sorry, I don't see your point. If I define real numbers somewhat different or just say that real numbers don't exist then still every theorem dealing with integers is valid. So? Theorems dealing with real numbers are not. Likewise if you meddle with integer number definition your integer theorems will not be all correct any more.
How does the stuff you posted prove mathematics is based on some assumptions?

Re:proved?

[Ann Coulter]

You seem to not understand the notion of notation or believe that mathematics is based solely on notation.

Re:It hasn't been proven, it has been shown.

[Secret Rabbit]

There actually is a BIG difference between proving something and showing it. There is no context that would change that. Equivalence and equality are *not* the same thing. Just getting the same result doesn't mean that you got there the same way.

Namely, that through a "show" one _only_ gets that particular result and pretty much ends up in a dead end. And even then, only an exhaustive search would get if the result is unique or not. It is a "dumb" result.

On the other hand, proofs are *much* more deep. Beside the generality (if even as specific as this result) there is the proof technique that was used. Terry Tao has said that the proof technique is regularly more important than the result itself. Which is rather obvious given that the technique can be reused whereas the result has limited areas of applicability. One also will find during the proof, that there are implications for further research. I could go on.

But, that isn't to say that Numerics isn't useful. One need only look to Experimental Mathematics to see that it is. But, that still isn't a proof. What they do is analysis to see if there is anything to something that we aren't seeing. *Then* they go in and actually *prove* something based on that. It's similar to the relationship between Experimental and Theoretical Physics.

But, to say that there isn't a difference between the two is inane.

Re:It hasn't been proven, it has been shown.

[Zarel]

    This is no more a "non-proof" than the proof of the 4-color map theorem in two dimensions, which was also "shown" using an exhaustive search.

I agree with you on your other points, but this? I'm pretty sure the proof of the Four-Color Theorem I know was proven by induction, not exhaustive search. Kind of hard to prove a theorem that applies to infinite situations with exhaustive search, don't you think?

Re:It hasn't been proven, it has been shown.

[gardyloo]

The "infinite situations" you reference were shown to be equivalent to a collection of two different sets:
      i) a set of 1936 (originally; later this was reduced to 1476 of them) maps. Each of these maps were checked one-by-one;
    ii) a set of counter-counter-examples, which also had to be checked one-by-one.

    Each of the successful proofs of the 4-color theorem has required the same sort of exhaustive search over these two kinds of sets (that I know of).

Re:It hasn't been proven, it has been shown.

[gardyloo]

But, to say that there isn't a difference between the two is inane.

To say that I asserted that is inane. In some cases (as in the case that the original story referenced) there *is* no difference. An exhaustive numeric search provided a proof of the original assertion.
      I'm not saying that numerics and analytical proofs are always the same (as they very often are not).

Re:It hasn't been proven, it has been shown.

[Zarel]

The "infinite situations" you reference were shown to be equivalent to a collection of two different sets:

      i) a set of 1936 (originally; later this was reduced to 1476 of them) maps. Each of these maps were checked one-by-one;

    ii) a set of counter-counter-examples, which also had to be checked one-by-one.

    Each of the successful proofs of the 4-color theorem has required the same sort of exhaustive search over these two kinds of sets (that I know of).

Oh, whoops, I was thinking of the Five Color Theorem, which is a lot easier to prove by induction.