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

Phil Carmody wrote:>

As for finding the smooth values (if I remember correctly you have

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

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,

>

I think this one might not be a good idea because you might skip over

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

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,

This one is good because you can easily sieve your p-smooth numbers to

> like a conventional sieve

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

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

> guessing won't play too much a role.

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

>

P.S. does "P = { 2,3,5, ... p }, say p is 10000" mean that 10000 is a

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

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