La tâche à accomplir est, à partir d’un nombre n, de trouver le plus petit nombre premier qui commence par AU MOINS n du nombre situé 2au début du nombre. C’est une séquence que j’ai trouvée sur OEIS ( A068103 ).

Les 17 premiers chiffres de la séquence sont donnés ci-dessous. Si vous voulez plus, je vais devoir mettre en œuvre la séquence, ce qui ne me dérange pas.

0  = 2
1  = 2
2  = 223
3  = 2221
4  = 22229
5  = 2222203
6  = 22222223                # Notice how 6 and 7 are the same! 
7  = 22222223                # It must be **AT LEAST** 6, but no more than necessary.
8  = 222222227
9  = 22222222223             # Notice how 9 and 10 are the same!
10 = 22222222223             # It must be **AT LEAST** 9, but no more than necessary.
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221

Je pensais qu'il s'agirait d'une combinaison intéressante de manipulation de chaîne, de détection principale et de séquences. C'est le code-golf , le plus petit nombre d'octets sera déclaré gagnant, probablement à la fin du mois.

Brachylog , 12 à 11 octets

:2rj:Acb#p=

Essayez-le en ligne!

Cela se traduit par Brachylog étonnamment directement. Il s’agit d’une fonction et non d’un programme complet (bien que le fait de donner l’interprète Zen argument de ligne de commande l’ajoute le wrapper approprié pour transformer la fonction en programme; c’est ce que j’ai fait pour que le lien TIO fonctionne). Il est également assez regrettable que l' jindice semble avoir une indexation -1 et qu'il soit nécessaire d'y apporter une correction.

Vous pouvez argumenter raisonnablement que ce =n'est pas nécessaire, mais je pense que, compte tenu du libellé du problème, il l'est; sans, la fonction décrivant l'ensemble de tous les nombres premiers qui commencent par le nombre donné de 2s, et sans déclaration explicite selon laquelle le programme devrait faire quelque chose avec cette description (dans ce cas, générer la première valeur), il n'en est probablement pas de même se conformer à la spéc.

Explication

:2rjbAcb#p=
:2rj         2 repeated a number of times equal to the input plus one
    :Ac      with something appended to it
       b     minus the first element
        #p   is prime;
          =  figure out what the resulting values are and return them

Lorsqu'elle est utilisée comme une fonction renvoyant un entier, rien ne demande de valeur après la première, de sorte que la première est tout ce dont nous devons nous préoccuper.

Une subtilité (soulignée dans les commentaires): :Acbet b:Acsont mathématiquement équivalentes (comme on supprime du début et l’autre ajoute à la fin, la région entre les deux ne se chevauchant jamais); J'avais précédemment b:Ac, ce qui est plus naturel, mais il se casse à l'entrée 0 (ce qui, je suppose, est parce qu'il crefuse de concaténer une liste vide, car de nombreuses fonctions intégrées de Brachylog tendent à se rompre pour une raison quelconque). :Acbs'assure qu'il cne faut jamais voir une liste vide, ce qui signifie que la casse de l'entrée 0 peut désormais fonctionner aussi.

Java (OpenJDK 8) , 164 110 octets

a->{int i=0;for(;!(i+"").matches("2{"+a+"}.*")|new String(new char[i]).matches(".?|(..+)\\1+");i++);return i;}

Merci à @FryAmTheEggman pour un tas d'octets!

Essayez-le en ligne!

Pyth, 12 octets

f&!x`T*Q\2P_

En pseudocode:

f                key_of_first_truthy_value( lambda T:
  !                  not (
   x`T*Q\2               repr(T).index(input()*'2')
                     )
 &                   and
          P_T        is_prime(T)
                 )

Boucle le lambdadébut à partir de T=1, incrémentant de 1 jusqu’à ce que la condition soit remplie. La chaîne de 2s doit être une sous-chaîne à partir du début de la chaîne, c'est-à-dire que la méthode d'indexation doit renvoyer 0. Si la sous-chaîne n'est pas trouvée, elle retourne -1ce qui est également une vérité, donc aucun cas exceptionnel n'existe.

Vous pouvez l'essayer en ligne ici , mais le serveur ne permet qu'une entrée de 4.

Perl, 50 octets

49 octets de code + -pdrapeau.

