Smarandache prime(s)

[Batalov]

I guess I'll start sieving 10⁵ < n < 10⁶, modestly as usual.
I've already given the obligatory hint in post #8: in each 10^k <= n < 10^k+1 region there is a simple polynomial formula. It is much easier to sieve that formula than pile up "numbers as strings".

Exercises:
A) calculate x+2x²+3x³+4x⁴+...+kx^k
B) calculate x^k-1+2x^k-2+3x^k-3+4x^k-4+...+(k-1)x+k (where x=10 and k=1..9). Hint: it is = (10[SUP]k+1[/SUP]-C)/81
C) calculate sum{j=10..k} j x^k-j (where x=100).
D) etc (where x=1000 and j=100..k), etc etc etc.
E) sum them up with proper weights

[LaurV]

Originally Posted by Batalov

It is much easier to sieve that formula than pile up "numbers as strings".

Whoops! Those first two functions had nothing to do with sieving and should not be in there! Stupid copy/paste.
Check the "s=(s*t[x]+n)%p;" in the sieve function.
OTOH, I see you modified one of my posts to put inside a movie, and things I didn't say... Shame on you!
Last time Ernst did that I was angry with him 20 minutes!

[Batalov]

For 10⁵ < n < 10⁶, , where C₆ is a (computable mod p) constant and is left as an exercise to the reader.
That's sievable over the whole range of n is one sweep. One can sieve that up to 10^12 .. 10^13.

Your "s=(s*t[x]+n)%p;" is not sieving -- it is trial division. How far can you trial div with that?

[wombatman]

Originally Posted by ATH

So you are currently doing 80k-90k and I will take 90k-100k?

Btw are you saving the residues from PFGW? Might be good to keep a list of them?

Sure, and yes, I'm logging everything from PFGW. The files are large, however. You will likely want to pare them down some (say, index with either its factor or residue).

[ATH]

Originally Posted by Batalov

For 10⁵ < n < 10⁶, , where C₆ is a (computable mod p) constant and is left as an exercise to the reader.
That's sievable over the whole range of n is one sweep. One can sieve that up to 10^12 .. 10^13.

Your "s=(s*t[x]+n)%p;" is not sieving -- it is trial division. How far can you trial div with that?

Why are we getting exercises? I do not recall signing up for any classes here...

I'm sure your sieving method is much faster and I'm pretty sure you are smarter than me, and probably smarter than many on this forum, but the way your are presenting this method strikes me as very arrogant. You posted a "hint" in post #8, but unfortunate we were all too stupid to get it.

Why did you start this thread about this problem? You had the superior method already and probably have the hardware resources to do this alone...

[Batalov]

I am sorry that you feel this way - but I honestly don't understand where this emotional outburst came from.

[LaurV]

Now don't you two get angry. I have this way of making people angry, but actually I like Serge
His "exercises" included. I got that part, what I didn't get is this:

Originally Posted by Batalov

Your "s=(s*t[x]+n)%p;" is not sieving -- it is trial division. How far can you trial div with that?

First, I said that the code can be made faster. It was just a demo. Where is yours?
Next, "sieving" to p=10 millions I may have 18000 (just an estimation) candidates left. You may sieve to 10^13 and have 17500. So?

Better do that sieving, and post the remaining file, so people can pick ranges...

And don't get me wrong, I am learning from your posts.

And DON'T MODIFY MY POSTS! Whatever you want to say, say it separate, or by PM (well, by PM is no fun, actually...hehe).

[Batalov]

