Enigme Nombres premiers d'addition @ Prise2Tete

nodgim · #1

Bonjour à tous.
Quel est le 1000 ème nombre premier d'addition (pa) ?

Le kième pa est défini ainsi : c'est le plus petit entier tel que n'importe quelle somme de pak avec un pa plus petit est différente de toute somme entre 2 pa différents inférieurs à pak.

Démarrage de la suite des pa :
0
1 somme: 1
2 sommes: 2,3
4 sommes: 4,5,6
7 sommes: 7,8,9,11
....

Bonne recherche

NB:
Je n'ai pas la solution. Il me parait difficile d'imaginer de trouver la réponse sans secours de l'informatique....

Sydre · #2

C'est pas plutôt 1, 2, 3, 5, 8, 13, 21, ... ? Il me semble que 3+2=4+1=5

enigmatus · #3

Bonjour,
Sauf erreur, je trouve que si 0 est le premier pa, le 1000 ème est 13951622.

Résultat fourni en 133 secondes par un script en python.

nodgim · #4

Sydre, il ne s'agit pas de la suite de Fibonacci.

Enigmatus: peut être... Serait il possible d'avoir toutes les valeurs ?
Si ton résultat est correct (on va attendre d'autres réponses, car je m'atttendais à un nombre plus grand), alors ça dépasse mes espérances. J'expliquerai à la fin de quoi il s'agit vraiment.

enigmatus · #5

nodgim #4 a écrit:
Enigmatus: peut être... Serait il possible d'avoir toutes les valeurs ?

C'est un peu volumineux, mais voici le programme nombres.py qui les génère

Code:

import sys

N=int(sys.argv[1])
pak=set()
som=set()

def ok(n):
   global som
   for n0 in pak:
      m=n+n0
      if m in som: return False
   for s in pak: som.add(s+n)
   return True

k=n=0
while True:
   if ok(n):
      k+=1
      print("k= %4d n= %8d"%(k,n))
      pak.add(n)
   n+=1
   if k>=N: break

À lancer ainsi (du moins sous linux) :

Code:

python nombres.py 1000

Sydre · #6

J'ai du mal comprendre ta définition alors

Pour moi [latex]PA_k[/latex] est le plus petit entier tel que [latex]\forall (i, j, l) \in [|0, k-1|]^3, j\neq l, PA_k + PA_i \neq PA_j + PA_l[/latex]

Or dans les premiers termes que tu donnes on trouve [latex]PA_4 + PA_1 = 4+1 = 5 = 3+2 = PA_3 + PA_2[/latex]

Ce qui va clairement à l'encontre de la définition !

nodgim · #7

Sydre: les 4 premiers d'addition sont 0,1,2,4. Les valeurs supplémentaires sont les sommes.

