Smarandache prime(s)

[LaurV]

Originally Posted by ewmayer

BTW, if my estimate accurately captures the large-scale odds for primes in the sequence, checking probable primality (*please* only for the 4-of-every-30 terms which can possibly be prime, all else is a sheer waste of cycles) for n = 10^5 through 10^6 only boosts the odds of turning up a prime by ~10% over those for n < 10^5, from around 0.55 to around 0.60. So "you're gonna need a bigger boat", unless you get lucky.

I think your estimation is in the lower side, a lot. There are "odd" things going on there, full orders of magnitude which are not divisible by certain primes. If for example for some power of 10, for some prime p, we have 10^n=-1 (mod p) and s(10^n) is small (mod p), there would be no x between 10^n and 10^(n+1) such as s(x) is divisible by that p. For example, there is no s(n) divisible by 7 from n=10^5 to n=10^6, and there is no s(n) divisible by 11 from n=10^1 to 10^2, nothing from 10^3 to 10^4, and so on for other primes. For every prime p, you can find some 10^n which is -1 (mod p), and s(10^n) is "convenient", and in that case, you will have no s(x) divisible to that p, in all interval 10^n<x<10^(n+1). Moreover, for any set of primes, p1, p2, etc, you can "intersect" those, and then find a very BIG n, such as s(10^n+1),...s(10^n+2)... up to s(10^(n+1)-1) are not divisible by ANY primes in that set. I think this is the way to demonstrate the fact that there are an infinite number of primes in this sequence (which I believe it is true, but the demonstration is far away). In fact, thinking like that, the subsequence with indexes 1, 7, 13, 19 (mod 30), (these are the only one who survive sieving with 2, 3, and 5) contains mostly primes (no, it is not a mistake!) for a power of 10 enough high... hehe...

[science_man_88]

Originally Posted by ATH

53,332 of these factors are 3 which is exactly 2/3 for some reason, I included all those for completeness.

The reason is explained above badly by me, basically think of it this way every time you appended a new number you add it's sum of digits to the sum of digits of the previous number. sum of digits mod 3 checks for divisibility by 3. That said there are two ways to end up at a value of 0 mod 3, start at 0 and add 1 and 2 mod 3 on the end or start with 0 mod 3 and add 0 mod 3. so from the sequence ( assume a 0 start for simplicity).

0(0 mod 3),1 ( 0 +1 mod 3),12 ( 0 + 1 +2 mod 3 =0),123(0+0 mod 3=0),1234(0+1 mod 3),12345(1+2 mod 3=0),123456(0+0 mod 3=0)...

[R. Gerbicz]

If 10^d<=n<10^(d+1), then s(n) has got less than (d+1)*10^(d+1) digits. ( it has got exactly d*10^d-(10^d-1)/9+(d+1)*(n-10^d) digits ). We have 9*10^d choices for n, this gives approx. 9*10^d/log(10^((d+1)*10^(d+1)))=0.9/log(10)/(d+1) primes if s(n) is a random number. So up to n we expect const*log(log(n)) primes. (sum of c0/d for d=1,..,log10(n)).

LaurV's idea doesn't change this too much, for a particular d it gives even: c0*log(d)/d primes and not c1/d. But shows that s(n) is NOT random.

[LaurV]

Indeed you are right, it does not change too much
I was only amazed by the fact, aftereffect, when I ran the sieve I thought there is an error in code, because there was no s(n) divisible by 7 from n=100k to n=1M, and this is 900 000 consecutive terms! None of them divisible by 7. Then I started digging and found the math behind, like RDS would say, first compute, and think after...

[wombatman]

Originally Posted by ATH

I'm also working on this, so maybe we should start coordinating ranges? Are you sieving and then running PRP test with PFGW on the survivors?

I have sieved n=1 to 200,000 up to p=68,000,000 so far. Out of the 79,999 numbers from 3 to 199,999 which are 1,3,7,9 mod 10, I found factors for 76,924:
smarandachefactors.txt
53,332 of these factors are 3 which is exactly 2/3 for some reason, I included all those for completeness.


Here are the remaining 79999-76924 = 3075 n's up to 200,000: smarandacheremaining.txt

