Asp Forum - Primality sieve challenge

JT

1/17/2016 9:41:00 AM

Maybe we could have a challenge finding the base with best reducion upto 100 000000? One probably do not want to store more vectors than that in memory, and i guess

Reducing composites in the integer field
http://jt.node365.se/comp...

I've made my own kind of primality sieve that work by reducing lthe number field into composite "legs" and prime "egs". The legs that contain just composites in the numberfield will be thrown away sieved?

I asked the people at sci.math if there was a known upper limit for the reduction using this type of counters in the integer field, they said no.

I wonder if there is a name for this type of sieve/counter within information theory?

My idea is to find a base with very high percentage of composite legs, remove all start numbers that produce only composites in their legs, and then store the other egs that contain prime in an array.

That array will than serve the purpose modelling the new integer field, using the searched base with highest composite reduction.

The script seaching the bases take a few seconds, so there could be alot of improvements. I have a feeling that using bignumb bases as sieves will be out of range for us mere mortals, but who knows maybe for computer theorists.

73 Answers

JT

1/17/2016 10:20:00 AM

Den söndag 17 januari 2016 kl. 10:41:03 UTC+1 skrev jonas.t...@gmail.com:
> Maybe we could have a challenge finding the base with best reducion upto 100 000000? One probably do not want to store more vectors than that in memory, and i guess
>
> Reducing composites in the integer field
> http://jt.node365.se/comp...
>
>
> I've made my own kind of primality sieve that work by reducing lthe number field into composite "legs" and prime "egs". The legs that contain just composites in the numberfield will be thrown away sieved?
>
> I asked the people at sci.math if there was a known upper limit for the reduction using this type of counters in the integer field, they said no.
>
> I wonder if there is a name for this type of sieve/counter within information theory?
>
> My idea is to find a base with very high percentage of composite legs, remove all start numbers that produce only composites in their legs, and then store the other egs that contain prime in an array.
>
> That array will than serve the purpose modelling the new integer field, using the searched base with highest composite reduction.
>
>
> The script seaching the bases take a few seconds, so there could be alot of improvements. I have a feeling that using bignumb bases as sieves will be out of range for us mere mortals, but who knows maybe for computer theorists.

At least i am impressed how well it reduce the composite integer field but of course you need a big array...

The math guys said just construct the base using the primes 2*3*5*7*11*13*17... and so on.

NEWBASE = 510510 ------------------------------------------
BASE= 510510 Composite legs= 92.91551585669234% ===============
One could say it is a bit clumsy but i think it is neat be able to peel of numbers that do not even need to be considered for primality test.

Ben Bacarisse

1/17/2016 4:24:00 PM

jonas.thornvall@gmail.com writes:

> Maybe we could have a challenge finding the base with best reducion
> upto 100 000000? One probably do not want to store more vectors than
> that in memory, and i guess
>
> Reducing composites in the integer field
> http://jt.node365.se/comp...

Why don't you engage with what people say? That function called
factor_it is very peculiar. What is it supposed to do?

<snip>
--
Ben.

JT

1/17/2016 5:03:00 PM

Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
>
> > Maybe we could have a challenge finding the base with best reducion
> > upto 100 000000? One probably do not want to store more vectors than
> > that in memory, and i guess
> >
> > Reducing composites in the integer field
> > http://jt.node365.se/comp...
>
> Why don't you engage with what people say? That function called
> factor_it is very peculiar. What is it supposed to do?
>
> <snip>
> --
> Ben.

Here you can see what it does.

http://jt.node365.se/composit_...

JT

1/17/2016 5:18:00 PM

Den söndag 17 januari 2016 kl. 18:03:19 UTC+1 skrev jonas.t...@gmail.com:
> Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
> > jonas.thornvall@gmail.com writes:
> >
> > > Maybe we could have a challenge finding the base with best reducion
> > > upto 100 000000? One probably do not want to store more vectors than
> > > that in memory, and i guess
> > >
> > > Reducing composites in the integer field
> > > http://jt.node365.se/comp...
> >
> > Why don't you engage with what people say? That function called
> > factor_it is very peculiar. What is it supposed to do?
> >
> > <snip>
> > --
> > Ben.
>
> Here you can see what it does.
>
> http://jt.node365.se/composit_...

It is a primality check algorithm.

What the algorithm do is to reduce the search space by filter out the composites it can reduce the search space with 2 magnitudes. It can filter out 99% of the composite numbers in the integer field given a good *big* base.

It *will* store the primeleg vectors in an array and throw away the composite legs.

