All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers > Sequences
Integers only (Posted on 2014-03-31) Difficulty: 3 of 5
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.)
Hints/Tips 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:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (9)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information