mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Programming

Reply
 
Thread Tools
Old 2004-12-27, 10:51   #1
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default Powerful Numbers programming challenge

N is a powerful number if p^2 divides N whenever p divides N (for prime p). See http://mathworld.wolfram.com/PowerfulNumber.html. The sequence of powerful numbers begins:

1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 72, 81, 100, ...

Pairs of consequtive powerful numbers are quite common, this sequence (smaller of each pair only) begins:

8, 288, 675, 9800, 12167, 235224, 332928, 465124, ...

But there are no known examples of three consequtive powerful numbers. Paul Erdös conjectured that none exist, but the problem remains open. Since adjacent even numbers cannot both be powerful (2^2 can't divide both), any three consequtive powerful numbers must include a pair of adjacent odd powerful numbers. These seem quite difficult to find, the sequence (smaller of each pair only) begins:

25, 70225, 130576327, 189750625, 512706121225, 13837575261123, 99612037019889, ...

As far as I can find out this is as far as the sequence has been computed. See http://www.research.att.com/projects/OEIS?Anum=A076445. If anyone else knows any more about this then please post.

I wrote a little PARI/GP program (attached) to search for new odd pairs of powerful numbers, it is simple-minded and slow (it takes about 6 seconds to search a range of one million on a P-III/600) but it works. I would like to write a program in C that sieves out non-powerful numbers from a range before testing any pairs that remain, which should be much faster. Does anyone know of an existing program that could do this?

This might be an interesting programming challenge in any case. If we could come up with something fast enough then a distributed project to extend this sequence (and to search for a counterexample to Erdös' conjecture in the process) might be viable.

If this particular sequence doesn't appeal then there are lots of other interesting ones at http://www.research.att.com/~njas/sequences/more.html. Any suggestions?
Attached Files
File Type: zip powp.zip (755 Bytes, 175 views)
geoff is offline   Reply With Quote
Old 2004-12-27, 15:45   #2
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

170348 Posts
Default

Interesting problem...

Now I have to go and learn about PARI/GP... I've never heard of that before...
Xyzzy is offline   Reply With Quote
Old 2004-12-29, 06:37   #3
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

I think that a program to extend the sequence, which must eliminate all candidate pairs in a range, will be much slower than one that simply looks for new pairs without regard to whether any smaller pairs exist. The first will propably need some fairly sophisticated factoring algorithms for best speed, but the second may need nothing more than trial division by very small primes.

I guess it is possible that larger terms in the sequence have already been found and that the seven term sequence I listed in my first post is just the longest that is known to have no gaps.
geoff is offline   Reply With Quote
Old 2004-12-30, 16:01   #4
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

100100001012 Posts
Default

Here is my first attempt at a C program to search for odd powerful pairs. By default it performs an exhaustive search which is very slow, but the -t switch allows a limit to be set so that the search only considers pairs where both numbers have all factors smaller than the limit. It uses 'long long' arithmetic, so the range to search must be below 2^64. The end of the existing sequence is below 2^47, so that is not a problem.

I think that it will be possible to add a sieving stage in which only 32 bit arithmetic will be needed that might speed it up a bit. Also I might try to link it to the PARI library which would allow better factoring algorithms to be used when trial factoring reaches its effective limit.

Here is an example running on a P3/600, it searches the range 1 to 200 million to a limit of 617 and finds the first four terms of the sequence:

Code:
geoff@vec:~$ ./oppsearch -t 617 1 200000000
(25,27), (70225,70227), (130576327,130576329), (189750625,189750627).
99999999 candidates tested, time = 268 sec. (2.68 usec/candidate)
61197656 (61.2%) eliminated by finding a singleton factor.
35011674 (35.0%) eliminated by eliminating neighbours.
3790665 (3.8%) could not be eliminated by trial division.
4 odd powerful pairs found.
Attached Files
File Type: zip oppsearch-0.1.zip (2.6 KB, 134 views)
geoff is offline   Reply With Quote
Old 2005-01-01, 14:28   #5
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13×89 Posts
Default

I have been thinking about this problem the wrong way. As noted in the references I gave earlier, any powerful number is of the form a^2.b^3 for some positive integers a,b. Instead of a sieving non-powerful numbers from a range it would be much easier to generate every powerful number in a range. Oh well, I have learned a bit about sieving so it wasn't all wasted effort.
geoff is offline   Reply With Quote
Old 2005-01-02, 04:42   #6
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default New pair found

I found this pair of powerful numbers that differ by two, extending the sequence A076445: (1385331749802025,1385331749802027)

The program I used is attached, there is plenty of room for optimisation but it should be fast enough to make it worthwhile looking for more pairs. It uses the gmp library and so should work with any range of numbers. If you use it and find anything then post your discoveries here.

I'm going to try to check up to at least 2^64, I am not quite sure how long it will take, maybe a day or so on my P3/600.
Attached Files
File Type: zip oppsearch-0.6.zip (2.2 KB, 140 views)
geoff is offline   Reply With Quote
Old 2005-01-03, 01:59   #7
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

I found this new pair: (3743165875258953025, 3743165875258953027)

I tested up to 2*10^19 (just beyond 2^64) and didn't find any other pairs. It took about 10 hours on a P3/600, probably could have been faster but I don't know how to choose the optimal block size yet. Next goal is to make the program do that automatically :-)
geoff is offline   Reply With Quote
Old 2005-01-06, 01:26   #8
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

48516 Posts
Default

The definition of powerful number can be generalised a little to say that a number N is m-powerful if p^m divides N whenever p divides N, for prime p.

I was wondering if there could be any 3-powerful numbers that differ by 2? If so they would form a subsequence of the sequence of powerful numbers that differ by 2, but none of the known terms of this sequence are 3-powerful so if one were discovered perhaps it would be the first known?

It would be quite easy to adapt the oppsearch program to look specifically for 3-powerful numbers, but for now I am going to concentrate on finding a few more terms of the original sequence. Maybe one will turn out to be 3-powerful.

The attached update is much easier to use, no need to choose a block size, just specify the amount of memory to use (in Mb) with the -m switch. The -d switch specifies the number of minutes between screen updates. The program now makes an accurate (hopefully) count of the number of odd powerful numbers in the range searched, which could be used as a form of checksum if double checking were done, or to test against another program.

If the program is interrupted (with ctrl-c) it outputs the bound that it has tested up to and the opn count, so it can be resumed from that point.

It also outputs the number of odd powerful numbers (opn) generated per second, a basis for measuring any performance improvement (unless I can find an algorithm that doesn't require generating every odd term of the sequence).
Attached Files
File Type: zip oppsearch-0.9.zip (3.2 KB, 158 views)
geoff is offline   Reply With Quote
Old 2005-01-09, 11:41   #9
Templus
 
Templus's Avatar
 
Jun 2004

2×53 Posts
Default

I am trying to compile the source under Windows XP using the djgpp compiler.
I already installed the gmp.h and gmp.lib files,
but when I try to compile it with the makefile I get the error that it can't find the -lgmp.
I believe this is a special flag referring to the gmp?

Does anybody know how I could solve this problem?
Templus is offline   Reply With Quote
Old 2005-01-09, 18:16   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

279116 Posts
Default

Quote:
Originally Posted by Templus
I am trying to compile the source under Windows XP using the djgpp compiler.
I already installed the gmp.h and gmp.lib files,
but when I try to compile it with the makefile I get the error that it can't find the -lgmp.
I believe this is a special flag referring to the gmp?

Does anybody know how I could solve this problem?
You probably need to tell it where to find the library, as it looks as if it may not be in a place where the compiler looks for itself. Try giving the directory containing the library as an argument to the -L switch.


Paul
xilman is offline   Reply With Quote
Old 2005-01-09, 22:02   #11
geoff
 
geoff's Avatar
 
Mar 2003
New Zealand

13·89 Posts
Default

Quote:
Originally Posted by Templus
I am trying to compile the source under Windows XP using the djgpp compiler.
If you succeed could you post a binary? I have access to a few Windows machines but don't know where to start installing development tools.

Here is a new version that is a little faster and has a few minor bugs fixed.
Attached Files
File Type: zip oppsearch-1.0.zip (3.8 KB, 140 views)
geoff is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Prime gap programming challenge robert44444uk Software 21 2017-04-13 09:40
Same team factored RSA challenge numbers in recent time koders333 Factoring 12 2006-03-31 16:06
Odd Perfect numbers - a factoring challenge philmoore Factoring 63 2005-01-06 03:09
long numbers. Programming. chrow Factoring 3 2003-08-24 17:41
programming challenge Fusion_power Puzzles 25 2003-08-21 15:56

All times are UTC. The time now is 08:12.

Thu Oct 29 08:12:16 UTC 2020 up 49 days, 5:23, 1 user, load averages: 1.24, 1.49, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.