Курсовая: Сумма делителей числа

Курсовая: Сумма делителей числа

[312, 840]

[313, 314]

[314, 474]

[315, 624]

[316, 560]

[317, 318]

[318, 648]

[319, 360]

[320, 762]

[321, 432]

[322, 576]

[323, 360]

[324, 847]

[325, 434]

[326, 492]

[327, 440]

[328, 630]

[329, 384]

[330, 864]

[331, 332]

[332, 588]

[333, 494]

[334, 504]

[335, 408]

[336, 992]

[337, 338]

[338, 549]

[339, 456]

[340, 756]

[341, 384]

[342, 780]

[343, 400]

[344, 660]

[345, 576]

[346, 522]

[347, 348]

[348, 840]

[349, 350]

[350, 744]

[351, 560]

[352, 756]

[353, 354]

[354, 720]

[355, 432]

[356, 630]

[357, 576]

[358, 540]

[359, 360]

[360, 1170]

[361, 381]

[362, 546]

[363, 532]

[364, 784]

[365, 444]

[366, 744]

[367, 368]

[368, 744]

[369, 546]

[370, 684]

[371, 432]

[372, 896]

[373, 374]

[374, 648]

[375, 624]

[376, 720]

[377, 420]

[378, 960]

[379, 380]

[380, 840]

[381, 512]

[382, 576]

[383, 384]

[384, 1020]

[385, 576]

[386, 582]

[387, 572]

[388, 686]

[389, 390]

[390, 1008]

[391, 432]

[392, 855]

[393, 528]

[394, 594]

[395, 480]

[396, 1092]

[397, 398]

[398, 600]

[399, 640]

[400, 961]

[401, 402]

[402, 816]

[403, 448]

[404, 714]

[405, 726]

[406, 720]

[407, 456]

[408, 1080]

[409, 410]

[410, 756]

[411, 552]

[412, 728]

[413, 480]

[414, 936]

[415, 504]

[416, 882]

[417, 560]

[418, 720]

[419, 420]

[420, 1344]

[421, 422]

[422, 636]

[423, 624]

[424, 810]

[425, 558]

[426, 864]

[427, 496]

[428, 756]

[429, 672]

[430, 792]

[431, 432]

[432, 1240]

[433, 434]

[434, 768]

[435, 720]

[436, 770]

[437, 480]

[438, 888]

[439, 440]

[440, 1080]

[441, 741]

[442, 756]

[443, 444]

[444, 1064]

[445, 540]

[446, 672]

[447, 600]

[448, 1016]

[449, 450]

[450, 1209]

[451, 504]

[452, 798]

[453, 608]

[454, 684]

[455, 672]

[456, 1200]

[457, 458]

[458, 690]

[459, 720]

[460, 1008]

[461, 462]

[462, 1152]

[463, 464]

[464, 930]

[465, 768]

[466, 702]

[467, 468]

[468, 1274]

[469, 544]

[470, 864]

[471, 632]

[472, 900]

[473, 528]

[474, 960]

[475, 620]

[476, 1008]

[477, 702]

[478, 720]

[479, 480]

[480, 1512]

[481, 532]

[482, 726]

[483, 768]

[484, 931]

[485, 588]

[486, 1092]

[487, 488]

[488, 930]

[489, 656]

[490, 1026]

[491, 492]

[492, 1176]

[493, 540]

[494, 840]

[495, 936]

[496, 992]

[497, 576]

[498, 1008]

[499, 500]

[500, 1092]

[501, 672]

[502, 756]

[503, 504]

[504, 1560]

[505, 612]

[506, 864]

[507, 732]

[508, 896]

[509, 510]

[510, 1296]

[511, 592]

[512, 1023]

[513, 800]

[514, 774]

[515, 624]

[516, 1232]

[517, 576]

[518, 912]

[519, 696]

[520, 1260]

[521, 522]

[522, 1170]

[523, 524]

[524, 924]

[525, 992]

[526, 792]

[527, 576]

[528, 1488]

[529, 553]

[530, 972]

[531, 780]

[532, 1120]

