13
\$\begingroup\$

You saved the day with your prime sequence code, and the math teacher loved it. So much so that a new challenge was posed to the librarian (a/k/a, your boss). Congratulations, you get to code the solution so the librarian can once again impress the math teacher.

Start with the sequence of natural numbers in base-10, N

0, 1, 2, 3, 4, 5, 6 ...

Excluding 0 and 1, every number in this sequence either is prime, P

2, 3, 5, 7, 11, 13 ...

or composite, C

4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 ...

Reflecting on how the librarian thought to insert an integer digit into the decimal expansion of a number from P, the math teacher instead created a function G(x,y) that takes a number x from N with 1 <= x <= 9 and a number y from C and inserts x into the decimal expansion of y in every position, in order left-to-right, selecting only unique numbers.

For example, G(3,14) is 314, 134, 143. However, G(1,14) is only 114, 141, as whether you prepend or insert the 1 into 14, the same number 114 is generated.

The math teacher wondered how many times you'd have to do these permutations before you get a number that's in P, if you took x in increasing order. The math teacher called this the Composite-Prime Index of a number, and wrote it as CPI(y).

For example, 4 only needs to be done twice: 14, 41, since 41 is prime, so CPI(4) is 2. However, 8 needs to be done 6 times, 18, 81, 28, 82, 38, 83 before reaching 83 as a prime number, so CPI(8) is 6.

Your task is to write code that will output this Composite-Prime Index, given an input number.

Input

  • A single integer y, such that y is in C, input via function argument, STDIN, or equivalent.
  • For the purposes of calculation, you can assume y will fit in usual integer ranges (e.g., assume 231-1 as an upper bound).
  • Behavior for y not in C is undefined.

Output

The resultant Composite-Prime Index, calculated as described above, output to STDOUT or equivalent, with two exceptions:

  • If the very last permutation (i.e., appending 9 to y) is the one that results in a prime, output -1. An example, expanded below, is y=14.
  • If there is no permutation (i.e., G(x,y) is a subset of C for all 1 <= x <= 9), output 0. An example, expanded below, is y=20.

Examples

 y -> operations             : output
 4 -> 14, 41                 : 2
 6 -> 16, 61                 : 2
 8 -> 18, 81, 28, 82, 38, 83 : 6
 9 -> 19                     : 1
10 -> 110, 101               : 2
12 -> 112, 121, 212, 122, 312, 132, 123, 412, 142, 124, 512, 152, 125, 612, 162, 126, 712, 172, 127 : 19
14 -> 114, 141, 214, 124, 142, 314, 134, 143, 414, 144, 514, 154, 145, 614, 164, 146, 714, 174, 147, 814, 184, 148, 914, 194, 149 : -1
15 -> 115, 151               : 2
16 -> 116, 161, 216, 126, 162, 316, 136, 163 : 8
18 -> 118, 181               : 2
20 -> 120, 210, 201, 220, 202, 320, 230, 203, 420, 240, 204, 520, 250, 205, 620, 260, 206, 720, 270, 207, 820, 280, 208, 920, 290, 209 : 0

Restrictions

  • This is code-golf, since you'll need to transcribe this to an index card so the librarian can show the math teacher, and your hand cramps easily.
  • Standard loophole restrictions apply. The librarian doesn't tolerate cheaters.

Leaderboard

