Looking for a sieving program

[jasong]

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.

[Xyzzy]

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:

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.

[Xyzzy]

In case you want to list the primes, here is a very ugly BASH program.

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.

[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.

[Xyzzy]

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.

[cheesehead]

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.

[Xyzzy]

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]

Why? Because we were bored.

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

Was it pointless? Of course!

[xilman]

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

[Xyzzy]

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!

[Citrix]

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.