mersenneforum.org Switching digits test
 Register FAQ Search Today's Posts Mark Forums Read

 2016-03-15, 23:14 #1 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts Switching digits test 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.
 2016-03-15, 23:20 #2 VBCurtis     "Curtis" Feb 2005 Riverside, CA 23×32×61 Posts 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?
2016-03-15, 23:30   #3
PawnProver44

"NOT A TROLL"
Mar 2016
California

3058 Posts

Quote:
 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.

Last fiddled with by PawnProver44 on 2016-03-15 at 23:30

 2016-03-15, 23:35 #4 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 38A16 Posts '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. Last fiddled with by danaj on 2016-03-15 at 23:41
 2016-03-15, 23:45 #5 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts 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.
2016-03-16, 00:08   #6
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

23×241 Posts

Here is one special case as a category:
Quote:
 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:

Quote:
 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

Last fiddled with by a1call on 2016-03-16 at 00:11

 2016-03-16, 04:36 #7 LaurV Romulan Interpreter     Jun 2011 Thailand 22·3·739 Posts 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). Code: 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 Last fiddled with by LaurV on 2016-03-16 at 04:46
 2016-03-16, 04:53 #8 LaurV Romulan Interpreter     Jun 2011 Thailand 22A416 Posts 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). Code: 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) Last fiddled with by LaurV on 2016-03-16 at 04:55
 2016-03-16, 05:58 #9 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts 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 Last fiddled with by PawnProver44 on 2016-03-16 at 05:59
 2016-03-16, 06:18 #10 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·3·151 Posts Nice, LaurV. For multiperm I just did: Code: 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. Code: 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. Last fiddled with by danaj on 2016-03-16 at 06:25
2016-03-16, 06:25   #11
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post YuL Factoring 24 2015-06-08 01:26 esqrkim Hardware 9 2010-03-02 20:27 Numbers Hardware 7 2005-09-12 19:10 tha Lone Mersenne Hunters 11 2004-05-17 15:43 sonjohan Software 2 2003-11-01 01:23

All times are UTC. The time now is 10:53.

Sun Oct 25 10:53:02 UTC 2020 up 45 days, 8:04, 0 users, load averages: 1.85, 1.54, 1.52