 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Integers only (Posted on 2014-03-31) What is the smallest pair (a1,a2) of integers (a1, less than a2) to provide a list of 24 integers using
a recurrent function a(n)=(a(n-1)+a(n-2))/2?

 See The Solution Submitted by Ady TZIDON No Rating Comments: ( Back to comment list | You must be logged in to post comments.) Some questions / Possible solution(s) | Comment 1 of 7

Are negative integers allowed?  If so, what does "smallest pair" of integers mean?

If I assume that a1 and a2 must both be positive integers, then I have a solution of a_1 = 2^22 = 4,194,304 and a_2 = 2^23 = 8,388,608.  I haven't proven that it's optimal but it feels like it might be.  This starting point assures that you can repeatedly sum and divide by two 22 times and still get an integer.

If negative integers are allowed then I assume "smallest" would refer to absolute values (otherwise I could make a_1,a_2 arbitrarily "small" by just starting with larger and larger negative numbers).  In this case we can transform the recurrence relation given in the problem to a_n = 2*a_(n+2) - a_(n+1) and work backwards.  I'd assume the smallest pair a_1,a_2 would occur when a_23,a_24 = (1,0).  Working backwards from there, then:

a_22 = 2(1) - 0 = 2.

a_21 = 2(0) - 2 = -2

a_20 = 2(2) - (-2) = 6

a_19 = 2(-2) - 6 = -10

...

a2 = 1,398,102

a1 = -2,796,202

Again, I haven't proven this is optimal but it feels like it would be, since it results in the smallest ending point.

 Posted by tomarken on 2014-03-31 14:46:35 Please log in:

 Search: Search body:
Forums (0)