var QUESTION_ID=63191,OVERRIDE_USER=42963;function answersUrl(e){return"http://api.stackexchange.com/2.2/questions/"+QUESTION_ID+"/answers?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+ANSWER_FILTER}function commentUrl(e,s){return"http://api.stackexchange.com/2.2/answers/"+s.join(";")+"/comments?page="+e+"&pagesize=100&order=desc&sort=creation&site=codegolf&filter="+COMMENT_FILTER}function getAnswers(){jQuery.ajax({url:answersUrl(answer_page++),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){answers.push.apply(answers,e.items),answers_hash=[],answer_ids=[],e.items.forEach(function(e){e.comments=[];var s=+e.share_link.match(/\d+/);answer_ids.push(s),answers_hash[s]=e}),e.has_more||(more_answers=!1),comment_page=1,getComments()}})}function getComments(){jQuery.ajax({url:commentUrl(comment_page++,answer_ids),method:"get",dataType:"jsonp",crossDomain:!0,success:function(e){e.items.forEach(function(e){e.owner.user_id===OVERRIDE_USER&&answers_hash[e.post_id].comments.push(e)}),e.has_more?getComments():more_answers?getAnswers():process()}})}function getAuthorName(e){return e.owner.display_name}function process(){var e=[];answers.forEach(function(s){var r=s.body;s.comments.forEach(function(e){OVERRIDE_REG.test(e.body)&&(r="<h1>"+e.body.replace(OVERRIDE_REG,"")+"</h1>")});var a=r.match(SCORE_REG);a&&e.push({user:getAuthorName(s),size:+a[2],language:a[1],link:s.share_link})}),e.sort(function(e,s){var r=e.size,a=s.size;return r-a});var s={},r=1,a=null,n=1;e.forEach(function(e){e.size!=a&&(n=r),a=e.size,++r;var t=jQuery("#answer-template").html();t=t.replace("{{PLACE}}",n+".").replace("{{NAME}}",e.user).replace("{{LANGUAGE}}",e.language).replace("{{SIZE}}",e.size).replace("{{LINK}}",e.link),t=jQuery(t),jQuery("#answers").append(t);var o=e.language;/<a/.test(o)&&(o=jQuery(o).text()),s[o]=s[o]||{lang:e.language,user:e.user,size:e.size,link:e.link}});var t=[];for(var o in s)s.hasOwnProperty(o)&&t.push(s[o]);t.sort(function(e,s){return e.lang>s.lang?1:e.lang<s.lang?-1:0});for(var c=0;c<t.length;++c){var i=jQuery("#language-template").html(),o=t[c];i=i.replace("{{LANGUAGE}}",o.lang).replace("{{NAME}}",o.user).replace("{{SIZE}}",o.size).replace("{{LINK}}",o.link),i=jQuery(i),jQuery("#languages").append(i)}}var ANSWER_FILTER="!t)IWYnsLAZle2tQ3KqrVveCRJfxcRLe",COMMENT_FILTER="!)Q2B_A2kjfAiU78X(md6BoYk",answers=[],answers_hash,answer_ids,answer_page=1,more_answers=!0,comment_page;getAnswers();var SCORE_REG=/<h\d>\s*([^\n,]*[^\s,]),.*?(\d+(?:[.]\d+)?)(?=[^\n\d<>]*(?:<(?:s>[^\n<>]*<\/s>|[^\n<>]+>)[^\n\d<>]*)*<\/h\d>)/,OVERRIDE_REG=/^Override\s*header:\s*/i;
body{text-align:left!important}#answer-list,#language-list{padding:10px;width:290px;float:left}table thead{font-weight:700}table td{padding:5px}
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script> <link rel="stylesheet" type="text/css" href="//cdn.sstatic.net/codegolf/all.css?v=83c949450c8b"> <div id="answer-list"> <h2>Leaderboard</h2> <table class="answer-list"> <thead> <tr><td></td><td>Author</td><td>Language</td><td>Size</td></tr></thead> <tbody id="answers"> </tbody> </table> </div><div id="language-list"> <h2>Winners by Language</h2> <table class="language-list"> <thead> <tr><td>Language</td><td>User</td><td>Score</td></tr></thead> <tbody id="languages"> </tbody> </table> </div><table style="display: none"> <tbody id="answer-template"> <tr><td>{{PLACE}}</td><td>{{NAME}}</td><td>{{LANGUAGE}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table> <table style="display: none"> <tbody id="language-template"> <tr><td>{{LANGUAGE}}</td><td>{{NAME}}</td><td>{{SIZE}}</td><td><a href="{{LINK}}">Link</a></td></tr></tbody> </table>

\$\endgroup\$
  • \$\begingroup\$ For 9, 19 is prime, so shouldn't the output be 1? \$\endgroup\$ – isaacg Nov 7 '15 at 9:10
  • \$\begingroup\$ Wow, cool answer chart! \$\endgroup\$ – cascading-style Dec 17 '16 at 3:41
  • 1
    \$\begingroup\$ @cascading-style If you mean the Leaderboard, that's primarily Martin's handiwork. \$\endgroup\$ – AdmBorkBork Dec 17 '16 at 7:02
1
\$\begingroup\$

Pyth, 35 bytes

&sKm}dPdsm{msj`dcz]khlzS9|%hxK1lK_1

Test suite

\$\endgroup\$
2
\$\begingroup\$

Haskell, 166 161 bytes

p n=mod(product[1..n-1]^2)n>0
q=p.read
n#c=[h++c:t|i<-[0..length n],(h,t)<-[splitAt i n]]
[y]%i|q y= -1|1<2=0
(y:z)%i|q y=i|1<2=z%(i+1)
f n=((n#)=<<['1'..'9'])%1 

Usage examples: f "8" -> 6, f "14"-> -1, f "20"-> 0.

How it works: p is the primality test (stolen from @Mauris' answer in a different challenge). q a wrapper for p to convert types from strings to integer. n # c inserts c at every position in n. % takes a list of numbers and an index i. When the first element of the list is prime, return i, else recure with the tail of the list and i+1. Stop when there's a single element left and return -1 if it's prime and 0 otherwise.

\$\endgroup\$
1
\$\begingroup\$

Minkolang 0.11, 85 bytes

n1(l*$d`)d9[i3G(0c2c$%$r2c*l*2c3c1+*++2gl:d2G)2gx1c2G3gx]r3XS(2M4&I)N.ikI1-4&1~N.1+N.

Try it here.

Explanation (coming soon)

n            Take integer from input (say, n)
1(           Calculate smallest power of 10 greater than n (say, a)
  l*         Multiply by 10
    $d`      Duplicate stack and push n>a
       )     Close while loop (ends when n<=a)
        d    Duplicates a (let's call it b)

9[                                                 For loop that runs 9 times 
  i1+                                              Loop counter + 1 (say, i)
     3G                                            Puts the loop counter in position 3
       (                                           Opens while loop
        0c2c$%                                     Copies n and b and pushes n//b, n%b
              $r                                   Swaps top two elements of stack
                2c*l*                              Copies b and multiplies by 10
                     2c3c*                         Copies b and i and multiplies them
                          ++                       Adds it all together (inserts i)
                            2gl:                   Gets b and divides by 10
                                d2G                Duplicates and puts one copy back
                                   )               Closes while loop (breaks when b=0)
                                    2gx            Gets and dumps b
                                       1c2G        Copies a and puts it in b's place
                                           3gx     Get and dumps i
                                              ]    Close for loop

r       Reverses stack
 3X     Dumps the top three elements (namely, n, a, and b)
   S    Removes duplicates

(                           Opens while loop
 2M                         Pushes 1 if top of stack is prime, 0 otherwise
   4&                       Jump four spaces if prime
     I)N.                   If the loop actually finishes, then all were composite,
                             so output 0 and stop.
         ik                 Pushes loop counter and breaks
           I1-              Pushes length of stack minus 1 (0 if last one was prime)
              4&1~N.        If this is 0, pushes -1, outputs as integer, and stops.
                    1+N.    Adds 1, outputs as integer, and stops.
\$\endgroup\$
1
\$\begingroup\$

Javascript, 324 bytes

y=>(p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0,u=a=>a.filter((c,i)=>a.indexOf(c)==i),g=(x,y)=>u(((x,y,z)=>z.map((c,i)=>z.slice(0,i).join("")+x+z.slice(i).join("")).concat(y+x))(x,y,y.split(''))),h=(x,y)=>g(x,y).concat(x==9?[]:h(++x,y)),i=h(1,y).reduce((r,c,i)=>r?r:p(c,2)?i+1:0,0),console.log(p(y,2)||y<2?'':i==h(1,y).length?-1:i))

If y not in C, then STDOUT output is empty.

Explanation

y=>(
    //Prime Test function
    p=(n,c)=>n%c!=0?c>=n-1?1:p(n,++c):0,

    //Unique function
    u=a=>a.filter((c,i)=>a.indexOf(c)==i),

    //Generates numbers from a couple x and y
    g=(x,y)=>u(((x,y,z)=>z.map((c,i)=>z.slice(0,i).join("")+x+z.slice(i).join("")).concat(y+x))(x,y,y.split(''))),

    //Generates all possible numbers from y using recusion
    h=(x,y)=>g(x,y).concat(x==9?[]:h(++x,y)),

    //Check if any prime in the generated numbers
    i=h(1,y).reduce((r,c,i)=>r?r:p(c,2)?i+1:0,0),

    console.log(
        //Is Y in C ?
        p(y,2)||y<2?
            ''
            :
            // Check if the answer is not the last one
            i==h(1,y).length?-1:i)
    )
\$\endgroup\$
  • \$\begingroup\$ Might be very late on commenting this, but couldn't you save a few bytes by replacing n%c!=0 with n%c; c>=n-1 with c>n-2; and x==9 with x-9? \$\endgroup\$ – Zacharý Nov 26 '16 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.