mersenneforum.org > Math Looking for a sieving program
 Register FAQ Search Today's Posts Mark Forums Read

 2007-03-18, 00:24 #1 jasong     "Jason Goatcher" Mar 2005 5·701 Posts Looking for a sieving program Is there a program out there, where you can enter a range of numbers, and it will tell you any factors below a million, a billion, or...? Mind you, these aren't special form numbers, these are sequential numbers.
2007-03-18, 02:16   #2
Xyzzy

"Mike"
Aug 2002

1D8916 Posts

Quote:
 Is there a program out there, where you can enter a range of numbers, and it will tell you any factors below a million, a billion, or...? Mind you, these aren't special form numbers, these are sequential numbers.
If you are running BASH (which you should) try:

Code:
for i in seq 2 10000; do factor \$i; done
It ain't fast, but it works. Adjust the numbers as appropriate.

When we say it ain't fast, we aren't joking. You could factor these by hand faster. Or something.
Attached Files
 10000.txt.bz2 (39.1 KB, 45 views)

 2007-03-18, 14:34 #3 Xyzzy     "Mike" Aug 2002 166118 Posts In case you want to list the primes, here is a very ugly BASH program. Code: cat file | cut -d ':' -f 2 | sed 's/^ //' | grep -v ' ' This assumes you sent the output from the first program to a file. You could do it on the fly but it would just slow things down even more, which, we know, sounds impossible to believe.
 2007-03-18, 20:39 #4 jasong     "Jason Goatcher" Mar 2005 5·701 Posts Since there doesn't seem to be a program that fits my needs, I guess I might as well reveal what I wanted to do. I wanted to find the lowest 114-digit number with two brilliant factors. A brilliant number is a number where all the prime factors have the same number of digits. So far, digits 1 through 113 are spoken for.
2007-03-19, 01:14   #5
Xyzzy

"Mike"
Aug 2002

7,561 Posts

Quote:
 Is there a program out there, where you can enter a range of numbers, and it will tell you any factors below a million, a billion, or...?
114 digit numbers are a little bigger than what you hinted at.

2007-03-19, 02:50   #6

"Richard B. Woods"
Aug 2002
Wisconsin USA

11110000011002 Posts

Quote:
 Originally Posted by Xyzzy 114 digit numbers are a little bigger than what you hinted at.
jasong's original posting contained no hint, misleading or otherwise, about the size of numbers he sought to factor. His mention of "factors below a million, a billion, or..." hints only at size of possible factors, not of the numbers to be factored.

Last fiddled with by cheesehead on 2007-03-19 at 02:53

 2007-03-19, 03:09 #7 Xyzzy     "Mike" Aug 2002 7,561 Posts Stop making sense. It hurts us so. The rock and pool Is nice and cool So juicy sweet Our only wish To catch a fish So juicy sweet
2007-03-19, 17:33   #8
Xyzzy

"Mike"
Aug 2002

7,561 Posts

Why? Because we were bored.

How long did it take? You don't want to know.

Was it pointless? Of course!

Attached Files
 1000000.bz2 (4.93 MB, 45 views)

2007-03-19, 19:22   #9
xilman
Bamboozled!

May 2003
Down not across

2·3·412 Posts

Quote:
 Originally Posted by jasong Since there doesn't seem to be a program that fits my needs, I guess I might as well reveal what I wanted to do. I wanted to find the lowest 114-digit number with two brilliant factors. A brilliant number is a number where all the prime factors have the same number of digits. So far, digits 1 through 113 are spoken for.
Now you've told us what you want, we can give sensible answers.

First off, write a simple program (yes, write it for yourself --- if you can't write it you're not going to succeed in everything else that's needed) which divide all numbers between (say 100^113 and 10^113+1000000) by small primes --- those under 1000 say. Anything which isn't divisible by one of those, you write to a file.

There are any number of programming languages which will let you do this first stage. If you're on a MS operating system, UBASIC is as good as any and better than most.

Then, once you've found all the numbers of interest without any small factors, get hold of an ECM program and use it to find medium size factors of those. GMP-ECM is the most effecient I know of and it's been ported to many operating systems. Keep using ECM, with ever larger B1 limit, until you get bored. Every time you find a factor of an integer N, remove it from your list.

After that phase is over --- it will probably take you only a month or so unless you've serious amount of computation available --- get hold of a NFS factoring package and use it to do each of the remaining candidates in order of size. Sooner or later you will find a brilliant number.

Beware: it took me about 5 years to find the smallest 150-brilliant number.

Good luck!

Paul

2007-03-19, 19:30   #10
Xyzzy

"Mike"
Aug 2002

7,561 Posts

Quote:
 Beware: it took me about 5 years to find the smallest 150-brilliant number.
On a Sinclair ZX81.

And he was happy to have it!

2007-03-19, 21:55   #11
Citrix

Jun 2003

1,553 Posts

Quote:
 Originally Posted by xilman Now you've told us what you want, we can give sensible answers. First off, write a simple program (yes, write it for yourself --- if you can't write it you're not going to succeed in everything else that's needed) which divide all numbers between (say 100^113 and 10^113+1000000) by small primes --- those under 1000 say. Anything which isn't divisible by one of those, you write to a file. Paul
I think you can use newpgen for this, though I am not sure. Check it out for yourself.

 Similar Threads Thread Thread Starter Forum Replies Last Post PawnProver44 Information & Answers 40 2016-03-11 22:00 JHansen NFSNET Discussion 9 2010-06-09 19:25 boooh Information & Answers 2 2010-03-22 15:22 moo Software 0 2006-06-27 00:19 drakkar67 Prime Sierpinski Project 14 2005-11-29 06:25

All times are UTC. The time now is 18:25.

Mon Jul 13 18:25:36 UTC 2020 up 110 days, 15:58, 1 user, load averages: 1.52, 1.65, 1.64