Perfect numbers: Difference between revisions

Line 3,050:

=={{header|Phix}}==

=== naive/native ===

function is_perfect(integer n)

return sum(factors(n,-1))=n

function is_perfect(integer n)

end function

return sum(factors(n,-1))=n

end function

for i=2 to 100000 do

if is_perfect(i) then ?i end if

for i=2 to 100000 do

end for

if is_perfect(i) then ?i end if

end for

</syntaxhighlight>

<pre>

Line 3,068:

Line 3,070:

=== gmp version ===

~~<!--~~<syntaxhighlight lang="phix"~~>(phixonline)--~~>

~~~~with~~ ~~javascript_semantics~~~~

with javascript_semantics

~~~~-- demo\rosetta\Perfect_numbers.exw (includes native ~~version~~ ~~above~~)~~~~

-- demo\rosetta\Perfect_numbers.exw (includes native and cheat versions)

include mpfr.e

include mpfr.e

atom t0 = time(), t1 = t0+1

mpz n = mpz_init(), p = mpz_init()

integer maxprime = 4423, -- 19937 (rather slow)

for i=2 to 159 do

lim = length(get_primes_le(maxprime))

mpz_ui_pow_ui(n, 2, i)

mpz n = mpz_init(), m = mpz_init()

mpz_sub_ui(n, n, 1)

for i=1 to lim do

if mpz_prime(n) then

integer p = get_prime(i)

mpz_ui_pow_ui(p,2,i-1)

mpz_ui_pow_ui(n, 2, p)

mpz_mul(n,n,p)

mpz_sub_ui(n, n, 1)

printf(1, "%d %s\n",{i,mpz_get_str(n,comma_fill:=true)})

if mpz_prime(n) then

end if

mpz_ui_pow_ui(m, 2, p-1)

end for

mpz_mul(n, n, m)

n = mpz_free(n)

string ns = mpz_get_short_str(n,comma_fill:=true),

et = elapsed_short(time()-t0,5,"(%s)")

printf(1, "%d %s %s\n",{p,ns,et})

elsif time()>t1 then

progress("%d/%d (%.1f%%)\r",{p,maxprime,i/lim*100})

t1 = time()+1

end if

end for

?elapsed(time()-t0)

</syntaxhighlight>

<pre>

Line 3,095:

Line 3,106:

31 2,305,843,008,139,952,128

61 2,658,455,991,569,831,744,654,692,615,953,842,176

89 191,561,942,608,236,~~107,294,793,378,084,303,638,130~~,997,321,548,169,216

89 191,561,942,608,236,...,997,321,548,169,216 (54 digits)

107 13,164,036,458,569,~~648,337,239,753,460,458,722,910,223,472,318,386~~,943,117,783,728,128

107 13,164,036,458,569,6...,943,117,783,728,128 (65 digits)

127 14,474,011,154,664,~~524,427,946,373,126,085,988,481,573,677,491,474,835,889,066,354~~,349,131,199,152,128

127 14,474,011,154,664,5...,349,131,199,152,128 (77 digits)

521 23,562,723,457,267,3...,492,160,555,646,976 (314 digits)

607 141,053,783,706,712,...,570,759,537,328,128 (366 digits)

1279 54,162,526,284,365,8...,345,764,984,291,328 (770 digits)

2203 1,089,258,355,057,82...,580,834,453,782,528 (1,327 digits)

2281 99,497,054,337,086,4...,375,675,139,915,776 (1,373 digits)

3217 33,570,832,131,986,7...,888,332,628,525,056 (1,937 digits) (9s)

4253 18,201,749,040,140,4...,848,437,133,377,536 (2,561 digits) (24s)

4423 40,767,271,711,094,4...,020,642,912,534,528 (2,663 digits) (28s)

"28.4s"

</pre>

Beyond that it gets rather slow:

<pre>

9689 11,434,731,753,038,6...,982,558,429,577,216 (5,834 digits) (6:28)

9941 598,885,496,387,336,...,478,324,073,496,576 (5,985 digits) (7:31)

11213 3,959,613,212,817,94...,255,702,691,086,336 (6,751 digits) (11:32)

19937 931,144,559,095,633,...,434,790,271,942,656 (12,003 digits) (1:22:32)

</pre>

=== cheating ===

include mpfr.e

atom t0 = time(), t1 = t0+1

mpz n = mpz_init(), m = mpz_init()

sequence validp = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607,

1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213,

19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091,

756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593,

