Zumkeller numbers: Difference between revisions
Content deleted Content added
m →{{header|AppleScript}}: Subset-sum matching handler relabelled, reparametered, and made partly iterative. |
added =={{header|Pascal}}== |
||
Line 2,751: | Line 2,751: | ||
960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 |
960687 999999 1024947 1054053 1072071 1073709 1095633 1108107 |
||
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377</pre> |
1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377</pre> |
||
=={{header|Pascal}}== |
|||
modified [[practical numbers]] |
|||
<lang pascal>program zumkeller; |
|||
{$IFDEF FPC} |
|||
{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
|||
{$ELSE} |
|||
{$APPTYPE CONSOLE} |
|||
{$ENDIF} |
|||
uses |
|||
sysutils |
|||
{$IFDEF WINDOWS} |
|||
,Windows |
|||
{$ENDIF} |
|||
; |
|||
const |
|||
LOW_DIVS = 0; |
|||
HIGH_DIVS = 2048 - 1; |
|||
type |
|||
tdivs = record |
|||
DivsVal: array[LOW_DIVS..HIGH_DIVS] of Uint32; |
|||
DivsMaxIdx, DivsNum, DivsSum: NativeUInt; |
|||
end; |
|||
var |
|||
Divs: tDivs; |
|||
HasSum: array of byte; |
|||
procedure GetDivisors(var Divs: tdivs; n: Uint32); |
|||
//calc all divisors,keep sorted |
|||
var |
|||
i, quot, ug, og: UInt32; |
|||
sum: UInt64; |
|||
begin |
|||
with Divs do |
|||
begin |
|||
DivsNum := n; |
|||
sum := 0; |
|||
ug := 0; |
|||
og := HIGH_DIVS; |
|||
i := 1; |
|||
while i * i < n do |
|||
begin |
|||
quot := n div i; |
|||
if n - quot * i = 0 then |
|||
begin |
|||
DivsVal[og] := quot; |
|||
Divs.DivsVal[ug] := i; |
|||
inc(sum, quot + i); |
|||
dec(og); |
|||
inc(ug); |
|||
end; |
|||
inc(i); |
|||
end; |
|||
if i * i = n then |
|||
begin |
|||
DivsVal[og] := i; |
|||
inc(sum, i); |
|||
dec(og); |
|||
end; |
|||
//move higher divisors down |
|||
while og < high_DIVS do |
|||
begin |
|||
inc(og); |
|||
DivsVal[ug] := DivsVal[og]; |
|||
inc(ug); |
|||
end; |
|||
DivsMaxIdx := ug - 1; |
|||
DivsSum := sum; |
|||
end; //with |
|||
end; |
|||
function isZumKeller(var Divs:TDivs;Middle: NativeInt):boolean; |
|||
//mark sum and than shift by next divisor == add |
|||
//for practical numbers every sum must be marked |
|||
//modified for zumkeller |
|||
var |
|||
hs0,hs1: pByte; |
|||
idx, j, i,maxlimit : NativeInt; |
|||
begin |
|||
hs0 := @HasSum[0]; |
|||
hs0[0] := 1; //empty set |
|||
maxlimit := 0; |
|||
for idx := 0 to Divs.DivsMaxIdx do |
|||
begin |
|||
i := Divs.DivsVal[idx]; |
|||
If i > middle then |
|||
BREAK; |
|||
IF maxlimit >= middle-i then |
|||
Begin |
|||
maxlimit := middle-i; |
|||
if hs0[maxLimit] <> 0 then |
|||
EXIT(true) |
|||
end; |
|||
//next sum |
|||
hs1 := @hs0[i]; |
|||
For j := maxlimit downto 0 do |
|||
hs1[j] := hs0[j]; |
|||
maxlimit += i; |
|||
end; |
|||
result := false; |
|||
end; |
|||
function GetZumKeller(n: Uint32): boolean; |
|||
var |
|||
sum,le: NativeUInt; |
|||
begin |
|||
GetDivisors(Divs, n); |
|||
sum := Divs.DivsSum; |
|||
//sum must be even and n not prime |
|||
if Not(Odd(sum)) then |
|||
Begin |
|||
IF ODD(n) then |
|||
IF sum <2*n then |
|||
EXIT(false); |
|||
sum := sum shr 1; |
|||
le := length(HasSum); |
|||
if le < sum then |
|||
Begin |
|||
le := (sum shr 3+1)shl 3; |
|||
setlength(HasSum,0); |
|||
setlength(HasSum, le); |
|||
end |
|||
else |
|||
fillQWord(HasSum[0],sum shr 3,0); |
|||
result := isZumKeller(Divs,sum); |
|||
end |
|||
else |
|||
result := false; |
|||
end; |
|||
const |
|||
ColCnt = 20; |
|||
MAX = 220; |
|||
var |
|||
n, col, count: NativeInt; |
|||
begin |
|||
setlength(HasSum,8); |
|||
col := ColCnt; |
|||
count := 0; |
|||
n := 1; |
|||
writeln('The first ',MAX,' zumkeller numbers'); |
|||
repeat |
|||
if GetZumKeller(n) then |
|||
begin |
|||
write(n:4); |
|||
inc(count); |
|||
dec(col); |
|||
if col = 0 then |
|||
begin |
|||
writeln; |
|||
col := ColCnt; |
|||
end; |
|||
end; |
|||
inc(n); |
|||
until count = MAX; |
|||
writeln; |
|||
writeln('The first odd 40 zumkeller numbers'); |
|||
n := 1; |
|||
count :=0; |
|||
col := 10; |
|||
repeat |
|||
if GetZumKeller(n) then |
|||
begin |
|||
write(n:8); |
|||
inc(count); |
|||
dec(col); |
|||
if col = 0 then |
|||
begin |
|||
writeln; |
|||
col := 10; |
|||
end; |
|||
end; |
|||
inc(n,2); |
|||
until count = 40; |
|||
writeln; |
|||
n := 1; |
|||
count :=0; |
|||
col := 10; |
|||
writeln('The first odd 40 zumkeller numbers not ending in 5'); |
|||
repeat |
|||
if GetZumKeller(n) then |
|||
begin |
|||
write(n:8); |
|||
inc(count); |
|||
dec(col); |
|||
if col = 0 then |
|||
begin |
|||
writeln; |
|||
col := 10; |
|||
end; |
|||
end; |
|||
inc(n,2); |
|||
if n MOD 5 = 0 then |
|||
inc(n,2); |
|||
until count = 40; |
|||
setlength(HasSum, 0); |
|||
{$IFNDEF UNIX} readln; {$ENDIF} |
|||
end.</lang> |
|||
{{out}} |
|||
<pre>TIO.RUN |
|||
The first 220 zumkeller numbers |
|||
6 12 20 24 28 30 40 42 48 54 56 60 66 70 78 80 84 88 90 96 |
|||
102 104 108 112 114 120 126 132 138 140 150 156 160 168 174 176 180 186 192 198 |
|||
204 208 210 216 220 222 224 228 234 240 246 252 258 260 264 270 272 276 280 282 |
|||
294 300 304 306 308 312 318 320 330 336 340 342 348 350 352 354 360 364 366 368 |
|||
372 378 380 384 390 396 402 408 414 416 420 426 432 438 440 444 448 456 460 462 |
|||
464 468 474 476 480 486 490 492 496 498 500 504 510 516 520 522 528 532 534 540 |
|||
544 546 550 552 558 560 564 570 572 580 582 588 594 600 606 608 612 616 618 620 |
|||
624 630 636 640 642 644 650 654 660 666 672 678 680 684 690 696 700 702 704 708 |
|||
714 720 726 728 732 736 740 744 750 756 760 762 768 770 780 786 792 798 804 810 |
|||
812 816 820 822 828 832 834 836 840 852 858 860 864 868 870 876 880 888 894 896 |
|||
906 910 912 918 920 924 928 930 936 940 942 945 948 952 960 966 972 978 980 984 |
|||
The first odd 40 zumkeller numbers |
|||
945 1575 2205 2835 3465 4095 4725 5355 5775 5985 |
|||
6435 6615 6825 7245 7425 7875 8085 8415 8505 8925 |
|||
9135 9555 9765 10395 11655 12285 12705 12915 13545 14175 |
|||
14805 15015 15435 16065 16695 17325 17955 18585 19215 19305 |
|||
The first odd 40 zumkeller numbers not ending in 5 |
|||
81081 171171 189189 207207 223839 243243 261261 279279 297297 351351 |
|||
459459 513513 567567 621621 671517 729729 742203 783783 793611 812889 |
|||
837837 891891 908523 960687 999999 1024947 1054053 1072071 1073709 1095633 |
|||
1108107 1145529 1162161 1198197 1224531 1270269 1307691 1324323 1378377 1432431 |
|||
Real time: 2.177 s CPU share: 99.18 % |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |