A087165 a(n)=1 when n == 1 (mod 4), otherwise a(n) = a(n - ceiling(n/4)) + 1. Removing all the 1's results in the original sequence with every term incremented by 1.

1, 2, 3, 4, 1, 5, 2, 6, 1, 3, 7, 2, 1, 4, 8, 3, 1, 2, 5, 9, 1, 4, 2, 3, 1, 6, 10, 2, 1, 5, 3, 4, 1, 2, 7, 11, 1, 3, 2, 6, 1, 4, 5, 2, 1, 3, 8, 12, 1, 2, 4, 3, 1, 7, 2, 5, 1, 6, 3, 2, 1, 4, 9, 13, 1, 2, 3, 5, 1, 4, 2, 8, 1, 3, 6, 2, 1, 7, 4, 3, 1, 2, 5, 10, 1, 14, 2, 3, 1, 4, 6, 2, 1, 5, 3, 9, 1, 2, 4, 7, 1, 3, 2

Offset: 1

Author

Paul D. Hanna, Aug 24 2003

Keywords

• nonn
• easy

Comments

Indices of records are given by A087192: a(A087192(n))=n, where A087192(n) = ceiling(A087192(n-1)*4/3).

From Benoit Cloitre, Mar 07 2009: (Start)

To construct the sequence:

Step 1: start from a sequence of 1's, leaving 3 undefined places between 1's, giving 1,(),(),(),1,(),(),(),1,(),(),(),1,(),(),(),1,(),(),(),1,...

Step 2: replace the first undefined place with a 2 and leave 3 undefined places between 2's, giving 1,2,(),(),1,(),2,(),1,(),(),2,1,(),(),(),1,2,(),(),1,...

Step 3: replace the first undefined place with a 3 and leave 3 undefined places between 3's, giving 1,2,3,(),1,(),2,(),1,3,(),2,1,(),(),3,1,2,(),(),1,...

Step 4: replace the first undefined place with a 4 and leave 3 undefined places between 4's, giving 1,2,3,4,1,(),2,(),1,3,(),2,1,4,(),3,1,2,(),(),1,...

Iterating the process indefinitely yields the sequence: 1,2,3,4,1,5,2,6,1,3,7,2,1,4,8,3,1,2,5,9,1,... (End)

Crossrefs

Cf. A001511, A087088, A087192, A244041.

a(n+1) - a(n) = 4*A018902(n-3), n > 2.

Programs

Maple

for n from 1 to 100 do
  if n mod 4 = 1 then A[n]:= 1
  else A[n]:= A[n - ceil(n/4)] + 1
  fi
od:
seq(A[n],n=1..100); # Robert Israel, Aug 05 2014

PARI

a(n)=my(s); while(n>4, if(n%4==1, return(s+1)); n=(n\4*3)+max(n%4 - 1,0); s++); s+n \\ Charles R Greathouse IV, Sep 22 2022

Formula

a(n) = 4 + A244041(4*(n-1)) - A244041(4*n). - Tom Edgar and James Van Alstine, Aug 05 2014

a(4*n) = a(3*n)+1.

a(4*n+1) = 1.

a(4*n+2) = a(3*n+1)+1.

a(4*n+3) = a(3*n+2)+1. - Robert Israel, Aug 05 2014

a(n) < k*log(n) + 4 for n > 1 where k = 1/log(4/3) < 3.5. - Charles R Greathouse IV, Sep 22 2022