Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #29280 > unrolled thread

Primality sieve challenge

Back to article view | Back to comp.lang.javascript

Contents

  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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#29372

On Wednesday, January 20, 2016 at 4:21:47 AM UTC-6, jonas.t...@gmail.com wrote:
> Den onsdag 20 januari 2016 kl. 11:10:28 UTC+1 skrev jonas.t...@gmail.com:

> > It seem obvious to me that multiplication can be done in linear time, maybe it is because i've been thinking about if before.
> 
> In fact it seem so obvious that can wonder how it can escape people, probably it has something todo with the way math is teached.

To quote Frank Atanassow [1]:

"There is a big difference between something being true, knowing that it is true, and knowing that you know it is true. We might say something is true if it is a theorem; we know that it's true if we know it is a theorem and there exists a proof; and we know that we know it's true if we can exhibit a proof that we understand.

If the first were the same as the last, then there would be no need for science or mathematics or objectively verifiable methods of argument. Furthermore, we would not be having this discussion in the first place, since truth would be self-evident, and so we could not possibly disagree."

In this case you must provide a proof (a program) that can perform multiplication in O(n) time to convince anyone besides yourself. I have already referenced the fasted method of multiplication I am aware of [2]

[1] <http://lambda-the-ultimate.org/node/175#comment-1333>
[2] <https://en.wikipedia.org/wiki/Multiplication_algorithm#Fourier_transform_methods>

[toc] | [prev] | [next] | [standalone]

#29381

jonas.thornvall@gmail.com wrote wrote:
> skrev jonas.t...@gmail.com:


>> It seem obvious to me that multiplication can be done in linear time, maybe 
>> it is because i've been thinking about if before.
> 
> In fact it seem so obvious that can wonder how it can escape people, probably
> it has something todo with the way math is teached.

In fact, it is quite simple to do this.  You start with a squared circle,
trisect the angle, and it should become obvious...

  -- Scott

[toc] | [prev] | [next] | [standalone]

#29387

On 01/20/2016 01:33, Stefan Weiss wrote:
> A few hours ago, the new largest known prime number has been published:
> 2^74207281 - 1. It has 22338618 decimal digits.

Fun fact: the number is a Mersenne prime, so its binary notation
contains only 1s. This makes it an ideal candidate for compression...
and here it is, in all its bzipped and base64-encoded glory:

QlpoOTFBWSZTWZD3yeYAAABgAKAAABAACKAAMM00ClR6exFBUMKCobhdyRThQkJD3yeY

(The uncompressed file size was 9275911 bytes: 01 FF FF FF ...
Compressed file size: 51 bytes using bzip2.)


- stefan

[toc] | [prev] | [next] | [standalone]

#29395

On 2016-01-21, Stefan Weiss <krewecherl@gmail.com> wrote:
> On 01/20/2016 01:33, Stefan Weiss wrote:
>> A few hours ago, the new largest known prime number has been published:
>> 2^74207281 - 1. It has 22338618 decimal digits.
>
> Fun fact: the number is a Mersenne prime, so its binary notation
> contains only 1s. This makes it an ideal candidate for compression...
> and here it is, in all its bzipped and base64-encoded glory:
>
> QlpoOTFBWSZTWZD3yeYAAABgAKAAABAACKAAMM00ClR6exFBUMKCobhdyRThQkJD3yeY
>
> (The uncompressed file size was 9275911 bytes: 01 FF FF FF ...
> Compressed file size: 51 bytes using bzip2.)

Here it is compressed even more: '2^74207281-1'. 12 bytes!
Here it is compressed even more: '\x31\x50\x6c\x04'. 4 bytes!

[toc] | [prev] | [next] | [standalone]

#29399

In comp.lang.javascript message <n7k49m$54l$1@news.albasani.net>, Tue,
19 Jan 2016 02:42:13, Stefan Weiss <krewecherl@gmail.com> posted:

>
>A common estimate for the number of atoms in the observable universe is
>10^80. That's a number with ~80 digits. You're going for a number with
>17425170 digits. The raw decimal number takes ~17MB to store in an
>uncompressed ASCII file, like you're proposing. If you were to print it
>out, you'd need around 4k-5k sheets of paper (pages).

<g>
That shows the importance of optimising the base.  One would only need
about 5/6 as many digits in ordinary Hex.  In binary, one would need 3.3
times as many digits; but each digit could be compressed on the paper to
a single black or white pixel, and one could do even better with
coloured pixels.  I estimate that a really good inkjet printer might get
the whole lot onto a single sheet of paper.
</g>

Via the Wayback Machine, http://www.merlyn.demon.co.uk/js-misc0.htm has
JavaScript code for Sieves of Eratosthenes.

-- 
 (c) John Stockton, Surrey, UK.  ¬@merlyn.demon.co.uk   Turnpike v6.05   MIME.
 Merlyn Web Site <                       > - FAQish topics, acronyms, & links.

[toc] | [prev] | [next] | [standalone]

#29411

On 01/22/2016 00:20, Dr J R Stockton wrote:
> That shows the importance of optimising the base.  One would only need
> about 5/6 as many digits in ordinary Hex.  In binary, one would need 3.3
> times as many digits; but each digit could be compressed on the paper to
> a single black or white pixel, and one could do even better with
> coloured pixels.  I estimate that a really good inkjet printer might get
> the whole lot onto a single sheet of paper.

Such posters actually exist, for smaller the smaller (but still huge)
Mersenne prime M44 with around 1 million digits. Unfortunately, the
company that produced them shut down after Richard Crandall died, and
there aren't a lot of images of those posters.

The company used to package a jeweler's loupe with them so that the
digits could be read. Without it, they just look like gray rectangles:

  http://aperiodical.com/wp-content/uploads/2013/04/poster-rachel.jpg

Through the loupe:

  http://www.mersenneforum.org/attachment.php?attachmentid=12131

Pixels are a possiblity, of course, but prime numbers have pretty good
pseudo-randomness, so the gray blob effect would just be more
pronounced. I'd expect something similar for colored pixel plots.
If we did find patterns in a plot of a prime number... things could get
interesting.

Pixel plots are often used to visually examine the randomness of series
of numbers. For example, here's the output of V8's Math.random()
function before and after the PRNG fix in December:

  http://goo.gl/8M4kuk


- stefan

[toc] | [prev] | [next] | [standalone]

#29422

In comp.lang.javascript message <n7ttan$3o3$1@news.albasani.net>, Fri,
22 Jan 2016 19:44:38, Stefan Weiss <krewecherl@gmail.com> posted:

>...

>Pixel plots are often used to visually examine the randomness of series
>of numbers. For example, here's the output of V8's Math.random()
>function before and after the PRNG fix in December:
>
>  http://goo.gl/8M4kuk

Can you say more about the V8 PRNG fix, including what (I suppose) it is
V8 of?  Or is that VB, in which case in which system(s)?

I still maintain the master of
<http://web.archive.org/web/20150905080518/http://www.merlyn.demon.co.uk
/js-randm.htm>.


-- 
 (c) John Stockton, Surrey, UK.  ¬@merlyn.demon.co.uk   Turnpike v6.05   MIME.
 Merlyn Web Site <                       > - FAQish topics, acronyms, & links.

[toc] | [prev] | [next] | [standalone]

#29426

On 01/23/2016 22:50, Dr J R Stockton wrote:
> In comp.lang.javascript message <n7ttan$3o3$1@news.albasani.net>, Fri,
> 22 Jan 2016 19:44:38, Stefan Weiss <krewecherl@gmail.com> posted:
> 
>> Pixel plots are often used to visually examine the randomness of series
>> of numbers. For example, here's the output of V8's Math.random()
>> function before and after the PRNG fix in December:
>>
>>  http://goo.gl/8M4kuk
> 
> Can you say more about the V8 PRNG fix, including what (I suppose) it is
> V8 of?  Or is that VB, in which case in which system(s)?
> 
> I still maintain the master of
> <http://web.archive.org/web/20150905080518/http://www.merlyn.demon.co.uk
> /js-randm.htm>.