Enigmatus:
Je ne sais pas faire tourner un programme sous Linux (eh oui, l'informatique et moi...)
Si tu pouvais extraire les 50 premiers et 10 derniers nombres par exemple, ce serait suffisant.

enigmatus · #8

Allez, soyons généreux…

Code:

        0        1        2        4        7       12       20       29       38       52
       73       94      127      151      181      211      257      315      373      412
      475      530      545      607      716      797      861      964     1059     1160
     1306     1385     1434     1555     1721     1833     1933     2057     2260     2496
     2698     2873     3060     3196     3331     3628     3711     3867     4139     4446
     4639     5021     5064     5322     5613     6003     6273     6493     6641     6979
     7275     7587     8017     8373     9071     9167     9760    10105    10489    11109
    11374    11516    12101    12330    12867    13426    13923    14535    14911    15469
    15904    16136    16900    17041    17822    19421    19933    20288    20996    21491
    22065    22612    22659    23724    24399    24969    25360    26071    26680    27601
    28018    28497    29557    30222    31877    32551    33118    33743    34342    34626
    36925    37747    38267    39267    39998    41082    42198    42436    43343    44252
    45424    46326    46848    47929    48621    49391    49851    53108    53384    54429
    54826    55239    56868    57974    60071    60533    62213    63834    64925    65191
    66550    67208    69645    72310    72927    73341    73541    76061    76304    76720
    80903    82444    84693    85235    86732    87710    87954    90773    91335    91971
    96507    97257    98177    99692   100484   103600   104325   106376   107898   108650
   111409   114068   114692   117535   120122   120767   121799   125410   127534   128834
   129926   133512   135690   138508   140895   141811   143211   148193   150031   151925
   153922   155672   158289   160057   160355   164124   166684   169794   171812   172531
   174766   175535   177386   180355   182564   184101   187953   191380   193770   195582
   197919   198724   199408   206087   207402   208734   214116   215573   219885   222952
   224713   225951   228405   230719   235655   237285   239222   242190   246343   249693
   252765   254612   256308   261142   266529   267372   272133   276039   277624   280877
   283129   289011   290295   293067   302169   305551   305802   308411   317253   319429
   324075   325350   329885   331230   333135   333836   337958   342897   344461   351293
   352268   353052   359151   364874   374184   376136   381501   384349   386972   388380
   391471   392439   400923   401552   405567   405849   411083   418502   422760   423833
   427695   429114   440298   440587   447682   455482   459422   463998   470054   471939
   472866   479480   483217   485436   489994   501610   507580   508872   518694   523449
   524678   528366   535017   537119   541418   549499   554394   555903   562779   563647
   567781   579841   584336   594235   598603   602275   608153   609464   611952   612242
   613442   629074   630204   634888   636332   639856   648334   656353   663706   672318
   673886   678839   684361   684601   692072   702243   707027   718768   721738   729589
   740183   742338   747499   750449   758741   760508   768802   774584   776149   787160
   797898   804125   806584   817194   818614   825332   827602   833162   840370   845719
   862033   865938   875230   878669   888718   890617   902070   906343   910215   910843
   919853   929516   939825   946901   948699   963686   964533   975326   980776   982328
   985869   990509   991532   993088  1000796  1036723  1046038  1051255  1054627  1057036
  1058542  1066560  1067301  1085442  1090684  1100045  1109938  1117713  1125551  1127047
  1142150  1153087  1160931  1171258  1177757  1180749  1184065  1194816  1211959  1216209
  1218029  1223580  1244015  1248223  1252320  1269264  1276613  1279255  1301869  1310171
  1318685  1324971  1328866  1338932  1344801  1346631  1356107  1369333  1370197  1370256
  1382666  1398028  1405380  1412686  1423891  1434922  1441552  1444128  1446783  1460452
  1466228  1470297  1487302  1491881  1502457  1522778  1533531  1535815  1555065  1566426
  1582487  1586273  1588260  1613264  1615370  1622568  1625549  1629793  1633916  1651920
  1684782  1688270  1690132  1698000  1704193  1710088  1716081  1721654  1745050  1748726
  1749132  1755480  1784439  1789544  1797528  1803147  1808508  1836595  1843411  1865293
  1879181  1881227  1882876  1899548  1921113  1934508  1946585  1953389  1955054  1972112
  1983519  1995289  2014876  2022543  2023681  2040388  2045104  2048130  2064244  2095085
  2101385  2105500  2112651  2126804  2143878  2157540  2165221  2168023  2177438  2180121
  2200362  2211294  2214962  2220503  2261850  2268115  2269626  2279532  2286003  2305416
  2310092  2318655  2323896  2347059  2349530  2352318  2368465  2372822  2377096  2407120
  2432086  2443959  2448514  2451301  2466728  2507296  2521278  2522534  2529232  2550557
  2554581  2570670  2574186  2604930  2610089  2623331  2624120  2678698  2686189  2690106
  2698395  2721725  2739060  2742232  2753394  2757592  2762967  2785009  2793924  2818703
  2824035  2845761  2855130  2864493  2885976  2887149  2910421  2921333  2938440  2945904
  2964728  2989736  2997651  2998916  3014908  3017647  3051425  3074564  3098970  3101427
  3113980  3127674  3131203  3145772  3150508  3169162  3171702  3197080  3209370  3222467
  3244639  3256225  3293282  3295734  3302647  3341558  3355364  3359616  3363630  3376222
  3398597  3410229  3419110  3432253  3448499  3481777  3509776  3538842  3552493  3557445
  3587885  3601039  3628591  3642351  3646587  3651618  3659674  3670378  3696616  3698256
  3742411  3747344  3770683  3804390  3806665  3838188  3857803  3864213  3872959  3895323
  3899658  3933468  3969044  3981279  3992967  4002661  4021115  4050531  4054557  4059780
  4083605  4106375  4113360  4131878  4136525  4139401  4145947  4180537  4187882  4211415
  4252315  4256027  4268043  4277910  4300825  4336894  4340335  4407276  4414258  4450739
  4484471  4501412  4504154  4522730  4536263  4546710  4578541  4604845  4615042  4622273
  4633124  4641030  4648630  4668026  4674720  4704885  4745891  4788174  4805119  4809329
  4826818  4830889  4861662  4897554  4912228  4914121  4917273  4930941  4950594  4989274
  5028713  5063835  5092750  5100810  5138598  5146212  5169489  5176656  5182289  5185510
  5191696  5192061  5208143  5220329  5242022  5308765  5344582  5355962  5360452  5371063
  5409045  5453993  5489250  5499581  5510250  5526975  5545218  5582611  5584751  5598750
  5605488  5610180  5619885  5679963  5701902  5765712  5806748  5822374  5852741  5864530
  5867046  5881798  5909663  5915321  5930458  5994504  6001896  6026262  6038487  6053748
  6092889  6104366  6112609  6134218  6183175  6190544  6191595  6197712  6217747  6225861
  6346384  6362790  6377955  6409358  6443735  6480984  6486269  6516643  6534320  6545481
  6562294  6583840  6614393  6648749  6675193  6681290  6691444  6743452  6766743  6819105
  6823578  6865807  6880431  6899149  6923707  6942243  6964345  7001148  7014530  7031996
  7044762  7046459  7107335  7124224  7148280  7179250  7257373  7263359  7294864  7309784
  7372937  7387910  7398845  7411142  7420083  7436721  7463667  7473302  7479209  7507361
  7510944  7536617  7585108  7585551  7620998  7625795  7682002  7694416  7779304  7815208
  7856689  7874700  7896514  7962900  7997387  8005949  8010600  8032104  8070882  8114086
  8122021  8128586  8138970  8178553  8217763  8223531  8295379  8341493  8349393  8370500
  8403355  8413339  8464355  8535076  8573069  8588685  8610016  8612551  8641913  8666288
  8691731  8715748  8740335  8814085  8840089  8851958  8864092  8872575  8913784  8960660
  8966738  8974680  9021171  9061321  9105434  9123927  9130531  9131860  9184229  9194993
  9199411  9239672  9245745  9306411  9346328  9395366  9412083  9456824  9464597  9486108
  9496560  9539041  9571703  9637131  9660920  9675040  9700045  9726740  9746139  9773535
  9792188  9857882  9958606 10007742 10076045 10098788 10104095 10127323 10171333 10195507
 10209075 10221337 10254151 10259843 10306339 10313185 10315233 10352150 10427585 10475212
 10519620 10525263 10528118 10553900 10564109 10582087 10585364 10696973 10749358 10774152
 10785637 10800433 10867769 10895837 10920540 10983268 11021967 11114331 11116035 11132034
 11164228 11175797 11187371 11248297 11272234 11426231 11478526 11481798 11499270 11510769
 11541224 11551350 11596378 11606314 11675960 11754496 11767789 11773293 11786150 11805210
 11844667 11866556 11904570 11947753 11952580 12090099 12118289 12139059 12212421 12242103
 12265425 12377924 12405937 12433587 12457247 12457942 12497694 12561376 12566064 12578475
 12631340 12643874 12711175 12730630 12748229 12787757 12818963 12820836 12893729 12905855
 12925882 12990038 13049793 13074409 13102075 13190892 13191077 13202957 13234403 13250175
 13338016 13385128 13406699 13426256 13468825 13500304 13525687 13534194 13588345 13645045
 13671111 13697624 13731729 13756133 13762947 13789145 13836398 13873009 13946359 13951622

enigmatus · #9

nodgim a écrit:
Je ne sais pas faire tourner un programme sous Linux

Ça tourne également sous Windows, mais je ne sais pas faire.

nodgim · #10

Merci bien Enigmatus.
Je voulais me rendre compte si le kième nombre est proche de la fonction 2*k²* ln k, comme ton résultat semble le dire.

nodgim · #11

Enigmatus: Jusqu'à 716 (25ème pa) c'est conforme avec ce que j'ai fait à la main. Il y a donc une quasi-certitude de la justesse de ton résultat.

Attendons un peu si d'autres intervenants sont intéressés.

dhrm77 · #12

Pourrais tu clarifier ta definition?
Par exemple, tu parles de "pak", sans le definir....

nodgim · #13

pak comme "(nombre) premier d'addition de rang k " ou kième pa.

dhrm77 · #14

1ere tentative, je trouve ceci:
0, 1, 2, 4, 7, 10, 13, 16, 19, 22, 25, 28, 31, 34, 37, 40, 43, 46, 49, 52, 55,
58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109,
112, 115, 118, 121, 124, 127, 130, 133, 136, 139, 142, 145, 148, 151, 154
qui n'est d'autre que 0, 2 et tous les nombres de la forme 3n+1.
En fait ce resultat est une analogie avec les nombres premiers avec la restriction de n'additioner que 2 nombres...

Si, quand tu dis "tel que n'importe quelle somme de pak avec un pa plus petit ", tu veux dire que 10 ne se trouve pas dans la liste puisque 10+1 est egal a 7+4? Dans ce cas je corrige mon programme, et pour ma 2eme tentative, en supposant que l'on élimine 10 pour les raisons mentionées ci-dessus, je trouve ceci:
0, 1, 2, 4, 7, 12, 20, 29, 38, 52, 73, 94, 127, 151, 181, 211, 257, 315, 373, 412, 475, 530, 545, 607,
716, 797, 861, 964, 1059, 1160, 1306, 1385, 1434, 1555, 1721, 1833, 1933, 2057, 2260, 2496,
2698, 2873, 3060, 3196, 3331, 3628, 3711, 3867, 4139, 4446, 4639, 5021, 5064, 5322, 5613,
6003, 6273, 6493, 6641, 6979, 7275, 7587, 8017, 8373, 9071, 9167, 9760, 10105, 10489, 11109,
11374, 11516, 12101, 12330, 12867, 13426, 13923, 14535, 14911, 15469, 15904, 16136, 16900,
17041, 17822, 19421, 19933, 20288, 20996, 21491, 22065, 22612, 22659, 23724, 24399, 24969,
25360, 26071, 26680, 27601, 28018, 28497, 29557, 30222, 31877, 32551, 33118, 33743, 34342,
34626, 36925, 37747, 38267, 39267, 39998, 41082, 42198, 42436, 43343, 44252, 45424, 46326,
46848, 47929, 48621, 49391, 49851, 53108, 53384, 54429, 54826, 55239, 56868, 57974, 60071,
60533, 62213, 63834, 64925, 65191, 66550, 67208, 69645, 72310, 72927, 73341, 73541, 76061,
76304, 76720, 80903, 82444, 84693, 85235, 86732, 87710, 87954, 90773, 91335, 91971, 96507,
97257, 98177, 99692, 100484, 103600, 104325, 106376, 107898, 108650, 111409, 114068,
114692, 117535, 120122, 120767, 121799, 125410, 127534, 128834, 129926, 133512, 135690,
138508, 140895, 141811, 143211, 148193, 150031, 151925, 153922, 155672, 158289, 160057,
160355, 164124, 166684, 169794, 171812, 172531, 174766, 175535, 177386, 180355, 182564,
184101, 187953, 191380, 193770, 195582, 197919, 198724, 199408, 206087, 207402, 208734,
214116, 215573, 219885, 222952, 224713, 225951, 228405, 230719, 235655, 237285, 239222,
242190, 246343, 249693, 252765, 254612, 256308, 261142, 266529, 267372, 272133, 276039,
277624, 280877, 283129, 289011, 290295, 293067, 302169, 305551, 305802, 308411, 317253,
319429, 324075, 325350, 329885, 331230, 333135, 333836, 337958, 342897, 344461, 351293,
352268, 353052, 359151, 364874, 374184, 376136, 381501, 384349, 386972, 388380, 391471,
392439, 400923, 401552, 405567, 405849, 411083, 418502, 422760, 423833, 427695, 429114,
440298, 440587, 447682, 455482, 459422, 463998, 470054, 471939, 472866, 479480, 483217,
485436, 489994, 501610, 507580, 508872, 518694, 523449, 524678, 528366, 535017, 537119,
541418, 549499, 554394, 555903, 562779, 563647, 567781, 579841, 584336, 594235, 598603,
602275, 608153, 609464, 611952, 612242, 613442, 629074, 630204, 634888, 636332, 639856,
648334, 656353, 663706, 672318, 673886, 678839, 684361, 684601, 692072, 702243, 707027,
718768, 721738, 729589, 740183, 742338, 747499, 750449, 758741, 760508, 768802, 774584,
776149, 787160, 797898, 804125, 806584, 817194, 818614, 825332, 827602, 833162, 840370,
845719, 862033, 865938, 875230, 878669, 888718, 890617, 902070, 906343, 910215, 910843,
919853, 929516, 939825, 946901, 948699, 963686, 964533, 975326, 980776, 982328, 985869,
990509, 991532, 993088, 1000796, 1036723, 1046038, 1051255, 1054627, 1057036, 1058542,
1066560, 1067301, 1085442, 1090684, 1100045, 1109938, 1117713, 1125551, 1127047,
1142150, 1153087, 1160931, 1171258, 1177757, 1180749, 1184065, 1194816, 1211959,
1216209, 1218029, 1223580, 1244015, 1248223, 1252320, 1269264, 1276613, 1279255,
1301869, 1310171, 1318685, 1324971, 1328866, 1338932, 1344801, 1346631, 1356107,
1369333, 1370197, 1370256, 1382666, 1398028, 1405380, 1412686, 1423891, 1434922,
1441552, 1444128, 1446783, 1460452, 1466228, 1470297, 1487302, 1491881, 1502457,
1522778, 1533531, 1535815, 1555065, 1566426, 1582487, 1586273, 1588260, 1613264,
1615370, 1622568, 1625549, 1629793, 1633916, 1651920, 1684782, 1688270, 1690132,
1698000, 1704193, 1710088, 1716081, 1721654, 1745050, 1748726, 1749132, 1755480,
1784439, 1789544, 1797528, 1803147, 1808508, 1836595, 1843411, 1865293, 1879181,
1881227, 1882876, 1899548, 1921113, 1934508, 1946585, 1953389, 1955054, 1972112,
1983519, 1995289, 2014876, 2022543, 2023681, 2040388, 2045104, 2048130, 2064244

et on a bien ton 716 en 25 position.

dhrm77 · #15

Et il s'agirait de la séquence: A010672 sur OEIS., et la réponse pour le 1000eme element est : 13951622.
Il faut a peu pres 13-14 minutes pour aller jusqu'a 14.000.000 et pour trouver le 1000eme élement.
Mon programe a pris 54 minutes pour aller jusqu'a 33.500.000.
Il devra me prendre entre 9 et 10 heures pour aller jusqu'a 160.000.000.
Si tu as besoin d'aide pour écrire, compiler et lancer un programme sur Linux, fait mon signe.

enigmatus · #16

@nodgim :
Voici quelques valeurs supplémentaires, avec le temps de calcul cumulé depuis le début (en secondes)

Code:

k= 1000 n=  13951622 Tcumu=   140.260
k= 2000 n=  96293106 Tcumu=  1747.451
k= 3000 n= 303322871 Tcumu=  8393.920
k= 4000 n= 688238145 Tcumu= 25036.643

nodgim · #17

Dhrm, c'est bon, bravo !
Et en plus cette suite existe déja. C'est vexant à la fin de voir qu'on n'invente plus rien....

Enigmatus, merci pour ces valeurs supplémentaires. Ton algo est nettement plus rapide que celui de Dhrm.

J'observe que dans la liste des pa, les différences d'écarts sont bien plus importantes que pour les nombres premiers !

masab · #18

Le 1000ème nombre premier d'addition est [latex]13951622[/latex] .
Pour [latex]k=1000[/latex] on a
[TeX]2\,k^2\,\ln(k) = 13815510.557964...[/TeX]

masab · #19

Voici les 1000 premiers nombres premiers d'addition :

Code:

[[1, 0], [2, 1], [3, 2], [4, 4], [5, 7], [6, 12], [7, 20], [8, 29], [9, 38], [10, 52], [11, 73], [12, 94], [13, 127], [14, 151], [15, 181], [16, 211], [17, 257], [18, 315], [19, 373], [20, 412], [21, 475], [22, 530], [23, 545], [24, 607], [25, 716], [26, 797], [27, 861], [28, 964], [29, 1059], [30, 1160], [31, 1306], [32, 1385], [33, 1434], [34, 1555], [35, 1721], [36, 1833], [37, 1933], [38, 2057], [39, 2260], [40, 2496], [41, 2698], [42, 2873], [43, 3060], [44, 3196], [45, 3331], [46, 3628], [47, 3711], [48, 3867], [49, 4139], [50, 4446], [51, 4639], [52, 5021], [53, 5064], [54, 5322], [55, 5613], [56, 6003], [57, 6273], [58, 6493], [59, 6641], [60, 6979], [61, 7275], [62, 7587], [63, 8017], [64, 8373], [65, 9071], [66, 9167], [67, 9760], [68, 10105], [69, 10489], [70, 11109], [71, 11374], [72, 11516], [73, 12101], [74, 12330], [75, 12867], [76, 13426], [77, 13923], [78, 14535], [79, 14911], [80, 15469], [81, 15904], [82, 16136], [83, 16900], [84, 17041], [85, 17822], [86, 19421], [87, 19933], [88, 20288], [89, 20996], [90, 21491], [91, 22065], [92, 22612], [93, 22659], [94, 23724], [95, 24399], [96, 24969], [97, 25360], [98, 26071], [99, 26680], [100, 27601], [101, 28018], [102, 28497], [103, 29557], [104, 30222], [105, 31877], [106, 32551], [107, 33118], [108, 33743], [109, 34342], [110, 34626], [111, 36925], [112, 37747], [113, 38267], [114, 39267], [115, 39998], [116, 41082], [117, 42198], [118, 42436], [119, 43343], [120, 44252], [121, 45424], [122, 46326], [123, 46848], [124, 47929], [125, 48621], [126, 49391], [127, 49851], [128, 53108], [129, 53384], [130, 54429], [131, 54826], [132, 55239], [133, 56868], [134, 57974], [135, 60071], [136, 60533], [137, 62213], [138, 63834], [139, 64925], [140, 65191], [141, 66550], [142, 67208], [143, 69645], [144, 72310], [145, 72927], [146, 73341], [147, 73541], [148, 76061], [149, 76304], [150, 76720], [151, 80903], [152, 82444], [153, 84693], [154, 85235], [155, 86732], [156, 87710], [157, 87954], [158, 90773], [159, 91335], [160, 91971], [161, 96507], [162, 97257], [163, 98177], [164, 99692], [165, 100484], [166, 103600], [167, 104325], [168, 106376], [169, 107898], [170, 108650], [171, 111409], [172, 114068], [173, 114692], [174, 117535], [175, 120122], [176, 120767], [177, 121799], [178, 125410], [179, 127534], [180, 128834], [181, 129926], [182, 133512], [183, 135690], [184, 138508], [185, 140895], [186, 141811], [187, 143211], [188, 148193], [189, 150031], [190, 151925], [191, 153922], [192, 155672], [193, 158289], [194, 160057], [195, 160355], [196, 164124], [197, 166684], [198, 169794], [199, 171812], [200, 172531], [201, 174766], [202, 175535], [203, 177386], [204, 180355], [205, 182564], [206, 184101], [207, 187953], [208, 191380], [209, 193770], [210, 195582], [211, 197919], [212, 198724], [213, 199408], [214, 206087], [215, 207402], [216, 208734], [217, 214116], [218, 215573], [219, 219885], [220, 222952], [221, 224713], [222, 225951], [223, 228405], [224, 230719], [225, 235655], [226, 237285], [227, 239222], [228, 242190], [229, 246343], [230, 249693], [231, 252765], [232, 254612], [233, 256308], [234, 261142], [235, 266529], [236, 267372], [237, 272133], [238, 276039], [239, 277624], [240, 280877], [241, 283129], [242, 289011], [243, 290295], [244, 293067], [245, 302169], [246, 305551], [247, 305802], [248, 308411], [249, 317253], [250, 319429], [251, 324075], [252, 325350], [253, 329885], [254, 331230], [255, 333135], [256, 333836], [257, 337958], [258, 342897], [259, 344461], [260, 351293], [261, 352268], [262, 353052], [263, 359151], [264, 364874], [265, 374184], [266, 376136], [267, 381501], [268, 384349], [269, 386972], [270, 388380], [271, 391471], [272, 392439], [273, 400923], [274, 401552], [275, 405567], [276, 405849], [277, 411083], [278, 418502], [279, 422760], [280, 423833], [281, 427695], [282, 429114], [283, 440298], [284, 440587], [285, 447682], [286, 455482], [287, 459422], [288, 463998], [289, 470054], [290, 471939], [291, 472866], [292, 479480], [293, 483217], [294, 485436], [295, 489994], [296, 501610], [297, 507580], [298, 508872], [299, 518694], [300, 523449], [301, 524678], [302, 528366], [303, 535017], [304, 537119], [305, 541418], [306, 549499], [307, 554394], [308, 555903], [309, 562779], [310, 563647], [311, 567781], [312, 579841], [313, 584336], [314, 594235], [315, 598603], [316, 602275], [317, 608153], [318, 609464], [319, 611952], [320, 612242], [321, 613442], [322, 629074], [323, 630204], [324, 634888], [325, 636332], [326, 639856], [327, 648334], [328, 656353], [329, 663706], [330, 672318], [331, 673886], [332, 678839], [333, 684361], [334, 684601], [335, 692072], [336, 702243], [337, 707027], [338, 718768], [339, 721738], [340, 729589], [341, 740183], [342, 742338], [343, 747499], [344, 750449], [345, 758741], [346, 760508], [347, 768802], [348, 774584], [349, 776149], [350, 787160], [351, 797898], [352, 804125], [353, 806584], [354, 817194], [355, 818614], [356, 825332], [357, 827602], [358, 833162], [359, 840370], [360, 845719], [361, 862033], [362, 865938], [363, 875230], [364, 878669], [365, 888718], [366, 890617], [367, 902070], [368, 906343], [369, 910215], [370, 910843], [371, 919853], [372, 929516], [373, 939825], [374, 946901], [375, 948699], [376, 963686], [377, 964533], [378, 975326], [379, 980776], [380, 982328], [381, 985869], [382, 990509], [383, 991532], [384, 993088], [385, 1000796], [386, 1036723], [387, 1046038], [388, 1051255], [389, 1054627], [390, 1057036], [391, 1058542], [392, 1066560], [393, 1067301], [394, 1085442], [395, 1090684], [396, 1100045], [397, 1109938], [398, 1117713], [399, 1125551], [400, 1127047], [401, 1142150], [402, 1153087], [403, 1160931], [404, 1171258], [405, 1177757], [406, 1180749], [407, 1184065], [408, 1194816], [409, 1211959], [410, 1216209], [411, 1218029], [412, 1223580], [413, 1244015], [414, 1248223], [415, 1252320], [416, 1269264], [417, 1276613], [418, 1279255], [419, 1301869], [420, 1310171], [421, 1318685], [422, 1324971], [423, 1328866], [424, 1338932], [425, 1344801], [426, 1346631], [427, 1356107], [428, 1369333], [429, 1370197], [430, 1370256], [431, 1382666], [432, 1398028], [433, 1405380], [434, 1412686], [435, 1423891], [436, 1434922], [437, 1441552], [438, 1444128], [439, 1446783], [440, 1460452], [441, 1466228], [442, 1470297], [443, 1487302], [444, 1491881], [445, 1502457], [446, 1522778], [447, 1533531], [448, 1535815], [449, 1555065], [450, 1566426], [451, 1582487], [452, 1586273], [453, 1588260], [454, 1613264], [455, 1615370], [456, 1622568], [457, 1625549], [458, 1629793], [459, 1633916], [460, 1651920], [461, 1684782], [462, 1688270], [463, 1690132], [464, 1698000], [465, 1704193], [466, 1710088], [467, 1716081], [468, 1721654], [469, 1745050], [470, 1748726], [471, 1749132], [472, 1755480], [473, 1784439], [474, 1789544], [475, 1797528], [476, 1803147], [477, 1808508], [478, 1836595], [479, 1843411], [480, 1865293], [481, 1879181], [482, 1881227], [483, 1882876], [484, 1899548], [485, 1921113], [486, 1934508], [487, 1946585], [488, 1953389], [489, 1955054], [490, 1972112], [491, 1983519], [492, 1995289], [493, 2014876], [494, 2022543], [495, 2023681], [496, 2040388], [497, 2045104], [498, 2048130], [499, 2064244], [500, 2095085], [501, 2101385], [502, 2105500], [503, 2112651], [504, 2126804], [505, 2143878], [506, 2157540], [507, 2165221], [508, 2168023], [509, 2177438], [510, 2180121], [511, 2200362], [512, 2211294], [513, 2214962], [514, 2220503], [515, 2261850], [516, 2268115], [517, 2269626], [518, 2279532], [519, 2286003], [520, 2305416], [521, 2310092], [522, 2318655], [523, 2323896], [524, 2347059], [525, 2349530], [526, 2352318], [527, 2368465], [528, 2372822], [529, 2377096], [530, 2407120], [531, 2432086], [532, 2443959], [533, 2448514], [534, 2451301], [535, 2466728], [536, 2507296], [537, 2521278], [538, 2522534], [539, 2529232], [540, 2550557], [541, 2554581], [542, 2570670], [543, 2574186], [544, 2604930], [545, 2610089], [546, 2623331], [547, 2624120], [548, 2678698], [549, 2686189], [550, 2690106], [551, 2698395], [552, 2721725], [553, 2739060], [554, 2742232], [555, 2753394], [556, 2757592], [557, 2762967], [558, 2785009], [559, 2793924], [560, 2818703], [561, 2824035], [562, 2845761], [563, 2855130], [564, 2864493], [565, 2885976], [566, 2887149], [567, 2910421], [568, 2921333], [569, 2938440], [570, 2945904], [571, 2964728], [572, 2989736], [573, 2997651], [574, 2998916], [575, 3014908], [576, 3017647], [577, 3051425], [578, 3074564], [579, 3098970], [580, 3101427], [581, 3113980], [582, 3127674], [583, 3131203], [584, 3145772], [585, 3150508], [586, 3169162], [587, 3171702], [588, 3197080], [589, 3209370], [590, 3222467], [591, 3244639], [592, 3256225], [593, 3293282], [594, 3295734], [595, 3302647], [596, 3341558], [597, 3355364], [598, 3359616], [599, 3363630], [600, 3376222], [601, 3398597], [602, 3410229], [603, 3419110], [604, 3432253], [605, 3448499], [606, 3481777], [607, 3509776], [608, 3538842], [609, 3552493], [610, 3557445], [611, 3587885], [612, 3601039], [613, 3628591], [614, 3642351], [615, 3646587], [616, 3651618], [617, 3659674], [618, 3670378], [619, 3696616], [620, 3698256], [621, 3742411], [622, 3747344], [623, 3770683], [624, 3804390], [625, 3806665], [626, 3838188], [627, 3857803], [628, 3864213], [629, 3872959], [630, 3895323], [631, 3899658], [632, 3933468], [633, 3969044], [634, 3981279], [635, 3992967], [636, 4002661], [637, 4021115], [638, 4050531], [639, 4054557], [640, 4059780], [641, 4083605], [642, 4106375], [643, 4113360], [644, 4131878], [645, 4136525], [646, 4139401], [647, 4145947], [648, 4180537], [649, 4187882], [650, 4211415], [651, 4252315], [652, 4256027], [653, 4268043], [654, 4277910], [655, 4300825], [656, 4336894], [657, 4340335], [658, 4407276], [659, 4414258], [660, 4450739], [661, 4484471], [662, 4501412], [663, 4504154], [664, 4522730], [665, 4536263], [666, 4546710], [667, 4578541], [668, 4604845], [669, 4615042], [670, 4622273], [671, 4633124], [672, 4641030], [673, 4648630], [674, 4668026], [675, 4674720], [676, 4704885], [677, 4745891], [678, 4788174], [679, 4805119], [680, 4809329], [681, 4826818], [682, 4830889], [683, 4861662], [684, 4897554], [685, 4912228], [686, 4914121], [687, 4917273], [688, 4930941], [689, 4950594], [690, 4989274], [691, 5028713], [692, 5063835], [693, 5092750], [694, 5100810], [695, 5138598], [696, 5146212], [697, 5169489], [698, 5176656], [699, 5182289], [700, 5185510], [701, 5191696], [702, 5192061], [703, 5208143], [704, 5220329], [705, 5242022], [706, 5308765], [707, 5344582], [708, 5355962], [709, 5360452], [710, 5371063], [711, 5409045], [712, 5453993], [713, 5489250], [714, 5499581], [715, 5510250], [716, 5526975], [717, 5545218], [718, 5582611], [719, 5584751], [720, 5598750], [721, 5605488], [722, 5610180], [723, 5619885], [724, 5679963], [725, 5701902], [726, 5765712], [727, 5806748], [728, 5822374], [729, 5852741], [730, 5864530], [731, 5867046], [732, 5881798], [733, 5909663], [734, 5915321], [735, 5930458], [736, 5994504], [737, 6001896], [738, 6026262], [739, 6038487], [740, 6053748], [741, 6092889], [742, 6104366], [743, 6112609], [744, 6134218], [745, 6183175], [746, 6190544], [747, 6191595], [748, 6197712], [749, 6217747], [750, 6225861], [751, 6346384], [752, 6362790], [753, 6377955], [754, 6409358], [755, 6443735], [756, 6480984], [757, 6486269], [758, 6516643], [759, 6534320], [760, 6545481], [761, 6562294], [762, 6583840], [763, 6614393], [764, 6648749], [765, 6675193], [766, 6681290], [767, 6691444], [768, 6743452], [769, 6766743], [770, 6819105], [771, 6823578], [772, 6865807], [773, 6880431], [774, 6899149], [775, 6923707], [776, 6942243], [777, 6964345], [778, 7001148], [779, 7014530], [780, 7031996], [781, 7044762], [782, 7046459], [783, 7107335], [784, 7124224], [785, 7148280], [786, 7179250], [787, 7257373], [788, 7263359], [789, 7294864], [790, 7309784], [791, 7372937], [792, 7387910], [793, 7398845], [794, 7411142], [795, 7420083], [796, 7436721], [797, 7463667], [798, 7473302], [799, 7479209], [800, 7507361], [801, 7510944], [802, 7536617], [803, 7585108], [804, 7585551], [805, 7620998], [806, 7625795], [807, 7682002], [808, 7694416], [809, 7779304], [810, 7815208], [811, 7856689], [812, 7874700], [813, 7896514], [814, 7962900], [815, 7997387], [816, 8005949], [817, 8010600], [818, 8032104], [819, 8070882], [820, 8114086], [821, 8122021], [822, 8128586], [823, 8138970], [824, 8178553], [825, 8217763], [826, 8223531], [827, 8295379], [828, 8341493], [829, 8349393], [830, 8370500], [831, 8403355], [832, 8413339], [833, 8464355], [834, 8535076], [835, 8573069], [836, 8588685], [837, 8610016], [838, 8612551], [839, 8641913], [840, 8666288], [841, 8691731], [842, 8715748], [843, 8740335], [844, 8814085], [845, 8840089], [846, 8851958], [847, 8864092], [848, 8872575], [849, 8913784], [850, 8960660], [851, 8966738], [852, 8974680], [853, 9021171], [854, 9061321], [855, 9105434], [856, 9123927], [857, 9130531], [858, 9131860], [859, 9184229], [860, 9194993], [861, 9199411], [862, 9239672], [863, 9245745], [864, 9306411], [865, 9346328], [866, 9395366], [867, 9412083], [868, 9456824], [869, 9464597], [870, 9486108], [871, 9496560], [872, 9539041], [873, 9571703], [874, 9637131], [875, 9660920], [876, 9675040], [877, 9700045], [878, 9726740], [879, 9746139], [880, 9773535], [881, 9792188], [882, 9857882], [883, 9958606], [884, 10007742], [885, 10076045], [886, 10098788], [887, 10104095], [888, 10127323], [889, 10171333], [890, 10195507], [891, 10209075], [892, 10221337], [893, 10254151], [894, 10259843], [895, 10306339], [896, 10313185], [897, 10315233], [898, 10352150], [899, 10427585], [900, 10475212], [901, 10519620], [902, 10525263], [903, 10528118], [904, 10553900], [905, 10564109], [906, 10582087], [907, 10585364], [908, 10696973], [909, 10749358], [910, 10774152], [911, 10785637], [912, 10800433], [913, 10867769], [914, 10895837], [915, 10920540], [916, 10983268], [917, 11021967], [918, 11114331], [919, 11116035], [920, 11132034], [921, 11164228], [922, 11175797], [923, 11187371], [924, 11248297], [925, 11272234], [926, 11426231], [927, 11478526], [928, 11481798], [929, 11499270], [930, 11510769], [931, 11541224], [932, 11551350], [933, 11596378], [934, 11606314], [935, 11675960], [936, 11754496], [937, 11767789], [938, 11773293], [939, 11786150], [940, 11805210], [941, 11844667], [942, 11866556], [943, 11904570], [944, 11947753], [945, 11952580], [946, 12090099], [947, 12118289], [948, 12139059], [949, 12212421], [950, 12242103], [951, 12265425], [952, 12377924], [953, 12405937], [954, 12433587], [955, 12457247], [956, 12457942], [957, 12497694], [958, 12561376], [959, 12566064], [960, 12578475], [961, 12631340], [962, 12643874], [963, 12711175], [964, 12730630], [965, 12748229], [966, 12787757], [967, 12818963], [968, 12820836], [969, 12893729], [970, 12905855], [971, 12925882], [972, 12990038], [973, 13049793], [974, 13074409], [975, 13102075], [976, 13190892], [977, 13191077], [978, 13202957], [979, 13234403], [980, 13250175], [981, 13338016], [982, 13385128], [983, 13406699], [984, 13426256], [985, 13468825], [986, 13500304], [987, 13525687], [988, 13534194], [989, 13588345], [990, 13645045], [991, 13671111], [992, 13697624], [993, 13731729], [994, 13756133], [995, 13762947], [996, 13789145], [997, 13836398], [998, 13873009], [999, 13946359], [1000, 13951622]]

nodgim · #20

Masab, c'est bon également bravo !

Cette question tombe un peu à coté du sujet qui me préoccupe depuis quelque temps :

Si on "additionne" 2 nombres binaires d'une liste, toutes les "sommes" doivent être distinctes. Mais il s'agit d'une addition particulière: elle se fait bit à bit avec : 0+0=0; 1+0=0+1=1 et 1+1=1.

Avec combien de bits minimum peut on faire une liste de 1000 nombres binaires conformes à cette contrainte ?

nodgim · #21

Attention Masab, il doit y avoir une erreur d'interprétation.

Tu donnes les premiers nombres: 0,1,2,4,7.
En binaire, en additionnant bit à bit 7+0 , 7+1 , 7+2 et 7+4 :
111+000=111
111+001=111
111+010=111
111+100=111
somme identique à chaque fois.

Ou alors j'ai mal compris tes données.

masab · #22

J'ai supprimé mon message sur le bit à bit.
En effet j'avais repris la 1er problème en remplaçant l'addition par l'addition bit à bit.
Or le 2ème problème est différent...

dhrm77 · #23

Question rapidité, c'est peu etre du au fait que mon programme est écrit pour aller beaucoup plus loin. Je n'utilise qu'un seul bit par nombre, et de ce fait ca prend plus de temps à le tester et changer d'etat. Mais ca me premettrait de tester les nombres jusqu'a 8.000.000.000.

J'ai egalement trouvé ceci: qui est la meme liste (jusqu'a 260.000.000) mais chaque nombre est augmenté de 1.

