34
\$\begingroup\$

Consider a prime number p, written in base 10. The memory of p is defined as the number of distinct primes strictly less than p that are contained as substrings of p.

Challenge

Given a non-negative integer n as input, find the smallest prime p such that p has memory n. That is, find the smallest prime with exactly n distinct strictly lesser primes as substrings.

Input

Input can be taken through any standard format. You must support input up to the largest n such that the output does not overflow. For reference, 4294967291 is the largest prime in 32 bits.

Output

Output may be written to STDOUT or returned from a function.

Examples

The number 2 has memory 0 since it contains no strictly lesser primes as substrings.

The number 113 is the smallest prime with memory 3. The numbers 3, 13, and 11 are the only prime substrings and no prime smaller than 113 contains exactly 3 primes as substrings.

The first 10 terms of the sequence, beginning with n = 0, are

2, 13, 23, 113, 137, 1237, 1733, 1373, 12373, 11317

Note

This is A079397 in OEIS.

Leaderboard

var QUESTION_ID=55406,OVERRIDE_USER=20469;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+)(?=[^\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\$ Is there a limit on the running time? \$\endgroup\$ – Beta Decay Aug 28 '15 at 7:37
  • \$\begingroup\$ @BetaDecay Nope. \$\endgroup\$ – Alex A. Aug 28 '15 at 19:33

13 Answers 13

8
\$\begingroup\$

Pyth, 22 bytes

f&}TPTqQlf}YPY{sMP.:`T

Demonstration, Test Harness

Explanation:

f&}TPTqQlf}YPY{sMP.:`T
                          Implicit: Q = eval(input())
f                         Starting at T=1 and counting up, return the first T where
                    `T    repr(T)
                  .:      all substrings
                 P        except T itself
               sM         converted to integers
              {           unique examples only
         f                filter on
          }YPY            Y is in the prime factorization of Y, e.g. Y is prime.
      qQl                 Q == len of the above, that is, T has memory Q,
 &}TPT                    and T is prime, (is in its prime factorization.)
\$\endgroup\$
  • \$\begingroup\$ Couldn't have you used P_Y and P_T instead of }YPY and }TPT back then? \$\endgroup\$ – Erik the Outgolfer Jun 11 '17 at 9:08
7
\$\begingroup\$

CJam, 33 31 30 bytes

1{)__mp*{_mp2$s@s#)*},,easi^}g

This is a full program that reads the input as a command-line argument.

Try it online in the CJam interpreter.

Test run

$ time cjam <(echo '1{)__mp*,{_mp2$s@s#)*},,easi^}g') 9
11317
real    0m3.562s
user    0m4.065s
sys     0m0.177s

How it works

1       e# Push I := 1 on the stack.
{       e# Do:
  )__   e#   Increment I and push two copies.
  mp*   e#   Check the last copy for primality and multiply with the first copy.
        e#   This pushes R := I if I is prime and R := 0 if it is composite.
  {     e#   Filter; for each J in [0 ... R-1]:
    _mp e#     Push a copy of J and check for primality.
    2$s e#     Push a copy of I and cast to string.
    @s  e#     Rotate the original J on top of the stack and cast to string.
    #   e#     Find the index (-1 if not found) of the latter in the former.
    )*  e#     Increment the index and multiply it with the result from `mp'.
        e#     This yields 0 iff J is composite or not a subtring of I.
  },    e#   Keep J if the product is non-zero.
  ,     e#   Push the length of the filtered range.
  easi  e#   Cast the array of command-line arguments to string, then to integer.
  ^     e#   XOR it with the length of the filtered range.
}g      e# Repeat while theresult is non-zero.
\$\endgroup\$
6
\$\begingroup\$

CJam, 40 bytes