I was referring to V8, Google's JavaScript engine used in Chrome,
Node.js and other projects. I was about to write that it's oddly named,
but when the other engines have names like SpiderMonkey or ChakraCore,
it fits right in. The name was taken in reference to the 8-cylinder
V-shaped automobile engine, by the way, not version 8.

Last year, a problem was discovered in V8's PRNG. They were using a
rather obscure generator function for a long time, and an early/buggy
version of it, too. The awful distribution of the pseudo-random output
of that function went undetected for years, until somebody encountered
unexplainabled hash collisions and pinned V8 as the culprit. They found
a comment along the lines of "we should have used a Mersenne Twister
instead" from a code reviewer in the commit log, but the PRNG was
committed like that anyway.

After they were notified of the bug, it was quickly fixed by exchanging
the generator for something more suitable... I can't remember the name,
but it wasn't MT.

As bad as that pixel plot looks, the consequences weren't that grave
(except maybe for the company with the hash collision). Math.random()
was never intended or specified as a cryptographically secure PRNG.
These days we have the Web Crypto API for that. It's still in the draft
stage, but at least partially implemented in most current browsers.


- stefan

[toc] | [prev] | [next] | [standalone]

#29428

On Friday, January 22, 2016 at 12:44:49 PM UTC-6, Stefan Weiss wrote:
> On 01/22/2016 00:20, Dr J R Stockton wrote:
> > That shows the importance of optimising the base.  One would only need
> > about 5/6 as many digits in ordinary Hex.  In binary, one would need 3.3
> > times as many digits; but each digit could be compressed on the paper to
> > a single black or white pixel, and one could do even better with
> > coloured pixels.  I estimate that a really good inkjet printer might get
> > the whole lot onto a single sheet of paper.
> 
> Such posters actually exist, for smaller the smaller (but still huge)
> Mersenne prime M44 with around 1 million digits. Unfortunately, the
> company that produced them shut down after Richard Crandall died, and
> there aren't a lot of images of those posters.
> 
> The company used to package a jeweler's loupe with them so that the
> digits could be read. Without it, they just look like gray rectangles:
> 
>   http://aperiodical.com/wp-content/uploads/2013/04/poster-rachel.jpg
> 
> Through the loupe:
> 
>   http://www.mersenneforum.org/attachment.php?attachmentid=12131
> 
> Pixels are a possiblity, of course, but prime numbers have pretty good
> pseudo-randomness, so the gray blob effect would just be more
> pronounced. I'd expect something similar for colored pixel plots.
> If we did find patterns in a plot of a prime number... things could get
> interesting.
> 
> Pixel plots are often used to visually examine the randomness of series
> of numbers. For example, here's the output of V8's Math.random()
> function before and after the PRNG fix in December:
> 
>   http://goo.gl/8M4kuk


Ulam Spirals:
<https://en.wikipedia.org/wiki/Ulam_spiral>

[toc] | [prev] | [next] | [standalone]

#29432

On 1/23/2016 5:54 PM, Michael Haufe (TNO) wrote:
>> On Friday, January 22, 2016 at 12:44:49 PM UTC-6, Stefan Weiss wrote:
>> Pixel plots are often used to visually examine the randomness of series
>> of numbers. For example, here's the output of V8's Math.random()
>> function before and after the PRNG fix in December:
>>
>>    http://goo.gl/8M4kuk

> Ulam Spirals:
> <https://en.wikipedia.org/wiki/Ulam_spiral>

FWIW, here is a little graph I did a while back:

https://plus.google.com/101799841244447089430/posts/YeVfh7q5rD5

Here is a excerpt:
_______________________________________________
  this graph is based on the x and y axis representing their respective 
primes. So the point (0,4) would the the 1st and 5th prime numbers. The 
point (1, 3) would the be the 2nd and 4th prime numbers. The color is 
based on how far apart they are from each other. So, the distance of 
point (0, 1) would be abs(2 - 3).

