Re: Primality sieve challenge

Newsgroups	comp.lang.javascript
Date	2016-01-17 09:22 -0800
References	<5b608a56-e16b-4467-a0ce-4e30f6796920@googlegroups.com> <871t9gfa2z.fsf@bsb.me.uk> <8b01caa9-8c09-4e69-915b-81b67eba7edc@googlegroups.com> <0b16c016-5128-4b68-8046-fbec55700ec3@googlegroups.com>
Message-ID	<60329a65-27f8-483e-bd6e-e262e952ee6f@googlegroups.com> (permalink)
Subject	Re: Primality sieve challenge
From	jonas.thornvall@gmail.com

Show all headers | View raw

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/composite.html
> > > 
> > > 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_llegs.html
> 
> 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.

Thread

Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 01:40 -0800
  Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 02:20 -0800
  Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-17 16:24 +0000
    Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:03 -0800
      Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:17 -0800
        Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 09:22 -0800
          Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 11:32 -0800
          Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-18 00:13 +0100
            Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:10 -0800
          Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 01:20 +0000
            Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 12:16 +0100
              Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 11:25 +0000
                Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 12:43 +0100
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:18 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 04:25 -0800
              Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 09:52 -0800
                Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 19:23 +0100
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-18 10:48 -0800
                Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 13:09 -0800
                Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-18 13:14 -0800
                Re: Primality sieve challenge "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2016-01-18 22:45 +0100
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 14:23 -0800
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 22:56 +0000
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 15:02 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 16:04 -0800
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-19 02:42 +0100
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 23:34 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 01:34 -0800
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-19 06:23 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 07:10 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 07:15 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 08:34 -0800
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-19 16:54 +0000
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-19 08:57 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 10:18 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-19 10:59 -0800
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-20 01:33 +0100
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-20 02:10 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-20 02:21 -0800
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-20 10:45 +0000
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-20 06:43 -0800
                Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-20 15:21 -0800
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-21 03:18 +0100
                Re: Primality sieve challenge Jon Ribbens <jon+usenet@unequivocal.co.uk> - 2016-01-21 12:12 +0000
                Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-21 23:20 +0000
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-22 19:44 +0100
                Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-23 21:50 +0000
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-24 01:26 +0100
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-23 17:54 -0800
                Re: Primality sieve challenge "Chris M. Thomasson" <nospam@no-spam.ws> - 2016-01-24 13:34 -0800
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-25 00:21 +0000
                Re: Primality sieve challenge Stefan Weiss <krewecherl@gmail.com> - 2016-01-25 03:08 +0100
                Re: Primality sieve challenge "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2016-01-24 19:35 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-25 03:53 -0800
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 19:32 +0000
        Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-17 19:51 +0000
          Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-17 13:43 -0800
  Re: Primality sieve challenge "Chris M. Thomasson" <nospam@nospam.nospam> - 2016-01-17 12:46 -0800
    Re: Primality sieve challenge Gene Wirchenko <genew@telus.net> - 2016-01-18 09:50 -0800
      Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-18 20:09 +0100
        Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-18 19:28 +0000
          Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-18 21:37 +0100
            Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-18 13:12 -0800
              Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 13:46 -0800
                Re: Primality sieve challenge jonas.thornvall@gmail.com - 2016-01-18 14:00 -0800
              Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 13:47 +0100
                Re: Primality sieve challenge Ben Bacarisse <ben.usenet@bsb.me.uk> - 2016-01-19 14:04 +0000
                Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 19:59 +0100
                Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-19 10:55 -0800
                Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-01-19 20:04 +0100
                Re: Primality sieve challenge Scott Sauyet <scott.sauyet@gmail.com> - 2016-01-19 13:42 -0800
                Re: Primality sieve challenge Erwin Moller <erwinmollerusenet@xs4all.nl> - 2016-01-21 17:21 +0100
                Re: Primality sieve challenge Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2016-02-03 19:52 +0100
        Re: Primality sieve challenge Dr J R Stockton <reply1600@merlyn.demon.co.uk.invalid> - 2016-01-19 19:43 +0000

csiph-web