Right now it just printout the perentage for each base. But it will store startvalues for the primelegs.

But i was a bit to optimistic before didn't check high enough.
NEWBASE = 510510 ------------------------------------------
BASE= 510510 Composite legs= 81.94863959569841% ===============

But still not that bad. At least i am impressed how well it reduce the composite integer field but of course you need a big array...

The math guys said just construct the base using the primes 510510=2*3*5*7*11*13*17... and so on.

One could say it is a bit clumsy but i think it is neat be able to peel of numbers that do not even need to be considered for primality test.

I wonder if i am correct assuming that the integers will be reduced with.
510510=2*3*5*7*11*13*17 so using base 510510 the integers will be reduced with.
1/2+1/3+1/5+1/7+1/11+1/13+1/17... adding next prime to list, so the reduction will go on forever using the sieve as the base gets higher and higher.
No that adds up to 1.40284617343...
So what is the forumula calculating the reduction?

1/2 -1/3-1/5-1/7-1/11-1/13-1/17...
+1/3 -1/5-1/7-1/11-1/13-1/17...
+1/5 -1/7-1/11-1/13-1/17...
+1/7 -1/11-1/13-1/17...
+1/11 -1/13-1/17...
+1/13 -1/17...
+1/17 -...

Is that it?
===========
It seem holding/storing the counter values->vectors in an array for bases up to 10^10 will be no problem.

Given 64-bit integers it would take 4 GB.
=========================================

1 10 4
2 100 25
3 1,000 168
4 10,000 1,229
5 100,000 9,592
6 1,000,000 78,498
7 10,000,000 664,579
8 100,000,000 5,761,455
9 1,000,000,000 50,847,534
10 10,000,000,000 455,052,511
11 100,000,000,000 4,118,054,813
12 1,000,000,000,000 37,607,912,018

JT

1/17/2016 5:22:00 PM

Den söndag 17 januari 2016 kl. 18:17:43 UTC+1 skrev jonas.t...@gmail.com:
> Den söndag 17 januari 2016 kl. 18:03:19 UTC+1 skrev jonas.t...@gmail.com:
> > Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
> > > jonas.thornvall@gmail.com writes:
> > >
> > > > Maybe we could have a challenge finding the base with best reducion
> > > > upto 100 000000? One probably do not want to store more vectors than
> > > > that in memory, and i guess
> > > >
> > > > Reducing composites in the integer field
> > > > http://jt.node365.se/comp...
> > >
> > > Why don't you engage with what people say? That function called
> > > factor_it is very peculiar. What is it supposed to do?
> > >
> > > <snip>
> > > --
> > > Ben.
> >
> > Here you can see what it does.
> >
> > http://jt.node365.se/composit_...
>
> It is a primality check algorithm.
>
> What the algorithm do is to reduce the search space by filter out the composites it can reduce the search space with 2 magnitudes. It can filter out 99% of the composite numbers in the integer field given a good *big* base.
>
> It *will* store the primeleg vectors in an array and throw away the composite legs.
>
> Right now it just printout the perentage for each base. But it will store startvalues for the primelegs.
>
> But i was a bit to optimistic before didn't check high enough.
> NEWBASE = 510510 ------------------------------------------
> BASE= 510510 Composite legs= 81.94863959569841% ===============
>
> But still not that bad. At least i am impressed how well it reduce the composite integer field but of course you need a big array...
>
> The math guys said just construct the base using the primes 510510=2*3*5*7*11*13*17... and so on.
>
> One could say it is a bit clumsy but i think it is neat be able to peel of numbers that do not even need to be considered for primality test.
>
> I wonder if i am correct assuming that the integers will be reduced with.
> 510510=2*3*5*7*11*13*17 so using base 510510 the integers will be reduced with.
> 1/2+1/3+1/5+1/7+1/11+1/13+1/17... adding next prime to list, so the reduction will go on forever using the sieve as the base gets higher and higher.
> No that adds up to 1.40284617343...
> So what is the forumula calculating the reduction?
>
> 1/2 -1/3-1/5-1/7-1/11-1/13-1/17...
> +1/3 -1/5-1/7-1/11-1/13-1/17...
> +1/5 -1/7-1/11-1/13-1/17...
> +1/7 -1/11-1/13-1/17...
> +1/11 -1/13-1/17...
> +1/13 -1/17...
> +1/17 -...
>
> Is that it?
> ===========
> It seem holding/storing the counter values->vectors in an array for bases up to 10^10 will be no problem.
>
> Given 64-bit integers it would take 4 GB.
> =========================================
>
> 1 10 4
> 2 100 25
> 3 1,000 168
> 4 10,000 1,229
> 5 100,000 9,592
> 6 1,000,000 78,498
> 7 10,000,000 664,579
> 8 100,000,000 5,761,455
> 9 1,000,000,000 50,847,534
> 10 10,000,000,000 455,052,511
> 11 100,000,000,000 4,118,054,813
> 12 1,000,000,000,000 37,607,912,018