I see some "wavy" squares all over the place. There is some sort of 
structure in the "prime color monitor"?

Humm...
_______________________________________________

;^)

[toc] | [prev] | [next] | [standalone]

#29433

"Chris M. Thomasson" <nospam@no-spam.ws> writes:

> On 1/23/2016 5:54 PM, Michael Haufe (TNO) wrote:
>>> On Friday, January 22, 2016 at 12:44:49 PM UTC-6, Stefan Weiss wrote:
>>> Pixel plots are often used to visually examine the randomness of series
>>> of numbers. For example, here's the output of V8's Math.random()
>>> function before and after the PRNG fix in December:
>>>
>>>    http://goo.gl/8M4kuk
>
>> Ulam Spirals:
>> <https://en.wikipedia.org/wiki/Ulam_spiral>
>
> FWIW, here is a little graph I did a while back:
>
> https://plus.google.com/101799841244447089430/posts/YeVfh7q5rD5

Very nice.

> Here is a excerpt:
> _______________________________________________
>  this graph is based on the x and y axis representing their respective
> primes. So the point (0,4) would the the 1st and 5th prime
> numbers. The point (1, 3) would the be the 2nd and 4th prime
> numbers. The color is based on how far apart they are from each
> other. So, the distance of point (0, 1) would be abs(2 - 3).

But this could be a bit clearer.  I want to know where the origin is
(top left?), and I'd word it like this: "In this graph the colour of
point (n, m) is determined by abs(p_n - p_m) i.e. by the difference
between the nth and mth prime, numbered from 0 (p_0 = 2, p_1 = 3, etc)."

I'd like to know what the integer to colour mapping is, too.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29435

On 01/25/2016 01:21, Ben Bacarisse wrote:
> "Chris M. Thomasson" <nospam@no-spam.ws> writes:
>> On 1/23/2016 5:54 PM, Michael Haufe (TNO) wrote:
>>
>>> Ulam Spirals:
>>> <https://en.wikipedia.org/wiki/Ulam_spiral>
>>
>> FWIW, here is a little graph I did a while back:
>>
>> https://plus.google.com/101799841244447089430/posts/YeVfh7q5rD5
> 
> Very nice.

Ulam spirals are fascinating, and those graphs are very nice indeed.
Just to be clear, though, they show patterns of prime numbers in the set
of positive integers, not patterns of digits (bits or decimal) in the
prime numbers themselves. I tried to find a study of how (pseudo-)random
the large primes actually are, but came up empty.

Speaking of large numbers, I found something bizarre today: somebody
published one of the largest named numbers in a set of books, and
actually got an ISBN for them. http://www.googolplexwrittenout.com/
offers all the digits of Googolplex in volumes of 1 million zeros each
(400 pages). They can be downloaded as PDF or ordered as printed books.
There are 10^94 volumes.


- stefan


PS (idle), this is what reading those books out loud could sound like,
with a talented narrator: https://youtu.be/umDCQNTkSCk (25 sec)

[toc] | [prev] | [next] | [standalone]

#29436

On Sunday, January 24, 2016 at 8:08:45 PM UTC-6, Stefan Weiss wrote:

> Speaking of large numbers, I found something bizarre today: somebody
> published one of the largest named numbers in a set of books, and
> actually got an ISBN for them. http://www.googolplexwrittenout.com/
> offers all the digits of Googolplex in volumes of 1 million zeros each
> (400 pages). They can be downloaded as PDF or ordered as printed books.
> There are 10^94 volumes.

See Graham's Number:

<https://en.wikipedia.org/wiki/Graham's_number>

From the page:

"As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, the smallest possible volume known to modern physics."

[toc] | [prev] | [next] | [standalone]

#29437

