Rozważmy liczba pierwsza p , napisany w bazie 10. pamięci z P jest zdefiniowana jako liczba różnych bodźców mniejszy od P , które są zawarte w podrzędnymi p .

Wyzwanie

Biorąc pod uwagę nieujemną liczbę całkowitą n jako wejście, znajdź najmniejszą liczbę pierwszą p, tak aby p miała pamięć n . Oznacza to, że znajdź najmniejszą liczbę pierwszą z dokładnie n wyraźnie ściśle liczbami pierwszymi jako podciągami.

Wkład

Dane wejściowe można pobierać w dowolnym standardowym formacie. Musisz obsługiwać dane wejściowe do największej liczby n, tak aby dane wyjściowe nie zostały przepełnione. Dla porównania, 4294967291 jest największą liczbą pierwszą w 32 bitach.

Wydajność

Dane wyjściowe mogą być zapisywane do STDOUT lub zwracane z funkcji.

Przykłady

Liczba 2 ma pamięć 0, ponieważ nie zawiera ściśle mniejszych liczb pierwszych jako podciągów.

Liczba 113 jest najmniejszą liczbą pierwszą z pamięcią 3. Liczby 3, 13 i 11 są jedynymi podstawowymi podciągami i żadna liczba pierwsza mniejsza niż 113 zawiera dokładnie 3 liczby pierwsze jako podciągi.

Pierwszych 10 terminów sekwencji, zaczynających się od n = 0, to

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

Uwaga

To jest A079397 w OEIS.

Tabela liderów

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>

Pyth, 22 bajty

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

Demonstracja , uprząż testowa

Wyjaśnienie:

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.)

CJam, 33 31 30 bajtów

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

Jest to pełny program, który odczytuje dane wejściowe jako argument wiersza poleceń.

Wypróbuj online w interpretatorze CJam .

Testowe uruchomienie

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

Jak to działa

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.

CJam, 40 bajtów

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

Wypróbuj online

Jestem pewien, że jest to wielki szok, ale w rzeczywistości jest dłuższy niż rozwiązanie, które opublikował Dennis. Cóż, niezupełnie, ponieważ sam nie miałem nawet wielkich nadziei. Ale i tak chciałem spróbować. A ponieważ działa, wydaje mi się dość rozsądny i uważam, że jest wystarczająco inny, aby przynajmniej być przedmiotem zainteresowania, pomyślałem, że i tak go opublikuję.

Podstawową ideą jest to, że tworzę listę liczb pierwszych w pętli, dodając kolejną większą liczbę pierwszą do listy na każdym kroku. Aby sprawdzić zakończenie, liczę, ile elementów innych niż ostatni element na liście jest podciągiem ostatniego elementu. Jeśli liczba ta jest równa wartości wejściowej n, jesteśmy skończeni.

Wyjaśnienie:

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.

Pyth - 25 bajtów

Filtr zagnieżdżony, wewnętrzny, aby obliczyć pamięć, zewnętrzny, aby znaleźć najpierw wymaganą pamięć.

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

Pakiet testowy .

Octave / Matlab, 126 bajtów

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

Wypróbuj online

JavaScript ES6, 106 bajtów

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}

Oto wersja bez golfa z wyjaśnieniem:

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;
}

Oczywiście dość szybko robi się to strasznie wolno. Jednak PO stwierdził, że nie ma ograniczenia czasowego.

Brachylog (2), 12 bajtów, wyzwanie dla postdate języka

~{ṗ≜{sṗ}ᵘkl}

Wypróbuj online!

Wcześniej było to 13 bajtów, ᶠdale teraz otrzymano skrót ᵘ, zmniejszając go do 12. Ponieważ język i tak jest postdatowany do wyzwania, a ta funkcja nie została dodana w szczególności do tego wyzwania, równie dobrze mogę Użyj tego.

Jak zwykle w Brachylog, jest to funkcja, a nie pełny program.

Wyjaśnienie

~{ṗ≜{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.

To daje nam najmniejszą liczbę pierwszą z pożądaną właściwością, ponieważ ≜najpierw sprawdza wartości w pobliżu 0.

Python 2, 163 154 bajtów

Jestem zbyt zmęczony, żeby grać w golfa. Mam nadzieję, że kiedy jutro się obudzę, mogę to poprawić.

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

Julia, 86 bajtów

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

Jest to praktycznie oczywiste. Zapętlaj wszystkie dodatnie liczby całkowite i za każdym razem, gdy zostanie znaleziona liczba pierwsza, zsumuj tablicę boolowską wskazującą, czy zbiór liczb pierwszych mniejszy od bieżącej jest podciągiem bieżącej. Jeśli znajdzie taki z wymaganą liczbą dopasowań, zwróć tę wartość.

Czas działania staje się powolny dla n = 11 i prawdopodobnie dla większości wartości wyższych niż 11 - szczególnie, na moim laptopie, n = 11 zajmuje około 33 sekund.

Haskell, 149 147 144 bajtów

(127 bajtów nie wlicza importdeklaracji).

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, 233,13113,137,1237,1733,1373,12373,11317,23719, Przerwany.

Powyższy wynik uzyskano przy dłuższej definicji

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

Nowa, 3 znaki krótsza definicja jest znacznie wolniejsza, mogłem uzyskać tylko 5 pierwszych liczb w sekwencji przed utratą cierpliwości i przerwaniem.

Haskell , 119 118 bajtów

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

Wypróbuj online! Zastosowanie: f 3plony 113.

PHP, 124 bajty

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");}

pobiera dane wejściowe z argumentu wiersza poleceń; biegać z -r.

awaria

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
}

Python 2 , 108 bajtów

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

Wypróbuj online!