## RE: [PrimeNumbers] My brain hurts - finding smooth numbers on an AP

Expand Messages
• 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
Message 1 of 4 , Nov 3, 2002
• 0 Attachment
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-----
> From: Phil Carmody [mailto:thefatphil@...]
> Sent: 02 November 2002 18:10
> 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
http://docs.yahoo.com/info/terms/
• ... 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
Message 2 of 4 , Nov 3, 2002
• 0 Attachment
--- 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
> not square free (by setting the location to a large negative value),

part of my approach (2)

> 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?

my approach (1)

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

The number that I'm expecting to pass now (I looked at a 100K range, and
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/
Your message has been successfully submitted and would be delivered to recipients shortly.