[533, 588]

[534, 1080]

[535, 648]

[536, 1020]

[537, 720]

[538, 810]

[539, 684]

[540, 1680]

[541, 542]

[542, 816]

[543, 728]

[544, 1134]

[545, 660]

[546, 1344]

[547, 548]

[548, 966]

[549, 806]

[550, 1116]

[551, 600]

[552, 1440]

[553, 640]

[554, 834]

[555, 912]

[556, 980]

[557, 558]

[558, 1248]

[559, 616]

[560, 1488]

[561, 864]

[562, 846]

[563, 564]

[564, 1344]

[565, 684]

[566, 852]

[567, 968]

[568, 1080]

[569, 570]

[570, 1440]

[571, 572]

[572, 1176]

[573, 768]

[574, 1008]

[575, 744]

[576, 1651]

[577, 578]

[578, 921]

[579, 776]

[580, 1260]

[581, 672]

[582, 1176]

[583, 648]

[584, 1110]

[585, 1092]

[586, 882]

[587, 588]

[588, 1596]

[589, 640]

[590, 1080]

[591, 792]

[592, 1178]

[593, 594]

[594, 1440]

[595, 864]

[596, 1050]

[597, 800]

[598, 1008]

[599, 600]

[600, 1860]

[601, 602]

[602, 1056]

[603, 884]

[604, 1064]

[605, 798]

[606, 1224]

[607, 608]

[608, 1260]

[609, 960]

[610, 1116]

[611, 672]

[612, 1638]

[613, 614]

[614, 924]

[615, 1008]

[616, 1440]

[617, 618]

[618, 1248]

[619, 620]

[620, 1344]

[621, 960]

[622, 936]

[623, 720]

[624, 1736]

[625, 781]

[626, 942]

[627, 960]

[628, 1106]

[629, 684]

[630, 1872]

[631, 632]

[632, 1200]

[633, 848]

[634, 954]

[635, 768]

[636, 1512]

[637, 798]

[638, 1080]

[639, 936]

[640, 1530]

[641, 642]

[642, 1296]

[643, 644]

[644, 1344]

[645, 1056]

[646, 1080]

[647, 648]

[648, 1815]

[649, 720]

[650, 1302]

[651, 1024]

[652, 1148]

[653, 654]

[654, 1320]

[655, 792]

[656, 1302]

[657, 962]

[658, 1152]

[659, 660]

[660, 2016]

[661, 662]

[662, 996]

[663, 1008]

[664, 1260]

[665, 960]

[666, 1482]

[667, 720]

[668, 1176]

[669, 896]

[670, 1224]

[671, 744]

[672, 2016]

[673, 674]

[674, 1014]

[675, 1240]

[676, 1281]

[677, 678]

[678, 1368]

[679, 784]

[680, 1620]

[681, 912]

[682, 1152]

[683, 684]

[684, 1820]

[685, 828]

[686, 1200]

[687, 920]

[688, 1364]

[689, 756]

[690, 1728]

[691, 692]

[692, 1218]

[693, 1248]

[694, 1044]

[695, 840]

[696, 1800]

[697, 756]

[698, 1050]

[699, 936]

[700, 1736]

[701, 702]

[702, 1680]

[703, 760]

[704, 1524]

[705, 1152]

[706, 1062]

[707, 816]

[708, 1680]

[709, 710]

[710, 1296]

[711, 1040]

[712, 1350]

[713, 768]

[714, 1728]

[715, 1008]

[716, 1260]

[717, 960]

[718, 1080]

[719, 720]

[720, 2418]

[721, 832]

[722, 1143]

[723, 968]

[724, 1274]

[725, 930]

[726, 1596]

[727, 728]

[728, 1680]

[729, 1093]

[730, 1332]

[731, 792]

[732, 1736]

[733, 734]

[734, 1104]

[735, 1368]

[736, 1512]

[737, 816]

[738, 1638]

[739, 740]

[740, 1596]

[741, 1120]

[742, 1296]

[743, 744]

[744, 1920]

[745, 900]

[746, 1122]

