Proposition of new subproject: Odd Weird Search

[fwjmath]

Hello everyone,

I would like to propose a new possibility of subproject. It is a number-theoretic subproject searching for odd weird numbers (http://en.wikipedia.org/wiki/Weird_number).

Let me first briefly define weird numbers.

For a number N, if the sum of all its proper divisor is greated than itself, then it is called an abundant number. For example, 8 is not an abundant number, since its proper divisors are 1, 2 and 4, and 1+2+4=7<8. 12 is an abundant number, since 1+2+3+4+6=16>12.

An abundant number is a weird number if no subset of its proper divisors sums to itself. For example, 12 is not a weird number, since 1+2+3+6=12. 70 is a weird number. Its proper divisors are 1,2,5,7,10,14,35, which sums to 74. If there is a subset of proper divisors that sums to 70, its complement will have a sum of 4, which is clearly impossible, therefore 70 is a weird number.

Here is the OEIS page for weird numbers: https://oeis.org/A006037. It also contains a list of known weird numbers. It is worth noting that every number in the list is even.

In fact, no odd weird number is known. Previous effort searches up to 10^17. The great mathematician Paul Erdos offered a 10$ prize for finding an odd weird number, and a 25$ for a proof of non-existence. We may conclude that Erdos thought an odd weird number should be more probable to exist, and the problem is interesting enough for Erdos to put money in it, since he is known for have money prizes for unsolved mathematical problems.

We would now like to continue this effort of searching for odd weird numbers.

I have written an application for such a search. It is designed to be distributed, and can be adapted to BOINC with some efforts. With previous collaboration with yoyo@home, I am sure that it is not a problem. Checkpointing is natively in the code. In fact, the input file and the checkpoint file share the same format.

I have tested the application on large intervals. It takes roughly a week to test an interval of length 10^17. I would like to do a search up to 10^20 or 3*10^20, or even 10^21. The CPU time to test up to 10^20 would be roughly 26.3 years, including the factor for duplicating results for verification.

However, there are still some minor problem with the resource comsumption of the application. In some cases, it eats up a lot of memory (about 700MB in extreme cases). It is possible to mitigate the situation with appropriate algorithms, but might slow down the application. I am working on this issue.

Anyway, thank you for reading. I am looking forward to any comment or reply.

Cheers,
fwjmath.

[ChristianB]

Very good proposal. Is there any gain from this (other than getting 10$ and the fame)? And I don't think that 700MB isn't that much with modern PC and I would prefer faster runtime over memory consumption in this case.

[fwjmath]

ChristianB, thanks for your reply.

I have to admit that, unlike harmonious labeling, odd weird number is a relatively isolated problem in number theory, and other than getting the fame (I assume no cruncher really cares about the 10$, but the fame is really a big one), it will not give much mathematical insight. Indeed, we will know a bit more about the additive structure of proper factors of odd number, namely knowing that really bad things can happen, but nothing much more. In fact, it would be much more interesting if no odd weird number exists, because it means that there is some additive structure in the set of proper divisors that we don't know. That seems also to be part of the reason that Erdos gave more money to a proof of non-existence.

But it is still an interesting and cool question, at least for me.

Cheers,
fwjmath.

[yoyo]

Very good proposal. I don't see really a problem with the RAM consumption. I think a RMA usage up to 1GB would be ok. Some other subprojects here need up to 1.8GB.
So let me know when your app is ready than I (and I hope Christian also) will have a look into it and adapt it to the Boinc API.
yoyo

[Dj Ninja]

> I think a RMA usage up to 1GB would be ok
return merchandise authorization ?

SCNR

[yoyo]

In which relation is the project to http://oproject.info/ ?
yoyo

[fwjmath]

In which relation is the project to http://oproject.info/ ?
yoyo

The short answer: not really any relation.

I will explain in detail.

OProject first started a subproject with the aim of searching for weird numbers. They held a challenge for volunteers to donate code for the project's research. They then adapted the code from cedricdd of Alliance Francophone.

But I pointed out that there are plenty of weird numbers (they are of positive asymptotic density), and searching for all of them is rather mathematically meaningless. I then suggested to search for odd weird numbers (this is my idea), since it is much more interesting. I became interested in this problem.

Then I helped cedricdd to optimize their algorithm for odd weird numbers searching, using mathematical arguments. A significant performance boost due to these mathematical arguments was observed (about 10000x, or even higher).

Due to various events that I don't want to talk about now, I am extremely disappointed by the management of OProject. I developped/rewrote my own version of the application, but borrowing some ideas from the code of cedricdd for a certain not-so-crucial part of my code. The current version of OProject's application (at least for some platform) is using my code with some optimizations (which are rather impressive) by cedricdd. This piece of code can be found online here: https://code.google.com/p/weird-odd-engine/.

I then came up with a very good idea of optimizing the algorithm during a math conference, and I wrote a totally new application realizing this algorithm. This is the one I am going to use in Odd Weird Search.

Since I am so disappointed by OProject, and I am interested enough to want to put in my effort to push this search by volunteer computing, I come here instead of giving the code to OProject. From the previous collaboration, I know that yoyo@home has a good team and a good management. My code will most surely shine under yoyo@home, and wither if I gave it to OProject. And clearly I want to do the better thing.

So, in one sentence. It is my idea, my code, my math.

By the way, given the difference in performance, there is no worry about range overlap.

[yoyo]

Did I saw it right, that you will join the Boinc workshop in Grenoble?
If this is the case I (and I think Christian) will meet you there.

yoyo

[fwjmath]

Did I saw it right, that you will join the Boinc workshop in Grenoble?
If this is the case I (and I think Christian) will meet you there.

yoyo

Yes, I will (very probably) be there. I am looking forward to discussing with you guys there.

Cheers,
fwjmath.