CODEWITHSUNDEEP
mathbinary-search
cryptomanic
cryptomanic

Reputation: 6306

nth term of a sequence

I have two sequence:

1.

8 27 64 125 ...

2.

1 2 3 4 5 6 ....

Now take one element from 1 and another from 2 and mutiply them. Repeat this. Arrange the numbers obtained in increasing order.

8 16 24 27 32 40 48 54 56 64 64 ...

How can we efficiently find the n-th number of this new sequence?

Upvotes: 2

Views: 84

Answers (1)

Spektre
Spektre

Reputation: 51845

If there are no duplicate elements in the result then I would use modified Sieves of Eratosthenes to mark all the final series numbers and then create table of the series itself. Here small C++ example:

// globals
const int N0=4;
const int N1=6;
const int N2=N0*N1;
const int M=(N0+2)*(N0+2)*(N0+2)*N1;
int f0(int x) { x+=2; return x*x*x; }   // x = <0,N0)
int f1(int x) { x+=1; return x; }       // x = <0,N1)
int f2[N2],n;                           // x = <0,n )

// locals
int x,y;
BYTE soe[M+1];
AnsiString txt="";

// debug print series
for (txt+="f0(x) = ",x=0;x<N0;x++) { txt+=f0(x); txt+=" "; } txt+="\r\n";
for (txt+="f1(x) = ",x=0;x<N1;x++) { txt+=f1(x); txt+=" "; } txt+="\r\n";

tbeg();
// compute sieve
for (x=0;x<=M;x++) soe[x]=0;
for (x=0;x<N0;x++)
 for (y=0;y<N1;y++)
  soe[f0(x)*f1(y)]=1;
// reorder it to table
for (x=0,n=0;x<=M;x++)
 if (soe[x]) { f2[n]=x; n++; }
tend(); txt+="computed in "+tstr(1)+"\r\n";

// debug print ordered series as function of x ... counting from 0
for (txt+="f2(x) = ",x=0;x<n;x++) { txt+=f2[x]; txt+=" "; } txt+="\r\n";

Form1->mm_log->Lines->Add(txt);

result:

f0(x) = 8 27 64 125 
f1(x) = 1 2 3 4 5 6 
computed in [   0.003 ms]
f2(x) = 8 16 24 27 32 40 48 54 64 81 108 125 128 135 162 192 250 256 320 375 384 500 625 750

Just ignore tbeg(),tend(),tstr() and string Form1->mm_log,txt stuff or rewrite to your platform/IDE. This is not optimized yet and can be improved a lot ... for example you can use single bit per sieve element instead BYTE or even avoid of using the whole sieve table in memory (by clever ordering/partitioning the subresults).

In case duplicates are present in output then you need use sieve as counter of element not just boolean and reconstruct it accordingly.

Upvotes: 1

Related Questions