[747, 1092]

[748, 1512]

[749, 864]

[750, 1872]

[751, 752]

[752, 1488]

[753, 1008]

[754, 1260]

[755, 912]

[756, 2240]

[757, 758]

[758, 1140]

[759, 1152]

[760, 1800]

[761, 762]

[762, 1536]

[763, 880]

[764, 1344]

[765, 1404]

[766, 1152]

[767, 840]

[768, 2044]

[769, 770]

[770, 1728]

[771, 1032]

[772, 1358]

[773, 774]

[774, 1716]

[775, 992]

[776, 1470]

[777, 1216]

[778, 1170]

[779, 840]

[780, 2352]

[781, 864]

[782, 1296]

[783, 1200]

[784, 1767]

[785, 948]

[786, 1584]

[787, 788]

[788, 1386]

[789, 1056]

[790, 1440]

[791, 912]

[792, 2340]

[793, 868]

[794, 1194]

[795, 1296]

[796, 1400]

[797, 798]

[798, 1920]

[799, 864]

[800, 1953]

[801, 1170]

[802, 1206]

[803, 888]

[804, 1904]

[805, 1152]

[806, 1344]

[807, 1080]

[808, 1530]

[809, 810]

[810, 2178]

[811, 812]

[812, 1680]

[813, 1088]

[814, 1368]

[815, 984]

[816, 2232]

[817, 880]

[818, 1230]

[819, 1456]

[820, 1764]

[821, 822]

[822, 1656]

[823, 824]

[824, 1560]

[825, 1488]

[826, 1440]

[827, 828]

[828, 2184]

[829, 830]

[830, 1512]

[831, 1112]

[832, 1778]

[833, 1026]

[834, 1680]

[835, 1008]

[836, 1680]

[837, 1280]

[838, 1260]

[839, 840]

[840, 2880]

[841, 871]

[842, 1266]

[843, 1128]

[844, 1484]

[845, 1098]

[846, 1872]

[847, 1064]

[848, 1674]

[849, 1136]

[850, 1674]

[851, 912]

[852, 2016]

[853, 854]

[854, 1488]

[855, 1560]

[856, 1620]

[857, 858]

[858, 2016]

[859, 860]

[860, 1848]

[861, 1344]

[862, 1296]

[863, 864]

[864, 2520]

[865, 1044]

[866, 1302]

[867, 1228]

[868, 1792]

[869, 960]

[870, 2160]

[871, 952]

[872, 1650]

[873, 1274]

[874, 1440]

[875, 1248]

[876, 2072]

[877, 878]

[878, 1320]

[879, 1176]

[880, 2232]

[881, 882]

[882, 2223]

[883, 884]

[884, 1764]

[885, 1440]

[886, 1332]

[887, 888]

[888, 2280]

[889, 1024]

[890, 1620]

[891, 1452]

[892, 1568]

[893, 960]

[894, 1800]

[895, 1080]

[896, 2040]

[897, 1344]

[898, 1350]

[899, 960]

[900, 2821]

[901, 972]

[902, 1512]

[903, 1408]

[904, 1710]

[905, 1092]

[906, 1824]

[907, 908]

[908, 1596]

[909, 1326]

[910, 2016]

[911, 912]

[912, 2480]

[913, 1008]

[914, 1374]

[915, 1488]

[916, 1610]

[917, 1056]

[918, 2160]

[919, 920]

[920, 2160]

[921, 1232]

[922, 1386]

[923, 1008]

[924, 2688]

[925, 1178]

[926, 1392]

[927, 1352]

[928, 1890]

[929, 930]

[930, 2304]

[931, 1140]

[932, 1638]

[933, 1248]

[934, 1404]

[935, 1296]

[936, 2730]

[937, 938]

[938, 1632]

[939, 1256]

[940, 2016]

[941, 942]

[942, 1896]

[943, 1008]

[944, 1860]

[945, 1920]

[946, 1584]

[947, 948]

[948, 2240]

[949, 1036]

[950, 1860]

[951, 1272]

[952, 2160]

[953, 954]

[954, 2106]