Here are some formulae (I've scribbled them last night, so they are not fully simplified; the final implementation for sieving can be different):

A1(n)=(10^(n+1)-9*n-10)/81
A2(n)=((121*10^9-1002)*10^(2*n-17)-99*n-100)/9801     
# A2(99)=((121*10^9-1002)*10^181-9901)/9801
# A3(n)=((99901+A2(99)*999^2)*10^(3*n-297)-999*n-1000)/999^2
A3(n)=(((121*10^9-1002)*111^2*10^179-1099022)/121*10^(3*n-295)-999*n-1000)/999^2
# A3x=(((121*10^9-1002)*111^2*10^179-1099022)/121*10^2702-1000)/999^2-1
A4(n)=((9999001+A3x*9999^2)*10^(4*n-3996)-9999*n-10^4)/9999^2
# A4x=((9999001+A3x*9999^2)*10^36000-10^4)/9999^2-1
A5(n)=((999990001+A4x*99999^2)*10^(5*n-49995)-99999*n-10^5)/99999^2
# A5x=((999990001+A4x*99999^2)*10^450000-10^5)/99999^2-1
A6(n)=((99999900001+A5x*999999^2)*10^(6*n-599994)-999999*n-10^6)/999999^2

The sieve which would implement these can start from any arbitrary value. Not sure if C_6 * B^n - 999999*n -10^6 = 0 (mod p) can be solved faster than step-6 jump over all n values in the interval; if it can be, then one immediately knows which values to strike and then hop to next p.

So, e.g. for four cores, the four abc files for running 90000-10⁵ range could look like these (definitions can be made shorter):

ABC2 ((999990001+(((9999001+(((120999998998*111^2*10^179-1099022)/121*10^2702-1000)/111^2-81)*1111^2)*10^36000-10^4)/1111^2-81)*11111^2)*10^(5*$a-49995)-99999*$a-10^5)/99999^2
a: from 90001 to 99999 step 30
--
ABC2 ((999990001+(((9999001+(((120999998998*111^2*10^179-1099022)/121*10^2702-1000)/111^2-81)*1111^2)*10^36000-10^4)/1111^2-81)*11111^2)*10^(5*$a-49995)-99999*$a-10^5)/99999^2
a: from 90007 to 99999 step 30
--
ABC2 ((999990001+(((9999001+(((120999998998*111^2*10^179-1099022)/121*10^2702-1000)/111^2-81)*1111^2)*10^36000-10^4)/1111^2-81)*11111^2)*10^(5*$a-49995)-99999*$a-10^5)/99999^2
a: from 90013 to 99999 step 30
--
ABC2 ((999990001+(((9999001+(((120999998998*111^2*10^179-1099022)/121*10^2702-1000)/111^2-81)*1111^2)*10^36000-10^4)/1111^2-81)*11111^2)*10^(5*$a-49995)-99999*$a-10^5)/99999^2
a: from 90019 to 99999 step 30

One of the n>10^5 files (this one does have some arithmetic shortening; the upper four don't) looks like this:

ABC2 ((((((((1490840987654358*10^179-1099022)/121*10^2699-1)/111^2*1111^2-89981)*10^35999-1)/1111^2*11111^2-899981)*10^449999-1)/11111^2*111111^2-8999981)*10^(6*$a-599989)-999999*$a-10^6)/999999^2
a: from 100003 to 199999 step 30

Isn't that nicer than generating huge text files and feeding them to PFGW? This project isn't PiP (primes in pi) where this was inevitable.

These are free to use for anyone who doesn't want exercises. They are ready to run.
I, for one, live for brain exercises. Ten maelstrom sudokus to start the brain engine in the morning. Ten rubik assemblies from scramble. Ten struts, ten sit-ups, ten push-ups -- and ready for serious work. ;-)

[Batalov]

Originally Posted by LaurV

And DON'T MODIFY MY POSTS! Whatever you want to say, say it separate, or by PM (well, by PM is no fun, actually...hehe).

You did say the first two lines, eh? The video simply makes your message much clearer...
Don't deny that this is how (don't ask me why) you see the mods - like Jules. So it is your message - plain and clear.

I disagree! I say a completely different thing: the volunteer mods owe you nothing really, especially reading word salad which is by multiple precedents known to be very voluminous but always harmless. Some other people's word salad is occasionally very vile; that does have to be cleaned up in Aisle 11 every once in a while; but never sm88's. (And that was a compliment! )

[science_man_88]

Originally Posted by Batalov

<snip>can be solved faster than step-6 jump over all n values in the interval; if it can be, then one immediately knows which values to strike and then hop to next p.

it really comes down to coding efficiently for the jumps:

like I said in http://mersenneforum.org/showpost.ph...01&postcount=4

you can do a forstep and jump by 6 and just skip over things or you can use a parfor loop changing things based on mod 5 of the value you use to plug into 6y+1 but then to make it work efficiently you either need to code twice or equally split the code so it can make use of the most amount of resources to do everything quicker in parallel ( for example you could save the 6*y+1 index into a loop variable etc).

[Antonio]

Originally Posted by Batalov

Isn't that nicer than generating huge text files and feeding them to PFGW? This project isn't PiP (primes in pi) where this was inevitable.

I would hardly call 21kB, huge.
A quick Perl script only took 50min. to reduce the range 100k-200k to a PFGW ABC file with 2662 indices to check, using mod 30 test plus a bit of extra trial division.

I must admit that your method is much more elegant though.