13466917, 20996011, 24036583, 25964951, 30402457, 32582657,

37156667, 42643801, 43112609, 57885161}

if platform()=JS then validp = validp[1..35] end if -- (keep it under 5s)

for p in validp do

mpz_ui_pow_ui(n, 2, p)

mpz_sub_ui(n, n, 1)

mpz_ui_pow_ui(m, 2, p-1)

mpz_mul(n, n, m)

string ns = mpz_get_short_str(n,comma_fill:=true),

et = elapsed_short(time()-t0,5,"(%s)")

printf(1, "%d %s %s\n",{p,ns,et})

end for

?elapsed(time()-t0)

</syntaxhighlight>

<pre>

2 6

3 28

5 496

7 8,128

13 33,550,336

17 8,589,869,056

19 137,438,691,328

31 2,305,843,008,139,952,128

61 2,658,455,991,569,831,744,654,692,615,953,842,176

89 191,561,942,608,236,...,997,321,548,169,216 (54 digits)

107 13,164,036,458,569,6...,943,117,783,728,128 (65 digits)

127 14,474,011,154,664,5...,349,131,199,152,128 (77 digits)

521 23,562,723,457,267,3...,492,160,555,646,976 (314 digits)

607 141,053,783,706,712,...,570,759,537,328,128 (366 digits)

1279 54,162,526,284,365,8...,345,764,984,291,328 (770 digits)

2203 1,089,258,355,057,82...,580,834,453,782,528 (1,327 digits)

2281 99,497,054,337,086,4...,375,675,139,915,776 (1,373 digits)

3217 33,570,832,131,986,7...,888,332,628,525,056 (1,937 digits)

4253 18,201,749,040,140,4...,848,437,133,377,536 (2,561 digits)

4423 40,767,271,711,094,4...,020,642,912,534,528 (2,663 digits)

9689 11,434,731,753,038,6...,982,558,429,577,216 (5,834 digits)

9941 598,885,496,387,336,...,478,324,073,496,576 (5,985 digits)

11213 3,959,613,212,817,94...,255,702,691,086,336 (6,751 digits)

19937 931,144,559,095,633,...,434,790,271,942,656 (12,003 digits)

21701 1,006,564,970,546,40...,865,255,141,605,376 (13,066 digits)

23209 81,153,776,582,351,0...,048,603,941,666,816 (13,973 digits)

44497 365,093,519,915,713,...,965,353,031,827,456 (26,790 digits)

86243 144,145,836,177,303,...,480,957,360,406,528 (51,924 digits)

110503 13,620,458,213,388,4...,255,233,603,862,528 (66,530 digits)

132049 13,145,129,545,436,9...,438,491,774,550,016 (79,502 digits)

216091 27,832,745,922,032,7...,263,416,840,880,128 (130,100 digits)

756839 15,161,657,022,027,0...,971,600,565,731,328 (455,663 digits)

859433 83,848,822,675,015,7...,651,540,416,167,936 (517,430 digits)

1257787 849,732,889,343,651,...,394,028,118,704,128 (757,263 digits)

1398269 331,882,354,881,177,...,668,017,723,375,616 (841,842 digits)

2976221 194,276,425,328,791,...,106,724,174,462,976 (1,791,864 digits)

3021377 811,686,848,628,049,...,147,573,022,457,856 (1,819,050 digits)

6972593 9,551,760,305,212,09...,914,475,123,572,736 (4,197,919 digits)

13466917 42,776,415,902,185,6...,230,460,863,021,056 (8,107,892 digits)

20996011 7,935,089,093,651,70...,903,578,206,896,128 (12,640,858 digits)

24036583 44,823,302,617,990,8...,680,460,572,950,528 (14,471,465 digits) (5s)

25964951 7,462,098,419,004,44...,245,874,791,088,128 (15,632,458 digits) (8s)

30402457 49,743,776,545,907,0...,934,536,164,704,256 (18,304,103 digits) (10s)

32582657 77,594,685,533,649,8...,428,476,577,120,256 (19,616,714 digits) (13s)

37156667 20,453,422,553,410,5...,147,975,074,480,128 (22,370,543 digits) (16s)

42643801 1,442,850,579,600,99...,314,837,377,253,376 (25,674,127 digits) (20s)

43112609 50,076,715,684,982,3...,909,221,145,378,816 (25,956,377 digits) (24s)

57885161 169,296,395,301,618,...,179,626,270,130,176 (34,850,340 digits) (29s)

"29.4s"

</pre>