Mian-Chowla sequence: Difference between revisions

Content added Content deleted
(Added Kotlin)
m (→‎{{header|Pascal}}: small improvement, known where to insert.Show runtime behavier of this implementation)
Line 803: Line 803:
{{works with|Free Pascal}}
{{works with|Free Pascal}}
keep sum of all sorted.Memorizing the compare positions speeds up.
keep sum of all sorted.Memorizing the compare positions speeds up.
<BR>
10 min for n = 5818 1998652370. The cost of inserting 5818 values into sum_all array takes about 9 seconds.
Calculating runtime to expect.
That is not relevant.
<pre>
n-> 2x n ~>
average distance between d = mian[n]-mian[n-1] d ~ 4x d
runtime t-> >10x t. ->
n mian[n] avg dist runtime
2700 225432491 195419 43411 ms
5400 1613654038 766839 471468 ms
</pre>
So calculating mian[25000] = mian[5940*(2**2,0733)]
runtime minimum > 10.86**2.0733 *471.5s = 66251 s and round about 2.5 Gbyte for Uint64.
One or two days should be enough.
<lang pascal>program MianChowla;
<lang pascal>program MianChowla;
//compiling with /usr/lib/fpc/3.2.0/ppcx64.2 -MDelphi -O4 -al "%f"
{$CODEALIGN proc=8,loop=4 }
uses
sysutils;
const
const
maxCnt = 100;
deltaK = 100;
maxCnt = 1000;
{
deltaK = 540;
maxCnt = (5966 DIV deltaK)*deltaK;
*}
type
type
tElem = Uint32;
tElem = Uint32;
tpElem = ^tElem;
tpElem = pUint32;
t_n = array[0..maxCnt+1] of tElem;
t_n = array[0..maxCnt+1] of tElem;
t_n_sum_all = array[0..(maxCnt+1)*(maxCnt+2) DIV 2] of tElem;
t_n_sum_all = array[0..(maxCnt+1)*(maxCnt+2) DIV 2] of tElem;


var
var
n_LastPos,
n : t_n;

n_sum_all : t_n_sum_all;
n_sum_all : t_n_sum_all;
n,
n_LastPos : t_n; //memorize compare positions :-)


maxIdx,
maxIdx,
Line 832: Line 853:
max_SumIdx := 1;
max_SumIdx := 1;
n_sum_all[max_SumIdx] := 2*maxN;
n_sum_all[max_SumIdx] := 2*maxN;

For i := 1 to maxCnt do
For i := 0 to maxCnt do
n_LastPos[i] := 1;
n_LastPos[i] := 1;
end;
end;


