mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2016-03-15, 23:14   #1
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post 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.
PawnProver44 is offline   Reply With Quote
Old 2016-03-15, 23:20   #2
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

22·1,091 Posts
Default

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?
VBCurtis is online now   Reply With Quote
Old 2016-03-15, 23:30   #3
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

Quote:
Originally Posted by VBCurtis View Post
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
PawnProver44 is offline   Reply With Quote
Old 2016-03-15, 23:35   #4
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

'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
danaj is offline   Reply With Quote
Old 2016-03-15, 23:45   #5
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

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.
PawnProver44 is offline   Reply With Quote
Old 2016-03-16, 00:08   #6
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

19·101 Posts
Default

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
a1call is offline   Reply With Quote
Old 2016-03-16, 04:36   #7
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

211728 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-03-16, 04:53   #8
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

2×3×1,471 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2016-03-16, 05:58   #9
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

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
PawnProver44 is offline   Reply With Quote
Old 2016-03-16, 06:18   #10
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default

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
danaj is offline   Reply With Quote
Old 2016-03-16, 06:25   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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.
danaj is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
SNFS(27x) How much ECM before switching to NFS? YuL Factoring 24 2015-06-08 01:26
Switching computers esqrkim Hardware 9 2010-03-02 20:27
Switching Boxes Numbers Hardware 7 2005-09-12 19:10
switching to doublechecking tha Lone Mersenne Hunters 11 2004-05-17 15:43
switching PC's for same exponent sonjohan Software 2 2003-11-01 01:23

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

Tue Oct 20 07:10:10 UTC 2020 up 40 days, 4:21, 0 users, load averages: 1.65, 1.66, 1.61

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.