Étant donné un nombre N, le défi consiste à obtenir la somme de la pyramide de N nombres premiers. Pour clarifier les choses, voici un exemple:
Input: 4
Nous allons lister les premiers 4
nombres premiers, puis calculer leur somme. Après cela, nous calculerons les sommes des sommes, et ainsi de suite:
2
> 5
3 > 13
> 8 > 33
5 > 20
> 12
7
Vous pouvez voir que le résultat final est 33 . Voici un autre exemple, avec N = 8:
2
> 5
3 > 13
> 8 > 33
5 > 20 > 83
> 12 > 50 > 205
7 > 30 > 122 > 495
> 18 > 72 > 290 > 1169
11 > 42 > 168 > 674
> 24 > 96 > 384
13 > 54 > 216
> 30 > 120
17 > 66
> 36
19
Vous pouvez voir que le résultat final est 1169 .
Voici un autre exemple avec un N impair, N = 3:
2
> 5
3 > 13
> 8
5
Cela nous donne 13 comme résultat
Votre tâche consiste à écrire un programme ou une fonction, qui prend un entier supérieur à 0, et à sortir le résultat final.
Voici quelques résultats de tests:
1: 2
2: 5
3: 13
4: 33
5: 83
6: 205
7: 495
8: 1169
9: 2707
10: 6169
11: 13889
12: 30993
13: 68701
14: 151469
15: 332349
16: 725837
17: 1577751
18: 3413221
19: 7349029
20: 15751187
21: 33616925
22: 71475193
23: 151466705
24: 320072415
25: 674721797
26: 1419327223
27: 2979993519
28: 6245693407
29: 13068049163
30: 27297614797
31: 56929779663
32: 118543624847
33: 246475746269
34: 511766428817
35: 1061264813321
36: 2198298700845
37: 4548996804811
38: 9405003164065
39: 19429190057417
40: 40107799133677
41: 82736199371081
42: 170553108953473
43: 351333736092089
44: 723224546040181
45: 1487710742395387
46: 3058157261678325
47: 6282142186547177
48: 12896743408107403
49: 26460652594917673
50: 54262186256186881
51: 111224391050741687
52: 227896496141836195
53: 466805185374509003
54: 955904519939662217
55: 1956988697590280537
56: 4005572366722212927
57: 8196803221276230093
58: 16769645303734608963
59: 34300013739423719561
60: 70136585692535099353
61: 143371352962891226373
62: 292978031452308375001
63: 598482012866917021541
64: 1222083126601616763473
65: 2494459637841415902073
66: 5089478703050176444803
67: 10379794709536133386939
68: 21160351440305258275579
69: 43119914481530819445497
70: 87833066190052490228187
71: 178841897161848754603319
72: 364014682565128163812791
73: 740654046243174781813209
74: 1506496270380756958474835
75: 3063280375436290387756263
76: 6227039507615221644290617
77: 12655020557561801933128885
78: 25712267089927372837530869
79: 52230425385198423845305957
80: 106076955379202815098486497
81: 215397386589448754140867649
82: 437308717912632286770415395
83: 887706233370396897803709611
84: 1801721089699452657985592689
85: 3656329898231436156162865559
86: 7418972676822310377574227797
87: 15051599987013574096449515927
88: 30532404546282900804722616529
89: 61926565462373271494414919017
90: 125582269494835615524470915169
91: 254631689768733901573206365479
92: 516210444730946464864091626473
93: 1046330617753410129672316234861
94: 2120493010460433691014704829565
95: 4296639990460140795780826898943
96: 8704509990931940668688755806845
97: 17631229933967301681217551193565
98: 35706243541395815998303171050377
99: 72298621492552303967009812018997
Il s'agit de code-golf , donc le plus petit nombre d'octets gagne!
[1169]
pour8
) est-elle acceptable?Réponses:
J, 15 octets
Explication:
Fondamentalement, la même chose que ma réponse Mathematica .
la source
Mathematica,
383635 octetsla source
Minkolang 0,14 , 17 octets
Essayez-le ici et vérifiez tous les cas de test ici .
Explication
J'utilise essentiellement le même algorithme que plusieurs des réponses précédentes qui utilisent des coefficients binomiaux. Chaque fois que vous voyez une telle pyramide de nombres ajoutée, le triangle de Pascal devrait être la première chose à laquelle vous pensez. Je ne vois pas que les autres réponses ont expliqué pourquoi cela fonctionne, alors je vais le faire.
PLUS d'explication
Comme vous pouvez le voir, les nombres premiers
2,3,5,7
apparaissent1,3,3,1
fois dans le résultat final. Laisse-moi changer un peu la disposition.Le nombre de fois où le
3
contribuera au résultat final est le même que le nombre de chemins allant du3
coin supérieur gauche, se déplaçant uniquement vers le haut et vers la gauche . Ici, il existe trois chemins de ce type pour3
:Notez que je peux inverser la direction sans perte de généralité. Je veux donc savoir combien de chemins il y a du coin supérieur gauche à chaque position le long du bord dentelé. Je peux les compter comme ça ...
Pour chaque nombre dans ce triangle, s'il s'agit de X unités à gauche et de Y unités à partir du haut, alors le nombre à cette position est
La façon dont je l'utilise, cependant,
X+Y = N
est constante etX
varie de 0 àN
, ce qui suit une diagonale. Je multiplie chaque coefficient par le nombre premier correspondant, puis j'additionne le tout.Voir l'article Wikipedia sur le triangle de Pascal pour en savoir plus.
la source
JavaScript ES7 107
Abuser de la limite fixe à 27 - comment ennuyeux est en fait de trouver les nombres premiers.
Extrait de test (en utilisant la compréhension du tableau, cela ne fonctionnera que dans Firefox)
la source
Pyth, 18 octets
Essayez-le en ligne: Démonstration
Explication:
la source
s*V.cLtQUQ.f}ZPZQ0
Pyth -
1615 octetsUtilise réduire et
first_n
filtrer.Suite de tests .
la source
Pyth, 16 octets
Très simple en fait:
la source
Haskell, 74 octets
Exemple d'utilisation:
Comment ça marche: calculer à plusieurs reprises les sommes voisines de tous les nombres premiers. Prenez la tête de l'
n
itération.Comme l'opérateur d'index
!!
est basé sur zéro, je préfère une liste vide pour éviter d'avoir à utiliser!!(n-1)
.la source
Matlab, 76 octets
Merci à David d'avoir économisé beaucoup d'octets!
Ancienne version, 98 octets
la source
x
utilisationx=primes(103);
permet d'économiser quelques octets, car il vous suffit de monterN=27
(et peu importe si lex
nombre d'entrées est supérieur à celui dont vous avez besoin).conv
était une excellente idée!JavaScript (ES6), 121 octets
Explication
La plus grande partie de la taille provient de la recherche des nombres premiers.
Tester
Afficher l'extrait de code
la source
Shell + utilitaires GNU et BSD, 92
la source
Sérieusement, 23 octets
Sort le résultat sous forme de liste de longueur 1:
8 -> [1169]
Essayez-le en ligne
Explication:
la source
Mathematica 73 octets
Comment ça marche
Prime@n~Table~{n,#}&
donne une liste des premiers#
nombres premiers.Partition[#,2,1]&
réorganise une liste de nombres,{a, b, c, d ...}
comme{{a,b}, {b,c}, {c,d}...}}
.Plus@@@
revient ensuite{a+b, b+c, c+d...}
.NestWhile
commence par la liste des#
nombres premiers et s'applique à plusieurs reprisesPlus@@@Partition...
tant qu'il y a plus d'un nombre dans la liste.Il faut environ 1/5 seconde pour résoudre les 1000 premiers nombres premiers.
la source
Python 2, 159 octets
la source
print
commande à l'intérieur de la boucle? Vous ne voulez pas imprimer une seule fois, à la fin?Voie lactée 1.4.8 ,
2625 octetsCette réponse n'est pas en concurrence. Certaines opérations ont été créées après la publication de cette question (mais pas nécessairement pour ce défi).
J'ai pu supprimer un octet après avoir lu les commentaires. La sortie est une liste à un seul élément.
Explication
Usage
la source
Ceylan, 169 octets
Ceci définit deux fonctions -
s
calcule la somme pyramidale d'une séquence d'entiers, tandis quep
appelant cela sur la séquence du premiern
nombres premiers.On dirait que la moitié environ de la taille trouve le premier
n
nombres premiers, l'autre moitié calcule la somme des pyramides.Voici une version formatée / commentée:
la source
Gelée , 7 octets
Essayez-le en ligne!
À l'origine, j'ai écrit une réponse Brachylog
1<|~lṗᵐ≠≜{s₂ᶠ+ᵐ}ⁱ~g
, mais quand elle est sortie à 19 octets, j'ai décidé que je devrais probablement essayer une autre langue.Apparemment, le mappage sur un nombre le traite comme une plage de 1 à lui-même inclus, et les entiers sont plus grands que les listes ou autre
''
.la source
APL (NARS), 41 caractères, 82 octets
En entrée si l'on veut utiliser un grand nombre il faut saisir le type nombre_x comme 47x. Il pourrait y avoir quelque chose qui ne va pas: j'écris ici que n nombres premiers sont dans l'ensemble 1..n ^ 2 Test:
la source
Perl 6 , 52 octets
Essayez-le en ligne!
Bloc de code anonyme qui prend un argument et imprime une liste d'un élément contenant le résultat.
la source
Stax , 13 octets
Exécuter et déboguer
la source