## My brain hurts - finding smooth numbers on an AP

Expand Messages
• 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
Message 1 of 4 , Nov 2, 2002
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/
• Hello Phil, ... As for finding the smooth values (if I remember correctly you have C&P:PNaCP) sections 3.2.5 and 3.2.6 are great at explaining a good way of
Message 2 of 4 , Nov 2, 2002
Hello Phil,

Phil Carmody wrote:
>
> 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?

As for finding the smooth values (if I remember correctly you have
C&P:PNaCP) sections 3.2.5 and 3.2.6 are great at explaining a good way
of sieving for finding smooth numbers.

Now, as for finding square-free numbers, well,

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

I think this one might not be a good idea because you might skip over
some numbers that fit your criteria. However, it is also good because
you are guaranteed to get only the numbers you want. So, its up to you
to do this one depending on whether you want all numbers fitting your
criteria in a range or if you don't mind missing a few in your range.

> 2) sieving by removing bad numbers that have unwanted factors,
> like a conventional sieve

This one is good because you can easily sieve your p-smooth numbers to
see if they are divisble by {4,9,25,...,p^2}. Actually, you might want
to do this at the same time you are testing for p-smoothness so that you
can do it all in one pass.

> 3) just trial divide every number, looks painful, and I'm
> guessing won't play too much a role.

I agree, this is one method to stay away from.

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

I hope the above was helpful. I have to get ready to go to work, but
when I get back if you want any help or advice in coding this up I would
love to help.

-David C.

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

P.S. does "P = { 2,3,5, ... p }, say p is 10000" mean that 10000 is a
Carmody-prime? ;)
• 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 3 of 4 , Nov 3, 2002
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 4 of 4 , Nov 3, 2002
--- 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.