I'm doing a basic sieve of the index (the n values) based on the 4 types of possible candidates mentioned above (1, 7, 13, 19 mod 30) and then outputting any candidates via a python script to a text file. Then I'm using PFGW for shallow trial factoring and PRP testing. It's worked pretty well. Even when I only sieved out the indexes divisible by 5, I could run through a range of 1000 candidates in about a day on a single core.

Also, what were you using to factor?

[science_man_88]

Originally Posted by LaurV

Indeed you are right, it does not change too much
I was only amazed by the fact, aftereffect, when I ran the sieve I thought there is an error in code, because there was no s(n) divisible by 7 from n=100k to n=1M, and this is 900 000 consecutive terms! None of them divisible by 7. Then I started digging and found the math behind, like RDS would say, first compute, and think after...

http://vixra.org/pdf/1005.0104v2.pdf linked to by the OEIS sequence page says some divide by 7 etc.

[ATH]

What is the argument that only 1,7,13,19 mod 30 can be prime?

I made my own C program to factor. For each prime p it runs through all 200,000 values. If it finds a factor it checks the array if it is missing and writes it to a file if needed.

for(a=1;a<=200000;a++)
{
	b=sprintf(str,"%i",a);
	for(c=0;c<strlen(str);c++)
	{
		d=(d*10+str[c]-48)%p;
	}
	if (d==0 && ((buf->test(a))==1))
	{
		fprintf(fil,"%i\t%i",a,p); fputc(13,fil); fputc(10,fil);
		buf->reset(a);
		fa++;
	}
}

Originally Posted by wombatman

Then I'm using PFGW for shallow trial factoring and PRP testing.

Is PFGW any good at trial factoring? I only tried a few times but it seems very slow?

[science_man_88]

Originally Posted by ATH

What is the argument that only 1,7,13,19 mod 30 can be prime?

that any index that's 0 or 2 mod 3 divides by three and that 5 divides one of the resulting classes mod 30 to leave only 1,7,13,19 left.

edit: in fact it can be shown that index n with divisor r can only divide by r if index n-1 does simply because s(n)=s(n-1)*10^ceil(log(n))+n
and a general divisibility rule is if you subtract a multiple of your attempted divisor the original number you subtract from is only a multiple of that divisor if the resulting number after subtraction is a multiple of the divisor. okay other than 5 it looks like. edit3: doh I realize it depends on the next power of 10 mod that divisor as well

[danaj]

Taking a hint from other projects, perhaps it would be worth someone dividing up the range into say 1k chunks, a task of trial division to result in just remaining candidates, then others can claim chunks to do PRP tests on the remainders. It seems there is a lot of duplicated work and effort going on.

[wombatman]

Originally Posted by ATH

What is the argument that only 1,7,13,19 mod 30 can be prime?

I made my own C program to factor. For each prime p it runs through all 200,000 values. If it finds a factor it checks the array if it is missing and writes it to a file if needed.

for(a=1;a<=200000;a++)
{
	b=sprintf(str,"%i",a);
	for(c=0;c<strlen(str);c++)
	{
		d=(d*10+str[c]-48)%p;
	}
	if (d==0 && ((buf->test(a))==1))
	{
		fprintf(fil,"%i\t%i",a,p); fputc(13,fil); fputc(10,fil);
		buf->reset(a);
		fa++;
	}
}

Is PFGW any good at trial factoring? I only tried a few times but it seems very slow?

Haven't tested it against other programs, to be honest. I knew that it would be able to handle the enormous numbers, and I figured that the factors would be small enough (which, for the most part, seems to be true) that it would suffice, in addition to its use for PRP testing.

I do like Dana's idea of splitting into chunks, whether we do trial division and PRP tests separately or together. I would suggest something like 5 or 10k chunks of n values since most of them are removed by the mod 30 sieve and another large number can be further removed by trial factoring. Just my two cents.

[ATH]

Originally Posted by wombatman

I do like Dana's idea of splitting into chunks, whether we do trial division and PRP tests separately or together. I would suggest something like 5 or 10k chunks of n values since most of them are removed by the mod 30 sieve and another large number can be further removed by trial factoring. Just my two cents.

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?