Considere un número primo p , escrito en la base 10. La memoria de p se define como el número de primos distintos estrictamente menores que p que están contenidos como subcadenas de p .
Reto
Dado un número entero no negativo n como entrada, encuentre el primo más pequeño p tal que p tenga memoria n . Es decir, encuentre el primo más pequeño con exactamente n primos estrictamente distintos como subcadenas.
Entrada
La entrada se puede tomar a través de cualquier formato estándar. Debe admitir la entrada hasta el n más grande de modo que la salida no se desborde. Como referencia, 4294967291 es el primo más grande en 32 bits.
Salida
La salida puede escribirse en STDOUT o devolverse desde una función.
Ejemplos
El número 2 tiene memoria 0 ya que no contiene primos estrictamente menores como subcadenas.
El número 113 es el primo más pequeño con memoria 3. Los números 3, 13 y 11 son las únicas subcadenas primas y ningún primo menor que 113 contiene exactamente 3 primos como subcadenas.
Los primeros 10 términos de la secuencia, que comienzan con n = 0, son
2, 13, 23, 113, 137, 1237, 1733, 1373, 12373, 11317
Nota
Este es A079397 en OEIS.
Tabla de clasificación
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>
Respuestas:
Pyth, 22 bytes
Demostración , prueba de arnés
Explicación:
fuente
P_Y
y enP_T
lugar de}YPY
y en}TPT
ese entonces?CJam,
333130 bytesEste es un programa completo que lee la entrada como un argumento de línea de comandos.
Pruébelo en línea en el intérprete de CJam .
Prueba de funcionamiento
Cómo funciona
fuente
CJam, 40 bytes
Pruébalo en línea
Estoy seguro de que esto es una gran sorpresa, pero de hecho es más largo que la solución que Dennis publicó. Bueno, en realidad no, ya que ni siquiera tenía muchas esperanzas. Pero quería darle una oportunidad de todos modos. Y como está funcionando, me parece bastante razonable, y creo que es lo suficientemente diferente como para ser de algún interés, pensé en publicarlo de todos modos.
La idea básica aquí es que construyo una lista de números primos en un ciclo, agregando el siguiente número primo más grande a la lista en cada paso. Para verificar la terminación, cuento cuántos elementos, además del último elemento de la lista, son una subcadena del último elemento. Si este recuento es igual a la entrada
n
, hemos terminado.Explicación:
fuente
Pyth - 25 bytes
Filtro anidado, interno para calcular la memoria, externo para encontrar primero que requiera memoria.
Test Suite .
fuente
r2T
en lugar detStT
Octava / Matlab, 126 bytes
Pruébalo en línea
fuente
JavaScript ES6, 106 bytes
Aquí hay una versión no golfista con explicación:
Por supuesto, esto se vuelve terriblemente lento bastante rápido. Sin embargo, el OP ha declarado que no hay límite de tiempo.
fuente
a
yi%c
para verificar la calidad. Puede guardar dos bytes cambiando{return i}else{a.push(i)}
areturn i;else a.push(i)
Creo que las funciones anónimas también están permitidas, lo que ahorraría dos bytes más al principio.if...else
lógica envolviéndolo en un bucle for.i++
coni%c
?a
y la siguiente llamada tendría un errori
, por ejemplo, cuando encontramos 10 primos iterará 10 veces para cada iteración del bucle externo.Brachylog (2), 12 bytes, desafío de fechas posteriores al idioma
Pruébalo en línea!
Anteriormente usaba 13 bytes,
ᶠd
pero ahora se le ha dado una abreviaturaᵘ
, reduciéndolo a 12. Como el lenguaje es posterior al desafío de todos modos, y la característica es una que no se agregó para este desafío en particular, también podría úsalo.Como es habitual en Brachylog, esta es una función, no un programa completo.
Explicación
Esto nos da el primo más pequeño con la propiedad que queremos, porque
≜
primero verifica los valores cercanos a 0.fuente
Python 2,
163154 BytesEstoy demasiado cansado para jugar al golf. Espero que cuando me despierte mañana pueda mejorar esto.
fuente
Julia, 86 bytes
Es prácticamente autoexplicativo. Recorra todos los enteros positivos, y cada vez que encuentre un primo, sume una matriz booleana que indique si el conjunto de primos menores que el actual son subcadenas del actual. Si encuentra uno con el número necesario de coincidencias, devuelva ese valor.
El tiempo de ejecución se vuelve lento para n = 11, y probablemente para la mayoría de los valores superiores a 11, específicamente, en mi computadora portátil, n = 11 tarda unos 33 segundos.
fuente
2^63
se evalúa como0
, por defecto JuliaInt32
para literales enteros en el sistema de 32 bits - sic!). El idioma más corto para hacer que la solución funcione en un sistema de 32 bits seríafor i=1:uint(-1)
entonces, pero cuesta 2 bytes más. Sin embargo, es difícil exigir probar soluciones de golf en todas las plataformas, por lo que +1.Haskell,
149147144 bytes(127 bytes sin contar la
import
declaración).El resultado anterior se produjo con la definición más larga
La nueva definición, 3 caracteres más corta, es mucho más lenta, solo pude obtener 5 primeros números en la secuencia antes de perder la paciencia y abortar.
fuente
Haskell ,
119118 bytesPruébalo en línea! Uso:
f 3
rendimientos113
.fuente
PHP, 124 bytes
toma datos del argumento de la línea de comando; correr con
-r
.Descompostura
fuente
Python 2 , 108 bytes
Pruébalo en línea!
fuente