Rosetta Code

Ludic numbers: Difference between revisions

Page Discussion

Ludic numbers (view source)

Revision as of 10:51, 3 February 2016

466 bytes added ,  8 years ago
m
→‎{{header|Pascal}}: speedup 4.4s -> 3 s. C-version is still at 1.25s for n= 100'000
({{header|Pascal}})
m (→‎{{header|Pascal}}: speedup 4.4s -> 3 s. C-version is still at 1.25s for n= 100'000)
Line 1,328:
=={{header|Pascal}}==
Inspired by "rotors" of perl 6 .
Runtime nearly quadratic: maxLudicCnt = 10000 -> 0.0403 s =>maxLudicCnt= 100000 -> 4.883 s
There is much space for improvement.Analog to prime wheels 2,3 -> +2+4,+2+4,+2+4 so only 2 of 6 numbers are to check.
The rotors can be grouped/listed together in order of their remaining cnt values. <10, <100, < 1000,< 10000 to reduce the checks of a special rotor.
<lang pascal>program lucid;
{$IFDEF FPC}
{$MODE objFPC} // useful for x64
{$ENDIF}
 
const
//66164 -> last < 1000*1000;
maxLudicCnt = 2005; //must be > 1
type
 
tDelta = record
dNum : LongInt;,
dCnt : LongInt;
end;
 
tpDelta = ^tDelta;
tLudicList = array of tDelta;
 
tArrdelta =array[0..0] of tDelta;
procedure getLudic(var Ll:tLudicList);▼
tpLl = ^tArrdelta;
 
function isLudic(plL:tpLl;maxIdx:nativeInt):boolean;
var
i,
n,LudicCnt,i : NativeUint;▼
isLucidcn : booleanNativeInt;
Begin▼
//check if n is 'hit' by a prior ludic number▼
For i := 1 to LudicCntmaxIdx do▼
with LlplL^[i] do▼
Begin▼
//Mask read modify write reread
//dec(dCnt);IF dCnt= 0▼
cn := enddCnt;▼
IF dCntcn = 01 then▼
end;Begin▼
dcnt := dNum;▼
isLucidisLudic := false;▼
BREAKEXIT;▼
end;
isLucid dcnt := truecn-1;▼
n := 1end;▼
isLudic := true;
end;
 
▲procedure getLudicCreateLudicList(var Ll:tLudicList);
var
plL : tpLl;
▲ n,LudicCnt,i : NativeUint;
begin
▲ n := 1;
// special case 1
n := 1;
Ll[0].dNum := 1;
 
plL := @Ll[0];
LudicCnt := 0;
 
repeat
inc(n);
If isLudic(plL,LudicCnt ) then
▲ isLucid := true;
▲ //check if n is 'hit' by a prior ludic number
▲ For i := 1 to LudicCnt do
▲ with Ll[i] do
▲ Begin
▲ dec(dCnt);
▲ IF dCnt = 0 then
▲ Begin
▲ dcnt := dNum;
▲ isLucid := false;
▲ BREAK
▲ end;
▲ end;
// a new ludic number found?
If isLucid then▼
Begin
inc(LudicCnt);
with LlplL^[LudicCnt] do
Begin
dNum := n;
dCnt := n;
end;
IF cnt(LudicCnt >= lengthHigh(LlLL)) then▼
BREAK;
end;
until LudicCnt >= High(LL)false;
end;
 
Line 1,396 ⟶ 1,413:
var
i,
chk : NativeIntNativeUint;
 
Begin
// special case 1,3,7
writeln('Ludic triples below ',max);
write('(',ll[0].dNum,',',ll[2].dNum,',',ll[4].dNum,') ');
 
For i := 1 to High(Ll) do
Begin
Line 1,414 ⟶ 1,431:
end;
 
procedure LastLucid(var Ll:tLudicList;start,cnt: NativeUint);
var
limit,i : NativeUint;
Begin
dec(start);
▲ IF cnt >= length(Ll) then
cntlimit := Highhigh(Ll);
▲ IF cnt If>= isLucidlimit then
i:= length(Ll);
cnt := limit;
writeln(i-cnt,'.th to ',i,'.th ludic number');▼
if start+cnt >limit then
For i := High(Ll)-cnt+1 to High(Ll)-1 do▼
start := limit-cnt;
write(Ll[i].dNum,',');▼
writeln(Ll[High(Ll)]Start+1,'.dNumth to ',Start+cnt+1,'.th ludic number');
▲ For i := High(Ll)-cnt+10 to High(Ll)cnt-1 do
▲ write(Ll[i+start].dNum,',');
writeln(Ll[start+cnt].dNum);
writeln;
end;
Line 1,430 ⟶ 1,450:
function CountLudic(var Ll:tLudicList;Limit: NativeUint):NativeUint;
var
i,res : NativeUint;
Begin
resultres := 0;
For i := 0 to High(Ll) do begin
IF Ll[i].dnum <= Limit then
inc(resultres)
else
BREAK;
CountLudic:= res;
end;
 
Line 1,443 ⟶ 1,464:
var
LudicList : tLudicList;
 
BEGIN
setlength(LudicList,maxLudicCnt);
getLudicCreateLudicList(LudicList);
firstN(LudicList,25);
writeln('There are ',CountLudic(LudicList,1000),' ludic numbers below 1000');
LastLucid(LudicList,2000,5);
LastLucid(LudicList,maxLudicCnt,5);
triples(LudicList,250);//all-> (LudicList,LudicList[High(LudicList)].dNum);
END.
{
(*
1,2,3,5,7,11,13,17,23,25,29,37,41,43,47,53,61,67,71,77,83,89,91,97,107
//maxLudicCnt = 100000
There are 142 ludic numbers below 1000
...
999952000.th to 1000002005.th ludic numbersnumber
21475,21481,21487,21493,21503,21511
1561291,1561301,1561307,1561313,1561333▼
 
*)
▲ writeln(i-cnt,'99995.th to ',i,'100000.th ludic number');
</lang>
▲1561243,1561291,1561301,1561307,1561313,1561333
 
Ludic triples below 250
(1,3,7) (5,7,11) (11,13,17) (23,25,29) (41,43,47) (173,175,179) (221,223,227) (233,235,239)
 
real 0m2.921s}</lang>
{{Output}}
<pre>
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/242729"