li2sa{_)\{1$\#)},,3$-}{i{)_mp!}gsa+}w]W=

Try it online

I'm sure this comes as a big shocker, but it is in fact longer than the solution Dennis posted. Well, not really, since I didn't even have very high hopes myself. But I wanted to give it a shot anyway. And since it's working, looks pretty reasonable to me, and I believe it is sufficiently different to at least be of some interest, I thought I'd post it anyway.

The basic idea here is that I build a list of prime numbers in a loop, adding the next larger prime number to the list in each step. To check for termination, I count how many elements other than the last element in the list are a substring of the last element. If this count is equal to the input n, we're done.

Explanation:

li    Get input and convert to integer.
2sa   Seed list of primes with ["2"]. The primes are stored as strings to make
      the later substring search more streamlined.
{     Start of while loop condition.
  _   Copy list of primes.
  )     Pop off last prime from list.
  \     Swap remaining list to top.
  {     Start of filter block for substring matches with all smaller primes.
    1$    Copy test prime to top.
    \     Swap the smaller prime to top to get correct order for substring search.
    #     Search.
    )     Increment to get truthy value (Search returns -1 if not found).
  },    End of filter. We have a list of smaller primes that are substrings now.
  ,     Count list entries.
  3$    Copy input n to top.
  -     Subtract the two for comparison. If they are different, continue loop.
}     End of while loop condition.
{     Start of while loop body. We need to generate the next prime.
  i     The largest prime so far is still on the stack, but as string.
        Convert it to integer.
  {     Start of loop for prime candidates.
    )     Increment current candidate value.
    _mp   Check if it is prime.
    !     Negate, loop needs to continue if it is not a prime.
  }g    End loop for prime candidates. On exit, next prime is found.
  sa+   Convert it to string, and add it to list of primes.
}w    End of while loop body.
]W=   Solution is at top of stack. Discard other stack entries.
\$\endgroup\$
4
\$\begingroup\$

Pyth - 25 bytes

Nested filter, inner to calculate memory, outer to find first that has required memory.

f&!tPTqlf&!tPY}`Y`TtStTQ2

Test Suite.

\$\endgroup\$
  • \$\begingroup\$ r2T instead of tStT \$\endgroup\$ – Jakube Aug 28 '15 at 20:06
2
\$\begingroup\$

Octave / Matlab, 126 bytes

function p=f(n)
p=1;t=1;while t
p=p+1;t=~isprime(p)|sum(arrayfun(@(x)any(strfind(num2str(p),num2str(x))),primes(p)))~=n+1;end

Try it online

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

JavaScript ES6, 106 bytes

n=>{for(a=[],i=2;a.filter(c=>(''+i).search(c)+1).length-n-1;a.push(i))while(!a.every(c=>i%c))i++;return i}

Here is an ungolfed version with explanation:

n=>{
  /**
   * a = list of primes
   * i = current integer
   * Iterate until number of members in a that are substring of i == n-1
   * After each iteration push the current value of i onto a
   */
  for(a=[],i=2; a.filter(c=>(''+i).search(c)+1).length-n-1; a.push(i)) {
    // Iterate until no member of a exactly divides i and increment i per iteration
    while(!a.every(c=>i%c)) i++;
  }
  return i;
}

Of course this gets horrendously slow rather quickly. However the OP has stated there is no limit on time.

\$\endgroup\$
  • \$\begingroup\$ Nice solution, ingenious use of a and i%c to check for prime-ness. You could save two bytes by changing {return i}else{a.push(i)} to return i;else a.push(i) I believe anonymous functions are allowed as well, which would save two more bytes at the beginning. \$\endgroup\$ – ETHproductions Aug 29 '15 at 3:32
  • \$\begingroup\$ @ETHproductions Thanks didn't think of that. Although I've managed to shave off 7 bytes and remove all if...else logic by wrapping it in a for loop. \$\endgroup\$ – George Reith Aug 29 '15 at 14:49
  • \$\begingroup\$ Wow, that's smart! What if you combined the i++ with i%c? \$\endgroup\$ – ETHproductions Aug 29 '15 at 15:47
  • \$\begingroup\$ @ETHproductions Wouldn't work because that would iterate for every value of a and the next call would have the wrong i e.g., when we have found 10 primes it would iterate 10 times for each outer loop iteration. \$\endgroup\$ – George Reith Aug 29 '15 at 15:49
  • \$\begingroup\$ @ETHproductions Ah yes I originally wanted to use recursion but it would have reached the stack limit before hitting the OP's minimum requirements. Now its refactored like this it should be possible... on it... \$\endgroup\$ – George Reith Aug 29 '15 at 15:59
2
\$\begingroup\$

Brachylog (2), 12 bytes, language postdates challenge

~{ṗ≜{sṗ}ᵘkl}

Try it online!

This was previously 13 bytes, using ᶠd, but that's now been given an abbreviation , cutting it down to 12. As the language postdates the challenge anyway, and the feature is one that wasn't added for this challenge in particular, I may as well use it.

