I posted this in one of the Haskell groups a few days ago - but it's 
actually not to do with Haskell particularly, so...

I've stumbled on a slightly unusual way to find prime numbers. It goes 
like this. Suppose you're sitting here seiving prime numbers. We start 
by deleting 2 and all its multiples. That leaves us with a pattern like 
this:

-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-

Ignoring 1, the next place that has a dash is 3, so 3 is the next prime 
number. Deleting 3 and all its multiples, we get

-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-

In other words, an infinite list of twin "primes". Well anyway, the next 
uncrossed number is 5, so 5 is prime. Deletin 5 and all its multiplies 
yields

-#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-

And so forth. At each stage, we get a longer repeating pattern. If you 
take each of these lines and snip it down to just 1 repartition, you get

Initial: (-)
After 2: (-#)
After 3: (-###-#)
After 5: (-#####-###-#-###-#-###-#####-#)

The first pattern is 1 units long, the next is 2*1 = 2 units long, the 
next is 3*2 = 6 units long, and the last one is 5*6 = 30 units long. The 
"after 7" pattern is 7*30 = 210 units long, so I won't bother writing it 
out here. ;-)

You can use all this to write an algorithm for finding primes. Basically 
start with some pattern, find the next prime P (first uncrossed square 
ignoring 1), repeat the pattern P times, seive out all multiplies of P, 
go back to step 1. (In practice, you have to start from the "after 3" 
pattern for this to work properly.)

Initial:  -###-#
Find   P: 5
Repeat P: -###-#-###-#-###-#-###-#-###-#
Seive  P: -#####-###-#-###-#-###-#####-#
Find   P: 7
etc.

Actually, every dash in the grid (up to sqrt(grid size) is a prime 
number). So after less than a dozen iterations of this (very simple) 
algorithm, you can find all primes below 1,000,000. (!)

(Notice that the "normal" seiving algorithm keeps 5 and deletes only 
higher multiples of it. My algorithm deletes 5 itself as well. It must 
for the algorithm to work right...)

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> -#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
> -###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
> -#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-

  That last pattern is wrong. The first incorrectly (non-)marked place
is at 25. It also marks 41 as non-prime even though it is.

  Anyways, using the correct patterns, wuldn't it be better to preserve
the info about which of those are the primes?
  If we mark untested numbers with '-', primes with '!' and non-primes
with '#' then that would become:

-!-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
-!!#-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
-!!#!#-###-#-###-#-###-#####-#-###-#-###-#-###-#-###-#####-#-#####-###-
-!!#!#!###-#-###-#-###-#####-#-#####-###-#-###-#####-#####-#-#####-###-

etc.

  In the end you end up with:

-!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###

  OTOH using this algorithm you basically need to fix the number of
primes you want to calculate. It also requires random access so it's
not very usable with linked lists.

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>> -#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
>> -###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
>> -#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-
> 
>   That last pattern is wrong.

Right. Well I typed these out by hand, so if there are errors then it's 
because my typing is inaccurate. :-S

>   Anyways, using the correct patterns, wuldn't it be better to preserve
> the info about which of those are the primes?
>   If we mark untested numbers with '-', primes with '!' and non-primes
> with '#' then that would become:
> 
> -!-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
> -!!#-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
> -!!#!#-###-#-###-#-###-#####-#-###-#-###-#-###-#-###-#####-#-#####-###-
> -!!#!#!###-#-###-#-###-#####-#-#####-###-#-###-#####-#####-#-#####-###-
> 
> etc.
> 
>   In the end you end up with:
> 
> -!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###

Well, then you'd need more bits per number. (I'm using a simple bitmap 
at the moment.) Still, it could work...

>   OTOH using this algorithm you basically need to fix the number of
> primes you want to calculate. It also requires random access so it's
> not very usable with linked lists.

Yeah, pretty much.

For finding "really big" prime numbers, it seems that space rather than 
time is going to be the issue. The algorithm more or less forces you to 
go up in predetermined step sizes. I would think you'll run out of RAM 
fairly quickly.

It's not entirely clear to me that this algorithm is any faster or 
otherwise "better" than the normal seiving algorithm. (As in, if you 
want all primes below N, find all primes below sqrt(N) and then sieve a 
larger list from 1 to N. And possibly find the smaller primes list by 
the same method recursively.)

It's certainly an "unusual" algorithm though. At least, I've not seen it 
before...

Post a reply to this message

Orchid XP v7 <voi### [at] devnull> wrote:
> >   In the end you end up with:
> > 
> > -!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###

> Well, then you'd need more bits per number.

  Not really, because the end result only has '#' and '!'. You simply
have to keep an index to the next untested value in a variable.

-- 
                                                          - Warp

Post a reply to this message

Orchid XP v7 wrote:
> I posted this in one of the Haskell groups a few days ago - but it's 
> actually not to do with Haskell particularly, so...
> 
> I've stumbled on a slightly unusual way to find prime numbers. It goes 
> like this. Suppose you're sitting here seiving prime numbers. We start 
> by deleting 2 and all its multiples. That leaves us with a pattern like 
> this:
> 
> -#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-#-
> 
> Ignoring 1, the next place that has a dash is 3, so 3 is the next prime 
> number. Deleting 3 and all its multiples, we get
> 
> -###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-#-###-
> 
> In other words, an infinite list of twin "primes". Well anyway, the next 
> uncrossed number is 5, so 5 is prime. Deletin 5 and all its multiplies 
> yields
> 
> -#####-###-#-###-#-#####-#-###-#-###-#####-###-#-###-#-#####-###-#-###-
> 
> And so forth. At each stage, we get a longer repeating pattern. If you 
> take each of these lines and snip it down to just 1 repartition, you get
> 
> Initial: (-)
> After 2: (-#)
> After 3: (-###-#)
> After 5: (-#####-###-#-###-#-###-#####-#)
> 
> The first pattern is 1 units long, the next is 2*1 = 2 units long, the 
> next is 3*2 = 6 units long, and the last one is 5*6 = 30 units long. The 
> "after 7" pattern is 7*30 = 210 units long, so I won't bother writing it 
> out here. ;-)
> 
> You can use all this to write an algorithm for finding primes. Basically 
> start with some pattern, find the next prime P (first uncrossed square 
> ignoring 1), repeat the pattern P times, seive out all multiplies of P, 
> go back to step 1. (In practice, you have to start from the "after 3" 
> pattern for this to work properly.)
> 
> Initial:  -###-#
> Find   P: 5
> Repeat P: -###-#-###-#-###-#-###-#-###-#
> Seive  P: -#####-###-#-###-#-###-#####-#
> Find   P: 7
> etc.
> 
> Actually, every dash in the grid (up to sqrt(grid size) is a prime 
> number). So after less than a dozen iterations of this (very simple) 
> algorithm, you can find all primes below 1,000,000. (!)
> 
> (Notice that the "normal" seiving algorithm keeps 5 and deletes only 
> higher multiples of it. My algorithm deletes 5 itself as well. It must 
> for the algorithm to work right...)

The pattern that you have to keep and process for each prime grows 
factorially.  Doesn't look too big for small n but it certainly takes 
off quickly.

So by the time that you are able to deliver say the 1000th prime number, 
the pattern would be *rather* large.  And you need to keep maintaining 
the growing pattern to continue delivering the 1001st, 1002nd etc.

If you choose to stop accumulating the pattern at some point then you 
are back to classic Sieve of Eratosthenes with a slightly different way 
to build up the array to its desired size.

I know you were just offering an insight not thinking it was actually 
practical.

How about we call this Orchid's Algorithm - because it is 'bloomin 
ridiculous' :)

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>>>   In the end you end up with:
>>>
>>> -!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###
> 
>> Well, then you'd need more bits per number.
> 
>   Not really, because the end result only has '#' and '!'. You simply
> have to keep an index to the next untested value in a variable.

...and *this* is why Warp is a high-end games programmer and I'm not. 
Heh. ._.

Post a reply to this message

Paul Fuller wrote:

> How about we call this Orchid's Algorithm - because it is 'bloomin 
> ridiculous' :)

Ooo... I *like* that! :-D

Post a reply to this message

Warp wrote:
> Orchid XP v7 <voi### [at] devnull> wrote:
>>>   In the end you end up with:
>>>
>>> -!!#!#!###!#!###!#!###!#####!#!#####!###!#!###!#####!#####!#!#####!###
> 
>> Well, then you'd need more bits per number.
> 
>   Not really, because the end result only has '#' and '!'. You simply
> have to keep an index to the next untested value in a variable.
> 
but take care that when concatenating the strings you set all fields 
below that number to # first.

Post a reply to this message