Den söndag 24 januari 2016 kl. 02:54:47 UTC+1 skrev Michael Haufe (TNO):
> On Friday, January 22, 2016 at 12:44:49 PM UTC-6, Stefan Weiss wrote:
> > On 01/22/2016 00:20, Dr J R Stockton wrote:
> > > That shows the importance of optimising the base.  One would only need
> > > about 5/6 as many digits in ordinary Hex.  In binary, one would need 3.3
> > > times as many digits; but each digit could be compressed on the paper to
> > > a single black or white pixel, and one could do even better with
> > > coloured pixels.  I estimate that a really good inkjet printer might get
> > > the whole lot onto a single sheet of paper.
> > 
> > Such posters actually exist, for smaller the smaller (but still huge)
> > Mersenne prime M44 with around 1 million digits. Unfortunately, the
> > company that produced them shut down after Richard Crandall died, and
> > there aren't a lot of images of those posters.
> > 
> > The company used to package a jeweler's loupe with them so that the
> > digits could be read. Without it, they just look like gray rectangles:
> > 
> >   http://aperiodical.com/wp-content/uploads/2013/04/poster-rachel.jpg
> > 
> > Through the loupe:
> > 
> >   http://www.mersenneforum.org/attachment.php?attachmentid=12131
> > 
> > Pixels are a possiblity, of course, but prime numbers have pretty good
> > pseudo-randomness, so the gray blob effect would just be more
> > pronounced. I'd expect something similar for colored pixel plots.
> > If we did find patterns in a plot of a prime number... things could get
> > interesting.
> > 
> > Pixel plots are often used to visually examine the randomness of series
> > of numbers. For example, here's the output of V8's Math.random()
> > function before and after the PRNG fix in December:
> > 
> >   http://goo.gl/8M4kuk
> 
> 
> Ulam Spirals:
> <https://en.wikipedia.org/wiki/Ulam_spiral>

Here you can rearrange primes in a quadratic numberfield, zoom in and out and rearrange it into rectangular and triangular if you like playing with patterns.

http://jt.node365.se/prime0.995/div.html

[toc] | [prev] | [next] | [standalone]

#29326

Gene Wirchenko <genew@telus.net> writes:

> On Mon, 18 Jan 2016 12:16:54 +0100, "Evertjan."
> <exxjxw.hannivoort@inter.nl.net> wrote:
>
>>Ben Bacarisse <ben.usenet@bsb.me.uk> wrote on 18 Jan 2016 in 
>>comp.lang.javascript:
>>
>>> jonas.thornvall@gmail.com writes:
>>> <snip>
>>>> In fact i already implemented the tools to factor an integer in linear
>>>> time if you check out my baseconversion.
>>> 
>>> Linear in what (i.e. what property of the integers is the algorithm's
>>> run-time a linear function of)?  (For the record, I don't believe you,
>>> but I'd like to know exactly what it is I don't believe.)
>>
>>Is there any other time than "linear time"?
>
>      Yes, of course.  It might be a language issue.  Execution in
> "linear time" means O(n).

But (just to be clear) my question was about what n is.  People often
forget to state it, though the context sometimes helps.  With claims
like "i already implemented the tools to factor an integer in linear
time" it's best not to rely on context!

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29291

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

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

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#29295

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

[toc] | [prev] | [next] | [standalone]

#29293

> 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-IwPBuMh2UJ
______________________________________________________________
<!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>
______________________________________________________________

;^) 

[toc] | [prev] | [next] | [standalone]

#29315

On Sun, 17 Jan 2016 12:46:51 -0800, "Chris M. Thomasson"
<nospam@nospam.nospam> wrote:

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

     It is a sieve.  It is optimised to not check some numbers that
could not be prime.  All primes >= 5 are of the form 6k +/- 1 where k
is a positive integer.

[snip]

Sincerely,

Gene Wirchenko

[toc] | [prev] | [next] | [standalone]

#29323

Gene Wirchenko wrote:

> […]  All primes >= 5 are of the form 6k +/- 1 where k is a positive
> integer.

Interesting thesis.  Prove it.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | SVN: <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | ES Matrix: <http://PointedEars.de/es-matrix>
Please do not cc me. / Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | comp.lang.javascript

csiph-web