La séquence de nombres segmentés ou nombres premiers de mesure ( OEIS A002048 ) est la séquence de nombres telle que chaque membre est le plus petit nombre positif (supérieur à zéro) qui ne peut pas être composé d'une somme de nombres consécutifs antérieurs, avec a(0) = 1.

Exemple

Pour calculer, a(7)nous calculons d'abord a(0->6) = [1, 2, 4, 5, 8, 10, 14]. nous partons ensuite de zéro et parcourons les nombres jusqu'à ce que nous trouvions celui qui n'est pas la somme d'un ou plusieurs nombres consécutifs dans la séquence.

1  = 1
2  = 2
3  = 1 + 2
4  = 4
5  = 5
6  = 2 + 4
7  = 1 + 2 + 4
8  = 8
9  = 4 + 5
10 = 10
11 = 2 + 4 + 5
12 = 1 + 2 + 4 + 5
13 = 5 + 8
14 = 14
15 = ????

Puisque quinze ne peut pas être fait en additionnant une sous-séquence consécutive et chaque nombre plus petit peut être quinze est le nombre suivant dans la séquence. a(7) = 15

Tâche

Votre tâche consiste à prendre un nombre (via les méthodes standard) et à sortir le nième terme dans cette séquence (via les méthodes de sortie standard). C'est du golf de code et vous serez noté comme tel.

Cas de test

0 -> 1
1 -> 2
2 -> 4
3 -> 5
4 -> 8
5 -> 10
6 -> 14
7 -> 15
8 -> 16
9 -> 21

Haskell, 62 58 octets

-4 octets grâce à @xnor!

(x:y)#z=x:filter(`notElem`scanl(+)x z)y#(x:z)
([1..]#[]!!)

La séquence est indexée sur 0.

Perl, 50 49 octets

Comprend +1 pour -p

Exécuter avec entrée sur STDIN:

segmented.pl <<< 7

segmented.pl:

#!/usr/bin/perl -p
${$_-=$\}++for@F;1while${-++$\};++$#F<$_&&redo}{

Explication

@Fcontient la liste des sommes (négatives) de nombres consécutifs qui se terminent par le dernier nombre actuel. Lorsqu'un nouveau nombre est découvert, la liste est étendue avec 0, puis toutes les valeurs sont diminuées par le nouveau nombre maintenant l'invariant.

Global %::est utilisé comme un hachage mappant tous les nombres (négatifs) qui ont été vus (à travers @F) à une valeur non nulle.

$\est le nombre actuel et est augmenté jusqu'à ce qu'il atteigne une valeur qui n'est pas encore entrée %::.

En faisant un peu attention à l'ordre dans lequel tout se passe, aucune initialisation n'est nécessaire, 1deviendra automatiquement le premier numéro.

Puisque la taille de @Fest le nombre de nombres générés, elle peut être utilisée comme condition d'arrêt

05AB1E , 17 16 octets

Xˆ$µ>D¯ŒOså_i¼Dˆ

Explication

Xˆ                # initialize global array to [1]
  $               # push 1 and input to stack
   µ              # while counter != input
    >             # increase variable on stack
      ¯ŒO         # list of all sums of consecutive number in global array
     D   så_i     # if current stack value is not in the list
             ¼    # increase counter
              Dˆ  # add current stack value to global array

Essayez-le en ligne!

1 octet enregistré grâce à Adnan

Gelée , 14 13 11 octets

Ḷ߀Ẇ;ḅ1‘ḟ$Ṃ

Essayez-le en ligne!

Comment ça fonctionne

Ḷ߀Ẇ;ḅ1‘ḟ$Ṃ  Main link. Argument: n

Ḷ            Unlength; yield [0, ..., n - 1].
 ߀          Recursively map the main link over the range.
   Ẇ         Window; yield all subarrays of consecutive elements of the result.
    ;        Append n to the array of subarrays.
     ḅ1      Convert all subarrays from base 1 to integer.
             This is equivalent to S€ (sum each), but it allows ; to hook.
         $   Combine the previous two links into a monadic chain.
       ‘       Increment all sums.
        ḟ      Filter; remove the original sums from the incremented ones.
          Ṃ  Compute the minimum.

Pyth - 19 17 octets

Merde par un qui ruine tous mes implicits. (Octets même chef d' accusation, literaly incrémenter Q: =hQesmaYf!}TsM.:Y)

esmaYf!}TsM.:Y)1h

Suite de tests .

Javascript, 125 112 110 octets

Sauvegardé 2 octets grâce à @Neil

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)a.some(b=>b.includes(i))||(a[z+1]=[0,...a[z++]||[]].map(v=>i+v));alert(i-1)}

Réponses précédentes

112 octets grâce à @Neil:

f=n=>{a=[[]];for(i=1,z=0;z<=n;i++)if(!a.some(b=>b.includes(i))){a[z+1]=[0,...a[z++]||[]].map(v=>i+v)}alert(i-1)}

125 octets:

f=n=>{a=[[]];for(i=1,k=z=0;z<=n;i++)if(a.every(b=>b.every(c=>c-i))){a[i]=[i].concat((a[k]||[]).map(v=>i+v));k=i,z++}alert(k)}

Python, 113 105 92 80 octets

s=F={1}
x=1
exec"while{x}<=s:x+=1\nF={x+j for j in{0}|F};s|=F\n"*input()
print x

Les derniers octets que j'ai enregistrés ont été inspirés par la réponse Perl de Ton: mon Ffait la même chose que la sienne @F; mon sfait essentiellement la même chose que la sienne %::.

JavaScript (ES6), 77 octets

(n,a=[],s=a,i=1)=>s[i]?f(n,a,s,i+1):--n?f(n,[0,...a].map(j=>s[j+=i]=j),s,i):i

Fondamentalement, un port récursif de l'algorithme de la réponse Perl de @ TonHospel.