- Am I missing something? Why don't you sieve with squares of elements from P to identify those not square free (by setting the location to a large negative value), and then sieve the remaining numbers, accumulating a list of elements of P on each sieve location while adding log(P) to the sieve location?

After the second sieve, those locations which are approximately log(X+iY) are smooth and the list gives you the factorization. If you're prepared to use trial division on the smooth locations, you don't need to store the list while sieving.

Paul

> -----Original Message-----

http://docs.yahoo.com/info/terms/

> From: Phil Carmody [mailto:thefatphil@...]

> Sent: 02 November 2002 18:10

> To: primenumbers

> Subject: [PrimeNumbers] My brain hurts - finding smooth

> numbers on an AP

>

>

> Lets say I have a set P = { 2,3,5, ... p }, say p is 10000

> And an AP X+iY where Y is about 10^50,

>

> Is there an effective way of finding any terms on the AP that are

> square-free and entirely factorable using members of P?

>

> My head's been spinning with other maths today, and has

> finally worn out!

>

> What makes sense -

> 1) sieving by adding good numbers

> like a QS approach, finding smooths, but on an AP not a QP.

> 2) sieving by removing bad numbers that have unwanted factors,

> like a conventional sieve

> 3) just trial divide every number, looks painful, and I'm

> guessing won't play too much a role.

> 4) one of the dozen permutations/combinations of the above.

>

>

> What are the heuristics - say I needed 100 such numbers, what

> range of i

> would I need to look at? Squarefreeness messes things up a bit, alas.

>

> Any ideas?

>

> Phil

>

>

> =====

> First rule of Factor Club - you do not talk about Factor Club.

> Second rule of Factor Club - you DO NOT talk about Factor Club.

> Third rule of Factor Club - when the cofactor is prime, or

> you've trial-

> divided up to the square root of the number, the factoring is over.

>

> __________________________________________________

> Do you Yahoo!?

> HotJobs - Search new jobs daily now

> http://hotjobs.yahoo.com/

>

> Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com

> The Prime Pages : http://www.primepages.org/

>

>

>

> Your use of Yahoo! Groups is subject to

- --- Paul Leyland <pleyland@...> wrote:
> Am I missing something?

You're missing the fact that I'd probably scribbled about 30 pages of notes

that day (none of which were bin-fodder, it was most productive), and was

quite literally mentally exhausted.

> Why don't you sieve with squares of elements from P to identify those

part of my approach (2)

> not square free (by setting the location to a large negative value),

> and then sieve the

my approach (1)

> remaining numbers, accumulating a list of elements of P on each sieve location while adding

> log(P) to the sieve location?

> After the second sieve, those locations which are approximately log(X+iY) are smooth and the

The number that I'm expecting to pass now (I looked at a 100K range, and

> list gives you the factorization. If you're prepared to use trial division on the smooth

> locations, you don't need to store the list while sieving.

found nothing) are so low that I think re-TD-ing will be inexpensive, which

was my approach (3), that it appears will play only a very minor role.

I think that (1) and (2) pretty much commute.

If anything, blanking the squaresome (neologism?) numbers after the log-accumulating

sieve works even better.

I wasn't so far out after all, I'm amazed!

It's just a shame that the yield is so low that it's probably not worth

doing. I'll put it on a back-burner, I've got another 20 pages of notes for

another new technique that may aid the task I'm currently looking at.

I'm trying to break a (minority interest) record using nothing but a single

PPro/200 - this will be a victory for wetware if it ever works!

Cheers for confirming my ideas,

Phil

=====

First rule of Factor Club - you do not talk about Factor Club.

Second rule of Factor Club - you DO NOT talk about Factor Club.

Third rule of Factor Club - when the cofactor is prime, or you've trial-

divided up to the square root of the number, the factoring is over.

__________________________________________________

Do you Yahoo!?

HotJobs - Search new jobs daily now

http://hotjobs.yahoo.com/