A339930 - OEIS

%I #11 Dec 27 2020 19:45:20

%S 0,0,0,1,1,1,1,2,1,2,2,2,2,2,3,2,3,2,3,3,2,4,2,4,2,4,3,3,4,3,4,3,3,5,

%T 2,5,2,5,3,4,5,3,5,3,4,4,4,5,3,6,3,5,3,4,6,4,6,4,5,4

%N a(n+1) = a(n-2-a(n)^2) + 1, starting with a(1) = a(2) = a(3) = 0.

%C To obtain the next term, square the current term and add 2, then count back this number and add 1.

%C The sequence cannot repeat. Proof: Assume a finite period. Label an arbitrary term in the period x. Because of the back-referencing definition it follows that x-1 has to be in the period, and by the same argument so does x-2 and x-3, x-4,... until 0. But it is not possible to obtain new 0s since each new term is larger than one already existing term.

%C Every positive integer appears in the sequence.

%C First occurrence of n: 1, 4, 8, 15, 22, 34, 50, 69, 108, 171, 210, 277, 376, 464, 567, 670, 775, 993,...

%C The sequence appears to grow with the cube root of n, which is expected since f(x) = (3*x)^(1/3) satisfies the definition for large x, i.e. lim_{x->oo} f(x+1)-(f(x-2-f(x)^2)+1) = 0.

%C The width of the distribution of terms within a range (n^2,n^2+n) appears to be constant for large n and can be defined as: lim_{n->oo} ( 1/n*Sum_{k=n..2n} ( Max_{i=k^2..k^2+k} a(i) - Min_{i=k^2..k^2+k} a(i) ) ) and evaluates to 7.41... (for n^2 = 5*10^8).

%F a(n) ~ (3*n)^(1/3) (conjectured).

%e a(4) = a(3-2-a(3)^2)+1 = a(1)+1 = 1.

%e a(5) = a(4-2-a(4)^2)+1 = a(1)+1 = 1.

%e a(6) = a(5-2-a(5)^2)+1 = a(2)+1 = 1.

%e a(7) = a(6-2-a(6)^2)+1 = a(3)+1 = 1.

%e a(8) = a(7-2-a(7)^2)+1 = a(4)+1 = 2.

%o (Python)

%o a = [0, 0, 0]

%o for n in range(2, 1000):

%o     a.append(a[n-2-a[n]**2]+1)

%o (C)

%o #include<stdio.h>

%o #include<stdlib.h>

%o int main(void){

%o     int N = 1000;

%o     int *a = (int*)malloc(N*sizeof(int));

%o     a[0] = 0;

%o     a[1] = 0;

%o     a[2] = 0;

%o     for(int n = 2; n < N-1; ++n){

%o         a[n+1] = a[n-2-a[n]*a[n]]+1;

%o     }

%o     free(a);

%o     return 0;

%o }

%Y Analogous sequences: A339929, A339931, A339932.

%Y Cf. A330772, A005206, A002516, A062039.

%K nonn

%O 1,8

%A _Rok Cestnik_, Dec 23 2020