procedure InsertNew_sum(NewValue:NativeUint);
procedure InsertNew_sum(NewValue:NativeUint);
//insertionsort
var
var
pElem :tpElem;
pElem :tpElem;
oldIdx,newIdx,nextValue : nativeInt;
InsIdx,chkIdx,oldIdx,newIdx : nativeInt;
Begin
Begin
write(#13,MaxIdx:10,NewValue:10);
newIdx := maxIdx;
newIdx := maxIdx;
oldIdx := max_SumIdx;
oldIdx := max_SumIdx;
Line 849: Line 871:
//extend sum_
//extend sum_
inc(max_SumIdx,maxIdx);
inc(max_SumIdx,maxIdx);

//heighest value already known
//heighest value already known
InsIdx := max_SumIdx;
n_sum_all[max_SumIdx] := 2*NewValue;
n_sum_all[InsIdx] := 2*NewValue;

//stop mark
pElem := @n_sum_all[max_SumIdx-1];
n_sum_all[InsIdx+1] := High(tElem);
nextValue := NewValue+n[newIdx];
pElem := @n_sum_all[0];
dec(InsIdx);
//n_LastPos[newIdx]+newIdx-1 == InsIdx
repeat
repeat
//move old bigger values
while n_sum_all[oldIdx] > nextValue do
chkIdx := n_LastPos[newIdx]+newIdx-1;
while InsIdx > chkIdx do
Begin
Begin
pElem^ := n_sum_all[oldIdx];
pElem[InsIdx] := pElem[oldIdx];
dec(InsIdx);
dec(oldIdx);
dec(oldIdx);
dec(pElem);
end;
end;
pElem^ := nextValue;
//insert new value
dec(pElem);
pElem[InsIdx] := NewValue+n[newIdx];
dec(InsIdx);
dec(newIdx);
dec(newIdx);
//all inserted
IF newIdx = 0 then
BREAK;
until newIdx <= 0;
//new minimum search position one behind, oldidx is one to small
nextValue := NewValue+n[newIdx];
inc(oldidx,2);
until newIdx < 0;
For newIdx := 1 to maxIdx do
n_LastPos[newIdx] := oldIdx;
end;
end;

procedure FindNew;
procedure FindNew;
var
var
pSumAll,pn : tpElem;
i,LastCheckPos,Ofs,newVal : NativeUint;
i,LastCheckPos,newValue,newSum : NativeUint;
TestRes : boolean;
TestRes : boolean;
begin
begin
//start value = last inserted value
ofs := n[maxIdx]+1;
For i := 1 to maxIdx+1 do
newValue := n[maxIdx];
n_LastPos[i] := 1;
pSumAll := @n_sum_all[0];
pn := @n[0];
repeat
repeat
LastCheckPos := 1;
//try next number
inc(newValue);
LastCheckPos := n_LastPos[1];
i := 1;
i := 1;
For i := 1 to maxIdx do
//check if sum = new is already n all_sum
Begin
repeat
newVal := ofs+n[i];
newSum := newValue+pn[i];
IF LastCheckPos < n_LastPos[i] then
IF LastCheckPos < n_LastPos[i] then
LastCheckPos := n_LastPos[i];
LastCheckPos := n_LastPos[i];
while n_sum_all[LastCheckPos] < newVal do
while pSumAll[LastCheckPos] < newSum do
Begin
inc(LastCheckPos);
inc(LastCheckPos);
if LastCheckPos >= max_SumIdx then
//memorize LastCheckPos;
BREAK;
n_LastPos[i] := LastCheckPos;
TestRes:= pSumAll[LastCheckPos] = newSum;
end;
TestRes:= n_sum_all[LastCheckPos] = newVal;
IF TestRes then
IF TestRes then
BREAK;
BREAK;
//memorize LastCheckPos;
inc(i);
until i>maxIdx;
n_LastPos[i] := LastCheckPos-1;
end;
//found?
//found?
If not(TestRes) then
If not(TestRes) then
BREAK;
BREAK;
inc(ofs);
until false;
until false;
InsertNew_sum(ofs);
InsertNew_sum(newValue);
end;
end;


var
var
i : NativeInt;
T1,T0: Int64;
i,k : NativeInt;

procedure Out_num(k:NativeInt);
Begin
T1 := GetTickCount64;
// k n[k] average dist last deltak total time
writeln(k:6,n[k]:12,(n[k]-n[k-deltaK+1]) DIV deltaK:8,T1-T0:8,' ms');
end;

BEGIN
BEGIN
writeln('Allocated memory ',2*SizeOf(t_n)+Sizeof(t_n_sum_all));
T0 := GetTickCount64;
while t0 = GetTickCount64 do;
T0 := GetTickCount64;
Init;
Init;

For i := 1 to maxCnt do
FindNew;
k := deltaK;
i := 1;
repeat
repeat
FindNew;
inc(i);
until i=k;
Out_num(k);
k := k+deltaK;
until k>maxCnt;
writeln;
writeln(#13,'The first 30 terms of the Mian-Chowla sequence are');
writeln(#13,'The first 30 terms of the Mian-Chowla sequence are');
For i := 1 to 30 do
For i := 1 to 30 do
Line 918: Line 969:
writeln;
writeln;
writeln;
writeln;
writeln('The terms 90 - 100 of the Mian-Chowla sequence are');
writeln('The terms 91 - 100 of the Mian-Chowla sequence are');
For i := 90 to 100 do
For i := 91 to 100 do
write(n[i],' ');
write(n[i],' ');
writeln;
writeln;
END.
END.
{#####
{https://oeis.org/A005282/b005282.txt
deltaK = 540;
*
maxCnt = (5966 DIV deltaK)*deltaK;
5816 1998326307
Allocated memory 70650384
5817 1998387406
540 2574622 4767 234 ms
5818 1998652370
1080 17315247 27269 2084 ms
*
1620 53808559 67542 7876 ms
...
2160 119743492 121877 20367 ms
5818 1998652370
2700 225432491 195419 43411 ms
3240 377659559 281283 80801 ms
3780 585851493 384664 137472 ms
4320 853722843 494787 217026 ms
4860 1198603744 637443 328136 ms
5400 1613654038 766839 471468 ms
5940 2124053407 944624 659681 ms


real 9m55,050s
real 10m59,682s
}
</lang>
</lang>
{{Out}}
{{Out}}
<pre>Allocated memory 2014024
<pre>The first 30 terms of the Mian-Chowla sequence are
100 27219 272 0.002 s
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312
200 172922 1443 0.011 s
300 514644 3404 0.037 s
400 1144080 6197 0.090 s
500 2085045 9398 0.179 s
600 3375910 12689 0.311 s
700 5253584 18705 0.520 s
800 7600544 23438 0.801 s
900 10441056 28339 1.160 s
1000 14018951 35611 1.640 s
The first 30 terms of the Mian-Chowla sequence are
1 2 4 8 13 21 31 45 66 81 97 123 148 182 204 252 290 361 401 475 565 593 662 775 822 916 970 1016 1159 1312


The terms 90 - 100 of the Mian-Chowla sequence are
The terms 91 - 100 of the Mian-Chowla sequence are
21948 22526 23291 23564 23881 24596 24768 25631 26037 26255 27219
22526 23291 23564 23881 24596 24768 25631 26037 26255 27219</pre>

real 0m0,002s
</pre>


=={{header|Perl}}==
=={{header|Perl}}==
Retrieved from "https://rosettacode.org/wiki/Mian-Chowla_sequence"