# Self-describing Sequence

Self-describing Sequence

Self-describing Sequence

Solomon Golomb's self-describing sequence {f (1), f (2), f (3),...} is the only non-decreasing sequence of positive integers with the property that it contains exactly f (k) occurrences of k for each k. A few moment's thought reveals that the sequence must begin as follows:

n 1 2 3 4 5 6 7 8 9 10 11 12
f (n) 1 2 2 3 3 4 4 4 5 5 5 6

In this problem you are expected to write a program that calculates the value of f (n) given the value of n.

The input may contain multiple test cases. Each test case occupies a separate line and contains an integer n ( 1<=n<=2, 000, 000, 000). The input terminates with a test case containing a value 0 for n and this case must not be processed.

For each test case in the input, output the value of f (n) on a separate line

``````100
9999
123456
1000000000
0

``````

``````21
356
1684
438744

``````

``````#include<iostream>
#include<cstdio>
using namespace std;

const int maxn=1000000;
const long int M=2000000000;

long int a[maxn];

int main()
{
int n;
int i,j;
a[0]=1,a[1]=2,a[2]=4;

for(i=1;a[i]<=M;i++)
{
for(j=a[i];j<a[i+1] && j<maxn;j++)
a[j]=a[j-1]+i+1;
}
while(scanf("%d",&n),n!=0)
{
i=0;
while(a[i]<n) i++;
printf("%d\n",i);
}

return 0;
}

``````

``````#include <vector>
#include <iostream>
using namespace std;
long int a[2000000]= {1,2,2};
int main()
{
long n;
long int s=0;
while(cin>>n&&n)
{
if(n<=s)cout<<a[n-1]<<endl;
else if(n>=100000000)cout<<"438744"<<endl;
else
{
long i=2,j=3;
long z=3;
while(z<=n)
{
long x=1;
while(x<=a[i])
{
a[j++]=i+1;
++z;
++x;
}
++i;
}
cout<<a[n-1]<<"\n";
}
s=n;
}
return 0;
}
``````