++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{

Fournissez l'entrée sans nouvelle ligne finale. Par exemple:

echo -n 4 | perl -pE '++$\=~/^2{$_}/&&(1x$\)!~/^1?$|^(11+)\1+$/||redo}{'

Cela prend un certain temps pour exécuter un nombre supérieur à 4, car il teste chaque nombre (il y a 2 tests: le premier /^2{$_}/vérifie s'il y en a suffisamment au début, et le second vérifie la (1x$\)!~/^1?$|^(11+)\1+$/primalité (avec de très mauvaises performances)).

Haskell, 73 octets

f n=[x|x<-[2..],all((>0).mod x)[3..x-1],take n(show x)==([1..n]>>"2")]!!0

Exemple d'utilisation: f 3-> 2221.

Force brute. [1..n]>>"2"crée une liste de n 2s qui est comparée aux premiers ncaractères de la représentation sous forme de chaîne du nombre premier actuel.

Mathematica, 103 octets

ReplaceRepeated[0,i_/;!IntegerDigits@i~MatchQ~{2~Repeated~{#},___}||!PrimeQ@i:>i+1,MaxIterations->∞]&

Fonction non nommée prenant un argument entier non négatif #et renvoyant un entier. Il teste littéralement tous les entiers positifs à son tour jusqu'à ce qu'il en trouve un qui commence par #2 et est premier. Horriblement lent pour les entrées supérieures à 5.

résultat précédent: Mathematica, 155 octets

Mathematica serait mieux pour jouer au golf s’il n’était pas typé aussi fort; nous devons explicitement basculer entre les types entier / liste / chaîne.

(d=FromDigits)[2&~Array~#~Join~{1}//.{j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}//.{a__,b_,10,c___}->{a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b})]/. 23->2&

Cet algorithme fonctionne sur des listes de chiffres , étrangement, en commençant par {2,...,2,1}. Tant que ceux-ci ne sont pas les chiffres d'un nombre premier, il ajoute un au dernier chiffre, en utilisant la règle {j___,k_}/;!PrimeQ@d@{j,k}:>({j,k+1}... puis implémente manuellement le report du premier au prochain chiffre aussi longtemps que l'un des les chiffres sont égaux à 10, en utilisant la règle {a__,b_,10,c___}->{a,b+1,0,c}... et ensuite, si nous sommes allés si loin que le dernier des premiers 2s est devenu un 3, recommence avec un autre chiffre à la fin, en utilisant la règle {a,b+1,0,c}/.{a:Repeated[2,#-1],3,b:0..}->{a,2,0,b}. À /. 23->2la fin, on ne résout que le cas particulier où l'entrée est 1: la plupart des nombres premiers ne peuvent pas se terminer 2, ils le 2peuvent. (Quelques erreurs sont crachées sur les entrées 0et 1, mais la fonction trouve son chemin vers la bonne réponse.)

Cet algorithme est assez rapide: par exemple, sur mon ordinateur portable, il faut moins de 3 secondes pour calculer que le premier nombre premier commençant à 1 000 2s est 22...220521.

Pyth, 17 octets

f&q\2{<`T|Q1}TPTh

Je n'arrive pas à résoudre le problème en n = 4ligne, mais c'est correct en théorie.

Explication

               Th    Starting from (input)+1, 
f                    find the first T so that
      <              the first
          Q          (input) characters
         | 1         or 1 character, if (input) == 0
       `T            of T's string representation
     {               with duplicates removed
  q\2                equal "2", 
 &                   and
            }T       T is found in
              PT     the list of T's prime factors.

Perl 6 , 53 octets

{($/=2 x$^n-1)~first {+($/~$_) .is-prime&&/^2/},0..*}

L'essayer

Étendu:

{
  ( $/ = 2 x $^n-1 )       # add n-1 '2's to the front (cache in ｢$/｣)
  ~
  first {
    +( $/ ~ $_ ) .is-prime # find the first that when combined with ｢$/｣ is prime
    &&
    /^2/                   # that starts with a 2 (the rest are in ｢$/｣)
  },
  0..*
}

Gelée , 14 octets

D=2×\S:³aÆPµ1#

Très inefficace. Essayez-le en ligne!

Pyke, 14 octets

.fj`Q\2*.^j_P&

Essayez-le ici!

.fj            - first number (asj)
   `    .^     -   str(i).startswith(V)
    Q\2*       -    input*"2"
             & -  ^ & V
          j_P  -   is_prime(j)

12 octets après la correction de bugs et une nouvelle fonctionnalité

~p#`Q\2*.^)h

Essayez-le ici!

~p           - all the primes
  #       )h - get the first where...
   `    .^   - str(i).startswith(V)
    Q\2*     -  input*"2"

Sage, 69 68 octets

lambda n:(x for x in Primes()if '2'*len(`x`)=>'2'*n==`x`[:n]).next()

Utilise un générateur pour trouver le premier (donc le plus petit) d’infiniment de termes.

Japt, 20 octets

L²o@'2pU +Xs s1)nÃæj

Testez-le en ligne! Il se termine en deux secondes sur ma machine pour toutes les entrées jusqu’à 14, puis perd naturellement de la précision (JavaScript n’a une précision entière que jusqu’à 2 ⁵³ ).

Merci beaucoup à @obarakon pour avoir travaillé dessus :-)

Explication

                       // Implicit: U = input integer, L = 100
L²o                    // Generate the range [0...100²).
   @             Ã     // Map each item X through the following function:
    '2pU               //   Take a string of U "2"s.
         +Xs s1)n      //   Append all but the first digit of X, and cast to a number.
                       // If U = 3, we now have the list [222, 222, ..., 2220, 2221, ..., 222999].
                  æ    // Take the first item that returns a truthy value when:
                   j   //   it is checked for primality.
                       // This returns the first prime in the forementioned list.
                       // Implicit: output result of last expression

Dans la dernière version de Japt, cela peut être 12 octets:

_n j}b!+'2pU   // Implicit: U = input integer
_   }b         // Return the first non-negative bijective base-10 integer that returns
               // a truthy value when run through this function, but first,
      !+       //   prepend to each integer
        '2pU   //   a string of U '2's.
               // Now back to the filter function:
 n j           //   Cast to a number and check for primality.
               // Implicit: output result of last expression

Testez-le en ligne! Il se termine en une demi-seconde sur ma machine pour toutes les entrées jusqu’à 14.

PHP, 76 octets

for($h=str_pad(2,$i=$argv[1],2);$i>1;)for($i=$p=$h.++$n;$p%--$i;);echo$p?:2;

prend en entrée l'argument de la ligne de commande. Courez avec -r.

panne

for($h=str_pad(2,$i=$argv[1],2) # init $h to required head
    ;$i>1;                      # start loop if $p>2; continue while $p is not prime
)
    for($i=$p=$h.++$n               # 1. $p = next number starting with $h
                                    #    (first iteration: $p is even and >2 => no prime)
    ;$p%--$i;);                     # 2. loop until $i<$p and $p%$i==0 ($i=1 for primes)
echo$p?:2;                      # print result; `2` if $p is unset (= loop not started)

Bash (+ coreutils), 53 octets

Fonctionne jusqu'à 2 ^ 63-1 (9223372036854775807) , prend beaucoup de temps pour terminer pour N> 8.

Golfé

seq $[2**63-1]|factor|grep -Pom1 "^2{$1}.*(?=: \S*$)"

Tester

>seq 0 7|xargs -L1 ./twist

2
2
223
2221
22229
2222203
22222223
22222223

Python 3, 406 octets

w=2,3,5,7,11,13,17,19,23,29,31,37,41
def p(n):
 for q in w:
  if n%q<1:return n==q
  if q*q>n:return 1
 m=n-1;s,d=-1,m
 while d%2==0:s,d=s+1,d//2
 for a in w:
  x=pow(a,d,n)
  if x in(1,m):continue
  for _ in range(s):
   x=x*x%n
   if x==1:return 0
   if x==m:break
  else:return 0
 return 1
def f(i):
 if i<2:return 2
 k=1
 while k:
  k*=10;l=int('2'*i)*k
  for n in range(l+1,l+k,2):
   if p(n):return n

code de test

for i in range(31):
    print('{:2} = {}'.format(i, f(i)))

sortie de test

 0 = 2
 1 = 2
 2 = 223
 3 = 2221
 4 = 22229
 5 = 2222203
 6 = 22222223
 7 = 22222223
 8 = 222222227
 9 = 22222222223
10 = 22222222223
11 = 2222222222243
12 = 22222222222201
13 = 22222222222229
14 = 222222222222227
15 = 222222222222222043
16 = 222222222222222221
17 = 222222222222222221
18 = 22222222222222222253
19 = 222222222222222222277
20 = 2222222222222222222239
21 = 22222222222222222222201
22 = 222222222222222222222283
23 = 2222222222222222222222237
24 = 22222222222222222222222219
25 = 222222222222222222222222239
26 = 2222222222222222222222222209
27 = 2222222222222222222222222227
28 = 222222222222222222222222222269
29 = 2222222222222222222222222222201
30 = 222222222222222222222222222222053

J'ai décidé de privilégier la vitesse sur une plage assez large plutôt que sur la taille en octets. :) J'utilise un test de primalité déterministe Miller-Rabin garanti jusqu'à 3317044064679887385961981 avec cet ensemble de témoins. Les nombres premiers les plus grands réussiront toujours le test, mais certains composites peuvent également réussir, même si la probabilité est extrêmement faible. Cependant, j'ai également testé les nombres de sortie pour i> 22 en utilisant pyecm un programme de factorisation de courbe elliptique, et ils semblent être premiers.

Python 3, 132 octets

def f(x):
 k=10;p=2*(k**x//9)
 while x>1:
  for n in range(p*k,p*k+k):
   if all(n%q for q in range(2,n)):return n
  k*=10
 return 2

Tout espoir de performance a été sacrifié pour un nombre d'octets plus petit.

Java, 163 octets

BigInteger f(int a){for(int x=1;x>0;x+=2){BigInteger b=new BigInteger(new String(new char[a]).replace("\0","2")+x);if(b.isProbablePrime(99))return b;}return null;}

code de test

    public static void main(String[] args) {
    for(int i = 2; i < 65; i++)
        System.out.println(i + " " + new Test20170105().f(i));
    }

sortie:

2 223
3 2221
4 22229
5 2222219
6 22222223
7 22222223
8 222222227
9 22222222223
10 22222222223
11 2222222222243
12 22222222222229
13 22222222222229
14 222222222222227
15 222222222222222143
16 222222222222222221
17 222222222222222221
18 22222222222222222253
19 222222222222222222277
20 2222222222222222222239
21 22222222222222222222261
22 222222222222222222222283
23 2222222222222222222222237
24 22222222222222222222222219
25 222222222222222222222222239
26 2222222222222222222222222213
27 2222222222222222222222222227
28 222222222222222222222222222269
29 22222222222222222222222222222133
30 222222222222222222222222222222113
31 222222222222222222222222222222257
32 2222222222222222222222222222222243
33 22222222222222222222222222222222261
34 222222222222222222222222222222222223
35 222222222222222222222222222222222223
36 22222222222222222222222222222222222273
37 222222222222222222222222222222222222241
38 2222222222222222222222222222222222222287
39 22222222222222222222222222222222222222271
40 2222222222222222222222222222222222222222357
41 22222222222222222222222222222222222222222339
42 222222222222222222222222222222222222222222109
43 222222222222222222222222222222222222222222281
44 2222222222222222222222222222222222222222222297
45 22222222222222222222222222222222222222222222273
46 222222222222222222222222222222222222222222222253
47 2222222222222222222222222222222222222222222222219
48 22222222222222222222222222222222222222222222222219
49 2222222222222222222222222222222222222222222222222113
50 2222222222222222222222222222222222222222222222222279
51 22222222222222222222222222222222222222222222222222289
52 2222222222222222222222222222222222222222222222222222449
53 22222222222222222222222222222222222222222222222222222169
54 222222222222222222222222222222222222222222222222222222251
55 222222222222222222222222222222222222222222222222222222251
56 2222222222222222222222222222222222222222222222222222222213
57 222222222222222222222222222222222222222222222222222222222449
58 2222222222222222222222222222222222222222222222222222222222137
59 22222222222222222222222222222222222222222222222222222222222373
60 222222222222222222222222222222222222222222222222222222222222563
61 2222222222222222222222222222222222222222222222222222222222222129
62 2222222222222222222222222222222222222222222222222222222222222227
63 2222222222222222222222222222222222222222222222222222222222222227
64 2222222222222222222222222222222222222222222222222222222222222222203

582,5858 millisecondes

Explication: boucle sur les entiers et les ajoute sous forme de chaînes à la chaîne racine, qui est la chaîne "2" donnée, et vérifie si elle est prime ou non.