mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2007-03-18, 00:24   #1
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

350510 Posts
Default 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.
jasong is offline   Reply With Quote
Old 2007-03-18, 02:16   #2
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

3×19×137 Posts
Default

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
File Type: bz2 10000.txt.bz2 (39.1 KB, 54 views)
Xyzzy is offline   Reply With Quote
Old 2007-03-18, 14:34   #3
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

1E8116 Posts
Default

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.
Xyzzy is offline   Reply With Quote
Old 2007-03-18, 20:39   #4
jasong
 
jasong's Avatar
 
"Jason Goatcher"
Mar 2005

5×701 Posts
Default

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.
jasong is offline   Reply With Quote
Old 2007-03-19, 01:14   #5
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

3·19·137 Posts
Default

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.

Xyzzy is offline   Reply With Quote
Old 2007-03-19, 02:50   #6
cheesehead
 
cheesehead's Avatar
 
"Richard B. Woods"
Aug 2002
Wisconsin USA

22·3·599 Posts
Default

Quote:
Originally Posted by Xyzzy View Post
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
cheesehead is offline   Reply With Quote
Old 2007-03-19, 03:09   #7
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

3×19×137 Posts
Default

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
Xyzzy is offline   Reply With Quote
Old 2007-03-19, 17:33   #8
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

172018 Posts
Default

Why? Because we were bored.

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

Was it pointless? Of course!

Attached Files
File Type: bz2 1000000.bz2 (4.93 MB, 53 views)
Xyzzy is offline   Reply With Quote
Old 2007-03-19, 19:22   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

5×2,039 Posts
Default

Quote:
Originally Posted by jasong View Post
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
xilman is offline   Reply With Quote
Old 2007-03-19, 19:30   #10
Xyzzy
 
Xyzzy's Avatar
 
"Mike"
Aug 2002

11110100000012 Posts
Default

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!
Xyzzy is offline   Reply With Quote
Old 2007-03-19, 21:55   #11
Citrix
 
Citrix's Avatar
 
Jun 2003

62716 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Citrix is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Fastest sieving program? PawnProver44 Information & Answers 40 2016-03-11 22:00
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
about the program boooh Information & Answers 2 2010-03-22 15:22
Old Program moo Software 0 2006-06-27 00:19
which program? drakkar67 Prime Sierpinski Project 14 2005-11-29 06:25

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

Sat Nov 28 02:28:05 UTC 2020 up 78 days, 23:39, 3 users, load averages: 1.24, 1.15, 1.15

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.