Update: J'ai re-écrit pour utiliser des octets à la place des bits., ce qui va 3 fois plus vite mais on est limité a 1.000.000.000. C'est parti pour trouver tous ces nombres jusqu'à 500,000,000 en quelques 31 heures.

masab · #24

Avec l'addition bit à bit, la liste comprenant [latex]0[/latex] et les [latex]2^k[/latex] avec [latex]0\leq k\leq 998[/latex] convient. Elle utilise [latex]999[/latex] bits.

scarta · #25

13951622, trouvé avec 7 lignes de code, que voila

Code:

int target = 1000, newPaIndex = 0, index = 0, currentPa = 0;
bool[] sums = new bool[100000000]; int[] paList = new int[target];
for (; newPaIndex < target; currentPa++)
{
    for (index = 0; index < newPaIndex && !sums[currentPa + paList[index]]; index++) ;
    if (index != newPaIndex) continue;
    for (index = 0; index < newPaIndex; index++) sums[currentPa + paList[index]] = true;
    paList[newPaIndex++] = currentPa;
}

J'ai aussi une autre version du code, qui utilise un crible, environ 15% plus rapide mais moins concise (et puis le gain commence à devenir significatif à partir du 2000ème)

Pour info, le 2000ème est 96293106

Forum dédié aux énigmes et à toutes formes de jeux de logique.	Déconnexion
Tu n'es pas identifié sur Prise2tete : s'identifier. Accueil Forum	[+]