[955, 1152]

[956, 1680]

[957, 1440]

[958, 1440]

[959, 1104]

[960, 3048]

[961, 993]

[962, 1596]

[963, 1404]

[964, 1694]

[965, 1164]

[966, 2304]

[967, 968]

[968, 1995]

[969, 1440]

[970, 1764]

[971, 972]

[972, 2548]

[973, 1120]

[974, 1464]

[975, 1736]

[976, 1922]

[977, 978]

[978, 1968]

[979, 1080]

[980, 2394]

[981, 1430]

[982, 1476]

[983, 984]

[984, 2520]

[985, 1188]

[986, 1620]

[987, 1536]

[988, 1960]

[989, 1056]

[990, 2808]

[991, 992]

[992, 2016]

[993, 1328]

[994, 1728]

[995, 1200]

[996, 2352]

[997, 998]

[998, 1500]

[999, 1520]

[1000, 2340]

Теперь посмотрим, все ли числа являются суммой делителей какого-либо числа и

есть ли такие числа сумма делителей которых равна (в первых двух сотнях).

Ниже приведена таблица: [[4, 7]](на втором месте сумма делителей, а на первом

число с данной суммой делителей) . [[1, 1]], [2] (т.е. нет такого числа с

суммой делителей равной двум):

[1,1]

[2]

[2,3]

[3,4]

[5]

[5,6]

[4,7]

[7,8]

[9]

[10]

[11]

[6,12]

[11, 12]

[9,13]

[13,14]

[8,15]

[16]

[17]

[10,18]

[17,18]

[19]

[19.20]

[21]

[22]

[23]

[14,24]

[15,24]

[23,24]

[25]

[26]

[27]

[12, 28].

[29]

[29,30]

[16,31]

[25.31]

[21,32]

[31,32]

[33]

[34]

[35]

[22,36]

[37]

[37,38]

[18,39]

[27, 40]

[41]

[20,42]

[26,42]

[41,42].

[43]

[43,44].

[45]

[46]

[47]

[33,48].

[35,4 8]

[47,48]

[49]

[50]

[51]

[52]

[53]

[34,54]

[53, 54]

[55]

[28,56]

[39.56]

[49,57]

[58]

[59]

[24,60]

[38.60]

[59,60]

[61]

[61,62]

[32,63]

[64]

[65]

[66]

[67]

[67, 68]

[69]

[70]

[71]

[30,72]

[46,72]

[51,72]

[55,72]

[71,72]

[73]

[73,74]

[75]

[76]

[77]

[45,78]

[79]

[57,80]

[79,80]

[81]

[82]

[83]

[44,84]

[65,84]

[83,84]

[85]

[86]

[87]

[88]

[89]

[40, 90]

[58,90]

[89,90]

[36,91]

[92]

[50,93].

[94]

[95]

[42, 96]

[62,96]

[69,96]

[77,96]

[97]

[52,98]

[97,98]

[99]

[100]

[101]

[102]

[103]

[63,104]

[105]

[106]

[107]

[85,108]

[109]

[110]

[111]

[91, 112]

[113]

[74,114],

[115]

[116]

[117]

[118]

[119]

[54,120]

[56,120]

[87,120]

[95,120]

[81,121]

[122]

[123]

[48,124]

[75, 124]

[125]

[68,126]

[82.126]

[64,127]

[9 3,128]

[129]

[130]

[131]

[86,132]

[133]

[134]

[135]

[136]

[137]

[138]

[139]

[76,140]

[141]

[142]

[143]

[66,144]

[70,144]

[94,144]

[145]

[146]

[147]

[178]

[149]

[150]

[151]

[152]

[153]

[154]

[155]

[99,156]

[157]

[158]

[159]

[160]

[161]

[162]

[163]

[164]

[165]

[166]

[167]

[60,168]

[78,168]

[92,168]

[169]

[170]

[98,171]

[172]

[173]

[174]

[175]

[176]

[177]

[178]

[179]

[88,180]

[181]

[182]

[183]

[184]

[185]

[80,186]

[187]

[188]