In fact i already implemented the tools to factor an integer in linear time if you check out my baseconversion. This is just removing numbers not necessary to check.

JT

1/17/2016 7:32:00 PM

Den söndag 17 januari 2016 kl. 18:22:19 UTC+1 skrev jonas.t...@gmail.com:
> Den söndag 17 januari 2016 kl. 18:17:43 UTC+1 skrev jonas.t...@gmail.com:
> > Den söndag 17 januari 2016 kl. 18:03:19 UTC+1 skrev jonas.t...@gmail.com:
> > > Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
> > > > jonas.thornvall@gmail.com writes:
> > > >
> > > > > Maybe we could have a challenge finding the base with best reducion
> > > > > upto 100 000000? One probably do not want to store more vectors than
> > > > > that in memory, and i guess
> > > > >
> > > > > Reducing composites in the integer field
> > > > > http://jt.node365.se/comp...
> > > >
> > > > Why don't you engage with what people say? That function called
> > > > factor_it is very peculiar. What is it supposed to do?
> > > >
> > > > <snip>
> > > > --
> > > > Ben.
> > >
> > > Here you can see what it does.
> > >
> > > http://jt.node365.se/composit_...
> >
> > It is a primality check algorithm.
> >
> > What the algorithm do is to reduce the search space by filter out the composites it can reduce the search space with 2 magnitudes. It can filter out 99% of the composite numbers in the integer field given a good *big* base.
> >
> > It *will* store the primeleg vectors in an array and throw away the composite legs.
> >
> > Right now it just printout the perentage for each base. But it will store startvalues for the primelegs.
> >
> > But i was a bit to optimistic before didn't check high enough.
> > NEWBASE = 510510 ------------------------------------------
> > BASE= 510510 Composite legs= 81.94863959569841% ===============
> >
> > But still not that bad. At least i am impressed how well it reduce the composite integer field but of course you need a big array...
> >
> > The math guys said just construct the base using the primes 510510=2*3*5*7*11*13*17... and so on.
> >
> > One could say it is a bit clumsy but i think it is neat be able to peel of numbers that do not even need to be considered for primality test.
> >
> > I wonder if i am correct assuming that the integers will be reduced with.
> > 510510=2*3*5*7*11*13*17 so using base 510510 the integers will be reduced with.
> > 1/2+1/3+1/5+1/7+1/11+1/13+1/17... adding next prime to list, so the reduction will go on forever using the sieve as the base gets higher and higher.
> > No that adds up to 1.40284617343...
> > So what is the forumula calculating the reduction?
> >
> > 1/2 -1/3-1/5-1/7-1/11-1/13-1/17...
> > +1/3 -1/5-1/7-1/11-1/13-1/17...
> > +1/5 -1/7-1/11-1/13-1/17...
> > +1/7 -1/11-1/13-1/17...
> > +1/11 -1/13-1/17...
> > +1/13 -1/17...
> > +1/17 -...
> >
> > Is that it?
> > ===========
> > It seem holding/storing the counter values->vectors in an array for bases up to 10^10 will be no problem.
> >
> > Given 64-bit integers it would take 4 GB.
> > =========================================
> >
> > 1 10 4
> > 2 100 25
> > 3 1,000 168
> > 4 10,000 1,229
> > 5 100,000 9,592
> > 6 1,000,000 78,498
> > 7 10,000,000 664,579
> > 8 100,000,000 5,761,455
> > 9 1,000,000,000 50,847,534
> > 10 10,000,000,000 455,052,511
> > 11 100,000,000,000 4,118,054,813
> > 12 1,000,000,000,000 37,607,912,018
>
> In fact i already implemented the tools to factor an integer in linear time if you check out my baseconversion. This is just removing numbers not necessary to check.

http://jt.node365.se/baseconvers...

Ben Bacarisse

1/17/2016 7:52:00 PM

jonas.thornvall@gmail.com writes:

> Den söndag 17 januari 2016 kl. 18:03:19 UTC+1 skrev jonas.t...@gmail.com:
>> Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
>> > jonas.thornvall@gmail.com writes:
>> >
>> > > Maybe we could have a challenge finding the base with best reducion
>> > > upto 100 000000? One probably do not want to store more vectors than
>> > > that in memory, and i guess
>> > >
>> > > Reducing composites in the integer field
>> > > http://jt.node365.se/comp...
>> >
>> > Why don't you engage with what people say? That function called
>> > factor_it is very peculiar. What is it supposed to do?
>> >
>> > <snip>
>> > --
>> > Ben.
>>
>> Here you can see what it does.
>>
>> http://jt.node365.se/composit_...
>
> It is a primality check algorithm.

It returns true for n == 1 up to (and including) n == 4. Some of those
numbers are prime and some are not.

<snip>
--
Ben.

Darren Jackson

1/17/2016 8:47:00 PM

> jonas.thornvall@gmail.com wrote in message
> news:5b608a56-e16b-4467-a0ce-4e30f6796920@googlegroups.com...

> Maybe we could have a challenge finding the base with best reducion upto
> 100 000000?
> One probably do not want to store more vectors than that in memory, and i
> guess

[...]

FWIW, here is some older code that finds primes. Its not a sieve, but oh
well:

https://groups.google.com/d/msg/comp.lang.javascript/ieCClS2d3kA/0-...
______________________________________________________________
<!DOCTYPE html>
<html>
<title>Primes</title>

<script type="text/javascript">
function is_prime(n)
{
if (isNaN(n) || ! isFinite(n) || n % 1 || n < 2)
return false;

if (! (n % 2)) return (n == 2);
if (! (n % 3)) return (n == 3);

var m = Math.sqrt(n);

for (var i = 5; i <= m; i += 6)
{
if (! (n % i) || ! (n % (i + 2)))
return false;
}

return true;
}

function count_prime(m)
{
var c = 0;

for (var n = 2; n < m; ++n)
if (is_prime(n)) ++c;

return c;
}

function main()
{
console.time("count_prime");

var c = count_prime(20000000);

console.timeEnd("count_prime");

alert("Found " + c + " Primes.");
}
</script>

<body onload="main();">

</body>
</html>
______________________________________________________________

;^)

JT

1/17/2016 9:43:00 PM

Den söndag 17 januari 2016 kl. 20:52:00 UTC+1 skrev Ben Bacarisse:
> jonas.thornvall@gmail.com writes:
>
> > Den söndag 17 januari 2016 kl. 18:03:19 UTC+1 skrev jonas.t...@gmail.com:
> >> Den söndag 17 januari 2016 kl. 17:24:33 UTC+1 skrev Ben Bacarisse:
> >> > jonas.thornvall@gmail.com writes:
> >> >
> >> > > Maybe we could have a challenge finding the base with best reducion
> >> > > upto 100 000000? One probably do not want to store more vectors than
> >> > > that in memory, and i guess
> >> > >
> >> > > Reducing composites in the integer field
> >> > > http://jt.node365.se/comp...
> >> >
> >> > Why don't you engage with what people say? That function called
> >> > factor_it is very peculiar. What is it supposed to do?
> >> >
> >> > <snip>
> >> > --
> >> > Ben.
> >>
> >> Here you can see what it does.
> >>
> >> http://jt.node365.se/composit_...
> >
> > It is a primality check algorithm.
>
> It returns true for n == 1 up to (and including) n == 4. Some of those
> numbers are prime and some are not.
>
> <snip>
> --
> Ben.

It is not a prime sieve Ben it is looking for legs with only composites because those are redundant " and that is about 90 percent of the integers so the complete field is reduced with 2 orders of magnitude.

The other legs 10% can have startvalues that are composite but they hold primes. And they will be stored in an array for primality check.

Well javascript isn't ideal to read in values, but i think i can put half a million integers in a form that i read in at body onload.

Using the base those numbers will form vectors? with numbers that i will do primality check upon.

So what i basicly do is i throw away 90% of ***all integers***, it may seem weird but not weirder than throwing away the even numbers same principle different scale.

Stefan Weiss

1/17/2016 11:14:00 PM

On 01/17/2016 18:22, jonas.thornvall@gmail.com wrote:
> In fact i already implemented the tools to factor an integer in linear time

Congratulations, you just solved the RSA problem.

- stefan

comp.lang.javascript

Primality sieve challenge

JT

JT

Ben Bacarisse

JT

JT

JT

JT

Ben Bacarisse

Darren Jackson

JT

Stefan Weiss

x Login to ForumsZone