LINUX.ORG.RU
Форум — Development  

Совершенные числа


0

3

Совершенные числа известны со времен Пифагора. Число называется совершенным, если сумма всех его делителей, за исключением самого числа,равнялась этому числу. Так, число 6 — совершенное, поскольку его делители 1, 2 и 3 в сумме составляют 6.

Я написал пару тестов на питоне, которые падают по причине того, что ядро у меня сейчас на данный момент 32-битное, и вся память сжирается.

Первый тест считает только первые 5 совершенных чисел, второй - семь

Мне интересно, какие результаты будут на 64-битной архитектуре

В первом тесте можно поиграться с диапазоном 2,14 Во втором использовать в массиве бОльше чисел из последовательности Мерсенна 

for i in range(2,14):
    x=2**(i-1)*(2**i-1)
    s=1
    for j in range(2,x/2+2):
        if(x%j==0):
          s+=j
    if (x==s):
        print '=====' +str(x)


n=[2, 3, 5, 7, 13, 17, 19]
for i in n:
  s=1
  s = reduce(lambda x, y: x+y , range(1, 2**i))
  print s
★★★★★
← Помогите определить формат данных принятых от сервера
декоратор Python →

Знатно. Хацкель не осилил?

anonymous
() 
$ python
Python 2.7.5 (default, May 20 2013, 11:51:12) 
[GCC 4.7.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> for i in range(2,32):
...     x=2**(i-1)*(2**i-1)
...     s=1
...     for j in range(2,x/2+2):
...         if(x%j==0):
...           s+=j
...     if (x==s):
...         print '=====' +str(x)
... 
=====6
=====28
=====496
=====8128
=====33550336
Killed
ziemin ★★
()
Ответ на: комментарий от kto_tama 
$ python2
Python 2.7.4 (default, Apr 19 2013, 18:28:01) 
[GCC 4.7.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> for i in range(2,14):
...     x=2**(i-1)*(2**i-1)
...     s=1
...     for j in range(2,x/2+2):
...         if(x%j==0):
...           s+=j
...     if (x==s):
...         print '=====' +str(x)
... 
=====6
=====28
=====496
=====8128
=====33550336
>>>
Deleted
()
Ответ на: комментарий от Deleted 
>>> n=[2, 3, 5, 7, 13, 17, 19]
>>> for i in n:
...   s=1
...   s = reduce(lambda x, y: x+y , range(1, 2**i))
...   print s
... 
6
28
496
8128
33550336
8589869056
137438691328
>>>
Deleted
()

ядро у меня сейчас на данный момент 32-битное, и вся память сжирается

Можно подумать, на 64х битах не сожрётся.

redgremlin ★★★★★
()

Это тред об использовании xrange'а и sum'а?

aedeph_ ★★
() 
irb(main):012:0> Prime.take(8).each{|i|p (1..2**i).reduce(&:+)}
10
36
528
8256
2098176
33558528
8590000128
137439215616
=> [2, 3, 5, 7, 11, 13, 17, 19]
cdshines ★★★★★
()
Ответ на: комментарий от cdshines 
"\n".join(str(sum(xrange(1,2**i))) for i in [2, 3, 5, 7, 11, 13, 17, 19])

"\n".join(filter(lambda x: x, ((lambda x: str(x) if x == reduce(lambda s,j: s + (j if (x%j==0) else 0), xrange(2, x/2+2), 1) else "")(2**(i-1)*(2**i-1)) for i in xrange(2,14))))
aedeph_ ★★
()

С учетом того, что нечетных совершенных чисел науке неизвестно, насколько я помню, то можно упростить задачу. Четные совершенные числа имеют вид:

(2^(n + 1) — 1) * 2^n при условии, что 2^(n+1) - 1 простое число.

Так что формально, поиск совершенных чисел можно свести к поиску простых чисел, это много памяти не жрет :)

cathode ★
()
Ответ на: комментарий от cathode

Так что формально, поиск совершенных чисел можно свести к поиску простых чисел, это много памяти не жрет :)

во втором примере это у меня и делается
но на 8-й итерации питон падает - memoryerror

kto_tama ★★★★★
() автор топика
Ответ на: комментарий от aedeph_

Питон падает из-за того, что ты ниасилил xrange.

читаем выше внимательнЕе - речь и дет о 2-м, а не 3-м питоне
во втором питоне это не канает

kto_tama ★★★★★
() автор топика
Ответ на: комментарий от kto_tama 
vadim@aquila:/tmp$ cat 1.py
n=[2, 3, 5, 7, 13, 17, 19, 23, 29]
for i in n:
  s=1
  s = reduce(lambda x, y: x+y , xrange(1, 2**i))
  print s
vadim@aquila:/tmp$ time python2 1.py 
6
28
496
8128
33550336
8589869056
137438691328
35184367894528
144115187807420416

real	6m58.743s
user	6m2.010s
sys	0m0.115s
vadim@aquila:/tmp$
geekless ★★
()
Ответ на: комментарий от geekless

И кстати.

vadim@aquila:/tmp$ time pypy 1.py 
6
28
496
8128
33550336
8589869056
137438691328
35184367894528
144115187807420416

real	0m59.128s
user	0m58.368s
sys	0m0.031s
vadim@aquila:/tmp$
geekless ★★
()

для таких целей хаскель лучше подходит 

algiz:~$ cat tmp.hs
perfect = [2^(p-1) * (2^p - 1) | p <- 2:[n | n <- [3,5..], null [x | x <- [2..(n-1)], mod n x == 0]]]
main = print $ take 30 perfect

algiz:~$ time ./tmp
[6,28,496,8128,2096128,33550336,8589869056,137438691328,35184367894528,144115187807420416,2305843008139952128,9444732965670570950656,2417851639228158837784576,38685626227663735544086528,9903520314282971830448816128,40564819207303336344294875201536,166153499473114483824745506383331328,2658455991569831744654692615953842176,10889035741470030830754200461521744560128,2787593149816327892690784192460327776944128,44601490397061246283066714178813853366747136,182687704666362864775460301858080473799697891328,46768052394588893382517909811217778170473142550528,191561942608236107294793378084303638130997321548169216,12554203470773361527671578846336104669690446551334525075456,3213876088517980551083924184681057554444177758164088967397376,51422017416287688817342786954912132678309582883443383916822528,13164036458569648337239753460458722910223472318386943117783728128,210624583337114373395836055367340540119236532374371439352601378816,53919893334301279589334030174039256154977430310253516431710891278336]

real	0m0.011s
user	0m0.004s
sys	0m0.004s

Aswed ★★★★★
()
Последнее исправление: Aswed (всего исправлений: 1) 
=====6
=====28
=====496
=====8128
Traceback (most recent call last):
  File "<stdin>", line 4, in <module>
MemoryError

ulimit'ы стоят.

beastie ★★★★★
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
← Помогите определить формат данных принятых от сервера
Development
декоратор Python →