A065035 a(n+1) = a(n)^2 + 3*a(n) + 1.

0, 1, 5, 41, 1805, 3263441, 10650056950805, 113423713055421844361000441, 12864938683278671740537145998360961546653259485195805, 165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185441

Offset: 0

Author

Henry Bottomley, Nov 03 2001

Keywords

• easy
• nonn

Comments

a(k) is the optimal competitive ratio of any memoryless algorithm for the weighted k-server problem (Chiplunkar and Vishwanathan). - David Eppstein, Dec 31 2013

This is a divisibility sequence, that is if n divides m then a(n) divides a(m). Cf. A002065. - Peter Bala, Mar 26 2018

Examples

			a(3) = a(2)^2 + 3*a(2) + 1 = 25 + 15 + 1 = 41.
		

Links

• Harry J. Smith, Table of n, a(n) for n = 0..12
• Ashish Chiplunkar and Sundar Vishwanathan, On Randomized Memoryless Algorithms for the Weighted k-server Problem, 54th IEEE Symp. Foundations of Computer Science (FOCS 2013), pp. 11-19; arXiv:1301.0123
• Index entries for sequences of form a(n+1)=a(n)^2 + ...

Crossrefs

Cf. A000058, A002065, A007018, A028387, A060136.

Programs

PARI

a(n)=if(n<1,0,a(n-1)^2+3*a(n-1)+1);

PARI

{ for (n=0, 12, a=if(n, a^2 + 3*a + 1, 0); write("b065035.txt", n, " ", a) ) } \\ Harry J. Smith, Oct 03 2009

Formula

a(n) = A007018(n)-1 = A000058(n)-2 = A060136(3, n) = A028387(a(n-1)). - Michael Somos, Feb 10 2002