#1 - 01-05-2016 08:16:34

Nombes premiers d'addition

#0 Pub

#2 - 01-05-2016 11:37:23

Nombres premiers d''addition

#3 - 01-05-2016 13:11:21

nombres premiers d'additiob

#4 - 01-05-2016 16:08:00

nolbres premiers d'addition

#5 - 01-05-2016 16:50:14

Nombres premiers d'additoin

nodgim #4 a écrit:

Code:

Code:

#6 - 01-05-2016 17:22:02

Nombres premier d'addition

#7 - 01-05-2016 17:32:40

Nombres prremiers d'addition

#8 - 01-05-2016 17:35:23

nombees premiers d'addition

Code:

#9 - 01-05-2016 17:36:44

Nombres premiers d'additio

nodgim a écrit:

#10 - 01-05-2016 17:39:55

nombres premierd d'addition

#11 - 01-05-2016 17:45:33

Nombres premiers d'additin

#12 - 01-05-2016 18:39:56

nombres premiers d'addotion

#13 - 01-05-2016 18:53:29

Nombres premiers d'addiion

#14 - 01-05-2016 20:18:21

nombred premiers d'addition

#15 - 01-05-2016 20:21:38

nombtes premiers d'addition

#16 - 02-05-2016 00:28:49

Nombres premiers da'ddition

Code:

#17 - 02-05-2016 08:01:24

nombres premiers d'asdition

#18 - 02-05-2016 10:18:57

nombres premiers d'zddition

#19 - 02-05-2016 10:33:06

Nombres pemiers d'addition

Code:

#20 - 02-05-2016 12:10:19

nombrrs premiers d'addition

#21 - 02-05-2016 20:01:04

Nombres preemiers d'addition

#22 - 02-05-2016 20:20:22

nombres ptemiers d'addition

#23 - 03-05-2016 00:06:33

Nomres premiers d'addition

#24 - 03-05-2016 14:25:09

Nombres premires d'addition

#25 - 03-05-2016 15:03:34

nombres przmiers d'addition

Code:

Réponse rapide

Sujets similaires

Mots clés des moteurs de recherche

Pied de page des forums