[189]

[190]

[191]

[192]

[193]

[194]

[72,195]

[196]

[197]

[198]

[199]

[200]

Как мы заметили, есть такие числа, которые не являются суммой делителей ни

одного числа и так же есть такие числа, которые являются суммой делителей ни

одного, а нескольких чисел. Теперь посмотрим только те числа, которые

являются суммой делителей ни одного, а нескольких чисел:

[6,12], [11,12]

[10,18], [17,18]

[14,24], [15,24], [23,24]

[16,31]. [25,31]

[21,32], [31,32]

[20, 42], [26,42], [41,42]

[33,48], [35,48], [47,48]

[34,5 4], [53,54]

[28,56], [39,56]

[24,60], [38,60], [59, 60]

[30,72], [46,72], [51,72], [55,72], [71,72]

[57,80], [79,80]

[44,84], [65,84], [83,84]

[40,90], [58, 9 0], [89,90]

[42,96], [62,96], [69,96], [77,96]

[52,98], [97,98]

[54,120], [56, 120], [87,120], [95,120]

[48,124], [75,124]

[68,126], [82,126]

[66,144], [70, 144], [94,144]

[60,168], [78,168], [92,168]

Отсюда можно сделать вывод, что нахождение числа по его сумме делителей не

всегда возможно и не всегда однозначно.

Теперь построим график. По оси Х расположим числа, а по оси Y их сумму

делителей (числа от 1 до 1000):

Посмотрим, что же у нас получилось: на графике отчётливо просматриваются

несколько прямых линий, например, нижняя это – простые числа. Верхняя граница –

это наиболее сложные числа (имеющие наибольшее количество делителей) - это не

прямая, но и не парабола. Скорее всего, – это показательная функция (у = а

х).

В мемуарах Эйлера я нашел много интересных мне рассуждений(σ(n) – сумма

делителей числа n): Определив значение σ(n) мы ясно видим, что если p –

простое, то σ(p)= p + 1. σ(1)=1, а если число n – составное, то

σ(n)>1 + n.

Если a, b, c, d – различные простые числа, то мы видим:

σ(ab)=1+a+b+ab=(1+a)(1+b)= σ(a)σ(b)

σ(abcd)= σ(a)σ(b)σ(c)σ(d)

σ(a^2)=1+a+a2=

σ(a^3)=1+a+a2+a3=

И вообще

σ(nn)=

Пользуясь этим:

σ(aqbwcedr)= σ(aq)σ(bw)σ(ce)σ(dr)

Например σ(360), 360 = 23*32*5 => σ(23

) σ(32) σ(5)=15*13*6=1170.

Чтобы показать последовательность сумм делителей приведём таблицу:

n	0	1	2	3	4	5	6	7	8	9
0	-	1	3	4	7	6	12	8	15	13
10	18	12	28	14	24	24	31	18	39	20
20	42	32	36	24	60	31	42	40	56	30
30	72	32	63	48	54	48	91	38	60	56
40	90	42	96	44	84	78	72	48	124	57
50	93	72	98	54	120	72	120	80	90	60
60	168	62	96	104	127	84	144	68	126	96
70	144	72	195	74	114	424	140	96	168	80
80	186	121	126	84	224	108	132	120	180	90
90	234	112	168	128	144	120	252	98	171	156

Если σ(n) обозначает член любой этой последовательности, а σ(n -

1), σ(n - 2), σ(n - 3). предшествующие члены, то σ(n) всегда

можно получить по нескольким предыдущим членам:

σ(n) = σ(n - 1) + σ(n - 2) - σ(n - 5) - σ(n - 7) +

σ(n - 12) + σ(n - 15) - σ(n - 22) - σ(n – 26) + . (**)

Знаки «+» «-» в правой части формулы попарно чередуются. Закон чисел 1, 2, 5,

7, 12, 15.,которые мы должны вычитать из рассматриваемого числа n, станет

ясен если мы возьмем их разности:

Числа:1, 2, 5, 7, 12, 15, 22, 26, 35, 40, 51, 57, 70, 77, 92, 100.

