Switching digits test

[PawnProver44]

Can anyone switch the digits of 9293392505711486960894715862 without adding or taking digits to form a prime? I am surprised to see if anyone can do that. Here is an example puzzle:

Original Number: 2841920

Prime formed: 4892201

This is just a small example, see. For larger numbers, I am not so sure.

[VBCurtis]

What are you not sure of? Writing the algorithm to test the possibilities?
Whether any such prime exists?

I mean, did you scramble a known prime (or did your professor for your homework), or just make up a string of digits that may or may not contain a prime when shuffled?

[PawnProver44]

Originally Posted by VBCurtis

What are you not sure of? Writing the algorithm to test the possibilities?
Whether any such prime exists?

I mean, did you scramble a known prime (or did your professor for your homework), or just make up a string of digits that may or may not contain a prime when shuffled?

It is a puzzle so I scrambled a known prime, but there may be other primes using the same digits that I do not know of. For almost any random number not a multiple of 3, this is possible.

[danaj]

'0011122233445556667788998999' is an simple example.

'9999988877666555443322102101' if you don't like leading zeros.
'9999988877666555220414012313' as one of many thousands of examples.

It's multiset permutations testing primality, but the only tricky bit is that there are a lot and if you're getting them in lexicographic order then you have to plow through a lot of leading zeros. I just reversed it. You could also use one of the many modules/packages/builtins that lets you shuffle an arbitrary deck/bag, if you wanted something more random looking. Loop pulling out random combinations until one is prime.

[PawnProver44]

I picked this number on my own: 44553815103018140629

I can only come up with two primes formed:

59445845011081062133

50540183611413058429

So about almost any number not a multiple of 3 this is possible for.

[a1call]

Here is one special case as a category:

A circular prime number is a number that remains prime on any cyclic rotation of its digits (in base 10).

https://en.wikipedia.org/wiki/List_o...ircular_primes

Another:

Primes that become a different prime when their decimal digits are reversed. The name "emirp" is obtained by reversing the word "prime".

https://en.wikipedia.org/wiki/List_o...numbers#Emirps

[LaurV]

Let's totally confuse the poor guy...

Single line pari/gp to write 20 primes, based on idea that there are n/log(n) primes there, so finding a random one won't take more than few milliseconds (one in 28*log(10)~=64 random trials will be prime).

gp > cnt=0; while(cnt<20,w=vecextract(v=eval(Vec("9293392505711486960894715862")),numtoperm(#v,random((#v)!)));if(isprime(s=sum(x=1,#w,w[x]*10^(#w-x))),print(s);cnt++))
9182515166396028053899494277
5790252548878614912396160939
8065193970459846172863122599
821379790684859221594159663
2498239697461105998682175053
2875349516987619625293009841
9346719526110843569258970289
4214029397039916216865887559
9635892650907162274541988139
7341063961072859499825562819
513549761509632862849982179
7589344367589019966852211029
3114429320666258958905178997
5690190229723199638884574561
4808306291559199227865743169
4052135849669315891722986709
5875249935961716094202881693
7165899439027916658280945213
4402971315966388620295959187
9340551886459861239129076729
time = 181 ms.
gp >

The shorter ones have starting zeroes. Well... I could do one more test...
But you like my string-to-vector-to-random-permutation-to-number functions huh?

edit: how can I replace the sum? I would like a vector-to-string function, or a concat combination, which would not do any calculus, for even more obfuscation, but I don't know such pari function

[LaurV]

Found it! I don't know why I had this fixed idea to apply eval() before shuffling it. The shuffle works perfect for character vectors, to which I can directly apply concat(). (otherwise, the concat() on integer vectors will return the vector itself).

gp > cnt=0; while(cnt<20,w=vecextract(v=Vec("9293392505711486960894715862"),numtoperm(#v,random((#v)!)));if(isprime(s=eval(concat(w))),print(s);cnt++))
5952959880393672096211164487
6965061212239814874935985907
7200418929249837815661659953
2116560389405997673981548229
3409512847521602869957913869
8839514176794286951009295263
9640322651819219357960884759
4261058231699196207954889357
6933576251126798800918925449
1858545261027969938971642093
2854968812303119755667409929
5097678924618962542518319903
7105339812269507952894468691
5102659546293698929031841787
6923988910519227637464815059
4959164579896327018522130689
7868523014995425271099686931
2326894160625038947598711599
9938170966151296594035482827
2956882154260045399116979837
time = 137 ms.
gp >
.

Brilliant huh?
(cheating too, I had to run it 4-5 times to get a lower running time and 20 primes which have no leading zeros, hehe)

[PawnProver44]

Record: Without "cheating" I found 10 primes using the digits of 27357157910631513050079090637098130593099977908 to form 4 primes (including zeros at the front):

2735715379108019050076901605899313059309997737

11590981799677089091703032030700553157376593099

57597106013051937770839101952059090009339679387

90827535715791163151305097963798339900000097097

[danaj]

Nice, LaurV.

For multiperm I just did:

use ntheory ":all"; 'formultiperm { $n=join "",@_; say $n if is_prime($n); } [split //,"9293392505711486960894715862"];

For the shuffling I played with vecextract but then realized I didn't need it.

use ntheory ":all"; use List::Util "shuffle"; my $n; my @s=split //,"9293392505711486960894715862"; for (1..20) { do { $n = join "",shuffle(@s); } while !is_prime($n); say $n; }

Both leave the leading zeros. I could use fromdigits instead of a simple join, which removes the leading zeros, but it currently has a dumb bigint implementation so is noticeably slower. I could also just regex them away, but who cares.

[danaj]

Originally Posted by PawnProver44

Record: Without "cheating" I found [...]

What is "cheating"?

Finding these is not hard with computers. As the percentage of non-acceptable-terminal-digits goes up, we could be a little more clever about the shuffling to speed things up.