As is usual in Brachylog, this is a function, not a full program.

Explanation

~{ṗ≜{sṗ}ᵘkl}
~{         }  Find a value for which the following is true:
  ṗ             The value is prime;
   ≜            (evaluation strategy hint; avoids an infinite loop)
    {  }ᵘ       The set of unique
     sṗ         substrings which are prime
          l     has a length equal to {the input}
         k      when one element is removed.

This gives us the smallest prime with the property we want, because checks values near 0 first.

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

Python 2, 163 154 Bytes

I'm too tired to be golfing.. Hopefully when I wake up tomorrow I can improve this.

p=lambda n:all(n%x for x in range(2,n))
g=input()
s=2
while not(p(s)and len([l for l in[str(x)for x in range(2,s)if p(x)]if l in str(s)])==g):s+=1
print s
\$\endgroup\$
1
\$\begingroup\$

Julia, 86 bytes

n->for i=1:~0>>>1 isprime(i)&&sum(j->contains("$i","$j"),primes(i-1))==n&&return i;end

It's practically self-explanatory. Loop over all positive integers, and each time a prime is found, sum a boolean array indicating whether the set of primes less than the current one are substrings of the current one. If it finds one with the necessary number of matches, return that value.

Running time becomes sluggish for n=11, and likely for most values higher than 11 - specifically, on my laptop, n=11 takes about 33 seconds.

\$\endgroup\$
  • \$\begingroup\$ Clean and elegant solution, even though it only works on 64-bit system (blame Julia type system for that - on 32-bit platform 2^63 evaluates to 0, as Julia defaults Int32 for integer literals on 32-bit system - sic!). The shortest idiom to make the solution work on 32-bit system would be for i=1:uint(-1) then, but it costs 2 bytes more. However, it's hard to require testing golfed solutions on all platforms, so +1. \$\endgroup\$ – pawel.boczarski Aug 28 '15 at 20:36
  • \$\begingroup\$ @pawel.boczarski - I can fix it, using bit-shifting. Have a look... \$\endgroup\$ – Glen O Aug 29 '15 at 4:53
  • \$\begingroup\$ I also removed the "map", because it's redundant inside sum, as sum can take a function that is applied to each term before summing. \$\endgroup\$ – Glen O Aug 29 '15 at 8:01
0
\$\begingroup\$

Haskell, 149 147 144 bytes

(127 bytes not counting the import declaration).

import Data.List
i x=x`elem`nubBy(((>1).).gcd)[2..x]
f n=[p|p<-[2..],i p,n==length(nub[x|x<-[read b|a<-tails$show p,b<-tail$inits a],i x])-1]!!0

Prelude Data.List> map f [0..20]
[2,13,23,113,137,1237,1733,1373,12373,11317,23719,Interrupted.

The above output was produced with the longer definition

i x=and$[x>1]++[rem x n>0|n<-[2..x-1]]

The new, 3 chars shorter, definition is much slower, I could only get 5 first numbers in the sequence before loosing patience and aborting.

\$\endgroup\$
0
\$\begingroup\$

Haskell, 119 118 bytes

p x=all((>0).mod x)[2..x-1]
f n=[y|y<-[2..],p y,n==sum[1|x<-[2..y-1],p x,elem(show x)$words=<<(mapM(:" ")$show y)]]!!0

Try it online! Usage: f 3 yields 113.

\$\endgroup\$
0
\$\begingroup\$

PHP, 124 bytes

for($p=1;;){for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);$m[]=$p;foreach($m as$q)$c+=!!strstr($p,"$q");$c-1-$argv[1]?:die("$p");}

takes input from command line argument; run with -r.

breakdown

for($p=1;;)
{
    for($i=$c=0;$i-1;)for($i=++$p;$p%--$i;);    // find prime $p
    $m[]=$p;                                    // remember that prime
    foreach($m as$q)$c+=!!strstr($p,"$q");      // count memory primes
    $c-1-$argv[1]?:die("$p");                   // if memory==N, exit
}
\$\endgroup\$
0
\$\begingroup\$

Python 2, 108 bytes

f=lambda n,x=2:n-sum(all(j%k for j in(i,x)for k in range(2,j))for i in range(2,x)if`i`in`x`)and f(n,x+1)or x

Try it online!

\$\endgroup\$

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.