Разности: 1, 3, 2, 5, 3, 7, 4, 9, 5, 11, 6, 13, 7, 15, 8.

В самом деле, мы имеем здесь поочередно все целые числа 1, 2, 3, 4, 5, 6, 7.

и нечетные 3, 5, 7,9 11.

Хотя эта последовательность бесконечна, мы должны в каждом случае брать

только те члены, для которых числа стоящие под знаком σ, еще

положительны, и опускать σ для отрицательных чисел. Если в нашей формуле

встретиться σ(0), то, поскольку его значение само по себе является

неопределённым, мы должны подставить вместо σ(0) рассматриваемое число

n. Примеры:

σ(1) = σ(0) =1

= 1

σ(2) = σ(1) + σ(0) =

1 + 2 = 3

.

σ(20) = σ(19)+σ(18)-σ(15)-

σ(13)+9σ(8)+σ(5)=20+39-24-14+15+6= 42

Доказательство теоремы (**) я приводить не буду.

Вообще, найти сумму всех делителей числа можно с помощью канонического

разложения натурального числа (это уже было сказано выше). Сумму делителей

числа n обозначают σ(n). Легко найти σ(n) для небольших

натуральных чисел, например σ(12) = 1+2+3+4+6+12=28(это было приведено

выше). Но при достаточно больших числах отыскивание всех делителей, а тем

более их суммы становится затруднительным. Совсем другое дело, если уже

известно, что каноническое

разложение числа n таково:.

Его делителями являются все числа

, для которых 0 ≤ βs ≤ αs, s = 1, .,

k. Ясно, что σ(n) представляет собой сумму всех таких чисел при различных

значениях показателей

β1, β2, . βk. Этот результат мы

получим раскрыв скобки в произведении

По формуле конечного числа членов геометрической прогрессии приходим к равенству

(*)

По этой формуле σ(360) = .

Формулу для вычисления значения функции σ(n) вывел замечательный

английский математик Джон Валлис(1616 - 1703) – один из основателей и первых

членов Лондонского Королевства общества (Академии наук). Он был первым из

английских математиков, начавших заниматься математическим анализом. Ему

принадлежат многие обозначения и термины, применяемые сейчас в математике, в

частности знак ∞ для обозначения бесконечности. Валлис вывел

удивительную формулу, представляющую число π в виде бесконечного

произведения:

Д. Валлис много занимался комбинаторикой и её приложениями к теории шифров,

не без основания считая себя родоначальником новой науки – криптологии (от

греч. «криптос» - тайный, «логос» - наука, учение). Он был одним из лучших

шифровальщиков своего времени и по поручению министра полиции Терло занимался

в республиканском правительстве Кромвеля расшифровкой посланий монархических

заговорщиков.

С функцией σ(n) связан ряд любопытных задач. Например:

1.) Найти пару целых чисел, удовлетворяющих условию: σ(m1)=m

2, σ(m2)=m1.

Некоторые из них не удаётся решить даже с использованием формулы (*). Так,

например, не иначе как подбором можно найти числа, для которых σ(n) есть

квадрат некоторого натурального числа. Такими числами являются 22, 66, 70,

81, 343, 1501, 4479865. Вот ещё две задачи, приведённые в 1657 г. Пьером

Ферма:

1.) найти такое m, для которого σ(m3) – квадрат натурального

числа (Ферма нашёл не одно решение этой задачи);

2.) найти такое m, для которого σ(m2) – куб натурального числа.

Например, одним из решений первой задачи является m = 7, а для второй m = 43098.

С помощью программы Derive, я попробовал найти ещё решения и у меня этого не

получилось. (я рассматривал σ(m3) = n2, где m

принимает значения от 1 до 1000, а n от 1 до 5000 в 1.) и тоже самое в 2.) )

Формулы:

1. DELITELI(m) := SELECT(MOD(m, n) = 0, n, 1, m)

DIMENSION(DELITELI(m))

2. SUMMADELITELEY(m) := Σ

ELEMENT(DELITELI(m), i)

i=1

Страницы: 1, 2