A083569: Le plus petit m n'apparaissant pas plus tôt, de sorte que m + n est premier

26

Définissez une séquence indexée comme suit:

  • A083569(1) = 1
  • A083569(n)nest un entier supérieur à 1, est le plus petit entier m n'apparaissant pas plus tôt tel qu'un m+nnombre premier.

Votre tâche consiste à accueillir net à revenir A083569(n).

 n  A083569(n)
 1  1
 2  3
 3  2
 4  7
 5  6
 6  5
 7  4
 8  9
 9  8
10 13
11 12
12 11
13 10
14 15
15 14
16 21
17 20
18 19
19 18
20 17

Plus de tests peuvent être trouvés ici . La séquence originale sur OEIS peut être trouvée ici .

C'est du . La réponse la plus courte en octets l'emporte. Des échappatoires standard s'appliquent.

Leaky Nun
la source
@ Mr.Xcoder "Définissez une séquence indexée comme suit"
Leaky Nun

Réponses:

14

Haskell , 87 86 83 80 74 69 octets

Merci à xnor d'avoir suggéré des changements qui ont sauvé 3 octets!

f n=[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]!!0

Essayez-le en ligne!

Je suis nouveau à Haskell et au golf à Haskell, les commentaires sont appréciés!

Explication

Nous définissons une fonction f n. Nous définissons f ncomme le premier élément !!0de la liste:

[m|m<-[1..],all((>0).mod(n+m))[2..n+m-1],all((/=m).f)[1..n-1]]

En panne, c'est:

[m|          # Numbers m
m<-[1..],    # From the integers greater than 0
all          # Forall x
(>0).mod(n+m)# n+m mod x is not zero
[2..n+m-1]   # from the integers from 2 to n+m-1
all          # Forall
((/=m).f)    # when f is applied the result is not m
[1..n-1]     # from the integers from 1 to n-1
Assistant de blé
la source
3
Bienvenue au golf Haskell! Cela [2,3..]peut juste être [2..], compter par 1 est par défaut. Il y a un intégré notElem.
xnor
@xnor Merci! J'ai fini par trouver un meilleur moyen de l'utiliser, notElemmais le premier conseil a été utile et je m'assurerai de garder le second dans ma poche arrière.
Wheat Wizard
On dirait que votre nouvelle révision se f 1trompe, devrait être 1.
xnor
@xnor Fixe, malheureusement au prix de 3 octets.
Wheat Wizard
6

Gelée , 16 15 octets

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ

Cela suppose A083569 (n) ≤ n² (la séquence semble croître de façon linéaire).

Essayez-le en ligne!

Comment ça marche

Rɓ²R+⁸ÆPTḟḢṭµ/Ṫ  Main link. Argument: n

R                Range; yield [1, ..., n].
 ɓ               Begin a dyadic chain with swapped arguments.
            µ/   Reduce the range by that chain.
                 If we call the chain f, this computes f(2,1), then f(3,f(2,1)),
                 then f(4,f(3,f(2,1)), etc.
                 The left argument is an integer k, the right one an array A.
  ²                Square; yield k².
   R               Range; yield [1, ..., k²].
    +⁸             Add k, yielding [1+k, ..., k²+k].
      ÆP           Test each sum for primality.
        T          Truth; get all indices of 1‘s. This finds all m in [1, ..., k²]
                   such that m+k is prime.
         ḟ         Filterfalse; remove all resulting elements that appear in A.
          Ḣ        Head; extract the first remaining result.
           ṭ       Tack; append the extracted integer to A.
                 This computes the first n elements of the sequence.
              Ṫ  Tail; extract the last, n-th element.
Dennis
la source
4
En effet, A083569(n)est au plus le nth premier plus grand que npar sa définition, qui est tout au plus le 2nth premier, qui (pour n≥3) est inférieur 4n*log(n)aux résultats de Rosser – Schoenfeld.
Greg Martin
Alors que @GregMartin l'a vérifié, c'est toujours une hypothèse assez folle à faire ...
Esolanging Fruit
4
@ Challenger5 Je préfère "deviner instruit".
Dennis
6

Pyth - 18 17 15 octets

Merci à @isaacg de m'avoir sauvé deux octets!

De retour sur ce site, après avoir été occupé pendant un certain temps, nous espérons que celui-ci continuera de jouer au golf.

esmaYf&-TYP_+Th

Essayez-le en ligne ici .

Maltysen
la source
4
Bienvenue à PPCG!
Leaky Nun
@LeakyNun Merci :)
Maltysen
1
-TYest un octet plus court que !/YT, et véridique dans les mêmes cas.
isaacg
Vous pouvez enregistrer un autre octet en changeant +hdTpour +Th.
isaacg
@isaacg, oh jette-t-il le premier élément dans une liste? C'est vraiment cool.
Maltysen
3

C # (.NET Core) , 169 octets

n=>{if(n<2)return 1;var p=new int[n-1];int i=0,j,s;for(;i<n-1;)p[i]=f(++i);for(i=1;;i++){for(j=2,s=i+n;j<s&&s%j++>0;);if(j==s&!System.Array.Exists(p,e=>e==i))return i;}}

Essayez-le en ligne!

De loin la façon la plus inefficace pour calculer les résultats, donc renoncez à calculer f(n)pour n>=30ce code. La première étape consiste à calculer récursivement les valeurs de f(1)à f(n-1), puis à procéder au calcul f(n)en recherchant le premier itel qui n+iest premier et ine figure pas dans la liste de valeurs précédente.

Charlie
la source
3

Assemblage x86-64, 57 55 octets

Je suis nouveau au golf, donc les commentaires / retours sont appréciés.

Remarque: ceci est optimisé pour la longueur du code machine, pas pour la longueur source.

0: 89 f8 ff cf 74 32 97 89 fe 89 f1 ff c6 89 f0 99
1: f7 f1 85 d2 e0 f7 85 c9 75 ed 89 f9 ff c9 56 29
2: fe 56 57 51 89 fc e8 d3 ff ff ff 59 5f 5e 39 c6
3: e0 ef 96 5e 74 d1 c3

Définit une fonction, en utilisant la convention standard (c'est-à-dire la valeur de retour dans eax, le premier argument dans edi, tous les registres sauvegardés par l'appelant sauf ebx) qui prend un entier 32 bits non signé et retourne le plus petit m etc.

La source:

    .globl a083569
    // edi = original, probably don't touch
    // esi = candidate prime, if it's not a repeat we return edi-this
a083569:
    mov %edi, %eax
    dec %edi
    jz end
    xchg %eax, %edi
    mov %edi, %esi
primecheck:
    mov %esi, %ecx
    inc %esi
primeloop:
    mov %esi, %eax
    cdq
    div %ecx
    test %edx, %edx
    loopnz primeloop
/* end */
    // if esi isn't prime, then ecx is now one or greater.
    test %ecx, %ecx
    jnz primecheck
    // esi is now our target prime: check if it's not already one
    mov %edi, %ecx
    dec %ecx
    push %rsi   /* we need a flag-safe way to restore this later */
    sub %edi, %esi
chkdup:
    push %rsi
    push %rdi
    push %rcx
    mov %ecx, %edi
    call a083569
    pop %rcx
    pop %rdi
    pop %rsi
    cmp %eax, %esi
    loopne chkdup
/* end loop - chkdup */
    xchg %esi, %eax
    pop %rsi
    je primecheck
/* end outer loop - primecheck */
end:
    ret

Essayez-le en ligne!

ObsequiousNewt
la source
1

Clojure, 158155 octets

#(loop[r[0 1]i 1](if(= i %)(last r)(recur(conj r(nth(for[j(range):when(=((set r)j)(seq(for[k(range 2(+ 1 i j)):when(=(mod(+ 1 i j)k)0)]j)))]j)0))(inc i))))

Cela pourrait encore avoir un peu de graisse, je ne suis pas très satisfait, (+ 1 i j)mais c'était la façon la plus simple de gérer le cas de base n = 1et le reste. ((set r)j)renvoie nilif jn'est pas dans l'ensemble, et (seq ())sur une liste vide retourne également nil. Calcule n = 1000en 48 secondes.

Mise à jour: supprimée nilde la =vérification car le code fonctionne correctement également sans elle.

NikoNyrh
la source
1

Ruby , 62 + 8 = 70 octets

Utilise le -rprimedrapeau.

f=->n,o=[]{o<<f[n-1,o]if n>1;Prime.find{|i|i>n&&o|[i-n]!=o}-n}

Essayez-le en ligne!

Encre de valeur
la source
1

Python, 194 170 110 octets

84 octets enregistrés par Leaky Nun

2 octets enregistrés par mathmandan

def s(n):
 a=[s(j)for j in range(1,n)];i=1
 while(i in a)|any((i+n)%j<1for j in range(2,i+n)):i+=1
 return i

Définit une fonction s (n) qui prend un nombre en entrée et renvoie A083569 (n).

Essayez-le en ligne

Madison Silver
la source
1
Vous pourriez envisager d'inclure ce lien TIO .
Leaky Nun
1
Vous pouvez utiliser p=lambda n:any(n%i<1for i in range(2,n))pour le contrôle de primalité.
Leaky Nun
1
110 octets
Leaky Nun
1
Vous pouvez utiliser au niveau du bit ou pour enregistrer quelques octets:while(i in a)|any(...
mathmandan