mersenneforum.org Powerful Numbers programming challenge
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2004-12-27, 10:51   #1
geoff

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 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
 powp.zip (755 Bytes, 249 views)

 2004-12-27, 15:45 #2 Xyzzy     Aug 2002 22×11×191 Posts Interesting problem... Now I have to go and learn about PARI/GP... I've never heard of that before...
 2004-12-29, 06:37 #3 geoff     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.
2004-12-30, 16:01   #4
geoff

Mar 2003
New Zealand

48516 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.
Attached Files
 oppsearch-0.1.zip (2.6 KB, 209 views)

 2005-01-01, 14:28 #5 geoff     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 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.
2005-01-02, 04:42   #6
geoff

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.
Attached Files
 oppsearch-0.6.zip (2.2 KB, 213 views)

 2005-01-03, 01:59 #7 geoff     Mar 2003 New Zealand 100100001012 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 :-)
2005-01-06, 01:26   #8
geoff

Mar 2003
New Zealand

13·89 Posts

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
 oppsearch-0.9.zip (3.2 KB, 233 views)

 2005-01-09, 11:41 #9 Templus     Jun 2004 10610 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?
2005-01-09, 18:16   #10
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·3·17·109 Posts

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

2005-01-09, 22:02   #11
geoff

Mar 2003
New Zealand

100100001012 Posts

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
 oppsearch-1.0.zip (3.8 KB, 212 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post robert44444uk Software 21 2017-04-13 09:40 koders333 Factoring 12 2006-03-31 16:06 philmoore Factoring 63 2005-01-06 03:09 chrow Factoring 3 2003-08-24 17:41 Fusion_power Puzzles 25 2003-08-21 15:56

All times are UTC. The time now is 02:30.

Tue Jan 18 02:30:37 UTC 2022 up 178 days, 20:59, 0 users, load averages: 1.78, 1.26, 1.24

Copyright ©2000 - 2022, 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.

โ  ยฑ โ รท ร ยท โ โ โฐ โ โ โ โ โ โค โฅ โฆ โง โจ โฉ โบ โป โผ โฝ โ โ โ โ ยฒ ยณ ยฐ
โ  โ ยฐ โ ~ โ โ โซ
โก โ โ โ โ โช โซ โโ โโ โ โ โ โ โง โจ โฉ โช โจ โ โ ๐ ๐ ๐ โฒ โณ
โ โ โ โฆ โฃ โฉ โช โ โ โ โ โ โ โ โ โ โ โ โ โ โ โค โ โ โ โต โถ โท โธ ๐
ยฌ โจ โง โ โ โ โ โ โ โ โ โ โด โต โค โฅ โข โจ โซค โฃ โฆ โฏ โฎ โฐ โฑ
โซ โฌ โญ โฎ โฏ โฐ โ โ ฮด โ โฑ โ โ
๐ข๐ผ ๐ฃ๐ฝ ๐ค๐พ ๐ฅ๐ฟ ๐ฆ๐๐ ๐ง๐ ๐จ๐ ๐ฉ๐๐ ๐ช๐ ๐ซ๐ ๐ฌ๐ ๐ญ๐ ๐ฎ๐ ๐ฏ๐ ๐ฐ๐ ๐ฑ๐ ๐ฒ๐ ๐ด๐ ๐ต๐ ๐ถ๐ ๐ท๐๐ ๐ธ๐ ๐น๐ ๐บ๐