Smarandache prime(s?)

[sweety439]

Are there any research for the smallest Smarandache prime in base b?

[rogue]

I discovered my code for the sieve on my computer, so I was curious about the search. I see that the PRPNet server is down. What is the status of the search?

[Batalov]

The search was finished to 10^6.

[Batalov]

Originally Posted by Neil J. A. Sloane, OEIS Foundation

@Serge-
If you write the numbers in descending order, 1, 21, 321, 4321, 54321, ..., "n n-1 ... 321" (this is A000422 in the OEIS), then two primes are known, for n = 82 and 37765 . This is A176024, but it only has 2 terms. Can you get one more term? This might be child's play for you!

Best regards
Neil

Challenge accepted!

I wrote a different sieve for Smr(n), sieved and (with Ryan) we will test the survivors up to n<=500000 for starters.

A few interesting facts:
1. Both Sm(n) and Smr(n) are trivially divisible by 3 for all n != 1 (mod 3). Why? Because by definition they have all numbers from 1 to n, written out. Now for divisibility of 3, sum all digits up, and this is the same as summing up numbers from 1 to n. That's n(n+1)/2 and it will be divisible by 3 for n == 0 or 2 (mod 3)
2. Some formulae for Smr() for 2-digit, 3-, 4-, 5- , 6-digit size ranges of n:

#constant values (note that they are = Smr(99), Smr(999) and so on)
c2=(98*10^191+879*10^10+121)/99^2
c3=(998*10^2701-989)/999^2*10^191+c2
c4=(9998*10^36001-9989)/9999^2*10^2892+c3
c5=(99998*10^450001-99989)/99999^2*10^38893+c4

# Now, Smr() for 2-digit n values, for 3-, 4-, 5-, 6-digit (and can be extended, now that you see the rules):
Smr2(n)=((n*99-1)*10^(2*n-19)-89)/99^2*10^10+(8*10^10+1)/9^2
Smr3(n)=((n*999-1)*10^(3*n-299)-989)/999^2*10^191+c2
Smr4(n)=((n*9999-1)*10^(4*n-3999)-9989)/9999^2*10^2892+c3
Smr5(n)=((n*99999-1)*10^(5*n-49999)-99989)/99999^2*10^38893+c4
Smr6(n)=((n*999999-1)*10^(6*n-599999)-999989)/999999^2*10^488894+c5

#for the sieve, obviously, implement this: for every prime, loop { solve for n and remove it from list }

P.S. Once one sums up power series similar to Sum(k*10^k), the result is rather aestetically pleasing (except the constants c_d keep piling up),

[frmky]

two primes are known

n=82 is trivial, but is 37765 proven or just prp? If proven, how?

[Batalov]

Originally Posted by frmky

n=82 is trivial, but is 37765 proven or just prp? If proven, how?

I guess Neil was typing fast. Of course it is a PRP (it is 177719 decimal digits in length; btw, apparently I just now added it to FactorDB for the first time... and to PRPtop).

It can be written explicitly as a formula but the c_d coefficients/addends will kill any hope for N+-1 factorization.

[frmky]

Originally Posted by Batalov

the c_d coefficients/addends will kill any hope for N+-1 factorization.

That's what I concluded, but I wondered whether I was overlooking something.

[Batalov]

I had posted my 3-4-year old sieve for Sm() (many posts above).

I have now refactored and somewhat improved a similar sieve for Smr() and I am fairly content with the result; why? because while I can directly orthogonally verify that my factors are correct, e.g.
pfgw -N -od -q"Smr(1094410)%130152847681"
returns "Zero(0)"
in contrast, if I run
pfgw -N -f99999 q"Smr(1094410)"
it runs for hours to reach the factor (or cannot reach it even then).

...but I sieve all values (10-40 thousand per batch) at once, while PFGW works on one at a time. So it is pretty good for elimination. And then Ryan's cluster for the final verdict. Too bad we weren't lucky with Sm(); no (PR)primes are still known while they are definitely expected to exist.
I am more optimistic about Smr() -- it is 2.5x "denser".

[JeppeSN]

There is a Numberphile video out today where Neil Sloane describes these efforts:
https://www.youtube.com/watch?v=vKlVNFOHJ9I
/JeppeSN

[Batalov]

Originally Posted by JeppeSN

There is a Numberphile video out today where Neil Sloane describes these efforts:
https://www.youtube.com/watch?v=vKlVNFOHJ9I
/JeppeSN

Now we see why Neil asked about it

I have never looked at the up-and-down variety that Neil was describing, but it is clear that those can be easily scripted using PFGW. The two primes that he mentioned are written as
Sm(9)*10^11+Smr(10)
Sm(2445)*10^8677+Smr(2446)

Writing a sieve is also feasible, just takes some writing. Maybe on the weekend. Without sieving, simply testing those numbers will not get one very far. Curiously, these are remarkably frequently divisible by 13 (and by 3 of course).

[Batalov]

P.S. A pet peeve. NJAS keeps calling them "primes" in the video.
They aren't, strictly speaking. Even that Sm(2445)*10^8677+Smr(2446) is not proven, but it can be with a bit of ECPP-ing.