20041227, 10:51  #1 
Mar 2003
New Zealand
13×89 Posts 
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 simpleminded and slow (it takes about 6 seconds to search a range of one million on a PIII/600) but it works. I would like to write a program in C that sieves out nonpowerful 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? 
20041227, 15:45  #2 
"Mike"
Aug 2002
17034_{8} Posts 
Interesting problem...
Now I have to go and learn about PARI/GP... I've never heard of that before... 
20041229, 06:37  #3 
Mar 2003
New Zealand
13×89 Posts 
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. 
20041230, 16:01  #4 
Mar 2003
New Zealand
10010000101_{2} Posts 
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. 
20050101, 14:28  #5 
Mar 2003
New Zealand
13×89 Posts 
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 nonpowerful 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.

20050102, 04:42  #6 
Mar 2003
New Zealand
13·89 Posts 
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. 
20050103, 01:59  #7 
Mar 2003
New Zealand
13·89 Posts 
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 :) 
20050106, 01:26  #8 
Mar 2003
New Zealand
485_{16} Posts 
The definition of powerful number can be generalised a little to say that a number N is mpowerful if p^m divides N whenever p divides N, for prime p.
I was wondering if there could be any 3powerful 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 3powerful 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 3powerful 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 3powerful. 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 ctrlc) 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). 
20050109, 11:41  #9 
Jun 2004
2×53 Posts 
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? 
20050109, 18:16  #10  
Bamboozled!
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across
2791_{16} Posts 
Quote:
Paul 

20050109, 22:02  #11  
Mar 2003
New Zealand
13·89 Posts 
Quote:
Here is a new version that is a little faster and has a few minor bugs fixed. 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Prime gap programming challenge  robert44444uk  Software  21  20170413 09:40 
Same team factored RSA challenge numbers in recent time  koders333  Factoring  12  20060331 16:06 
Odd Perfect numbers  a factoring challenge  philmoore  Factoring  63  20050106 03:09 
long numbers. Programming.  chrow  Factoring  3  20030824 17:41 
programming challenge  Fusion_power  Puzzles  25  20030821 15:56 