Hofstadter Q sequence


 







Q
(
1
)



=
Q
(
2
)
=
1
,




Q
(
n
)



=
Q


(


n
−
Q
(
n
−
1
)


)


+
Q


(


n
−
Q
(
n
−
2
)


)


,

n
>
2.






{\displaystyle {\begin{aligned}Q(1)&=Q(2)=1,\\Q(n)&=Q{\big (}n-Q(n-1){\big )}+Q{\big (}n-Q(n-2){\big )},\quad n>2.\end{aligned}}}




It is defined like the Fibonacci sequence, but whereas the next term in the Fibonacci sequence is the sum of the previous two terms, in the Q sequence the previous two terms tell you how far to go back in the Q sequence to find the two numbers to sum to make the next term of the sequence.



Task

 Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6 
 Confirm and display that the 1000th term is:   502


Optional extra credit
 Count and display how many times a member of the sequence is less than its preceding term for terms up to and including the 100,000th term.
 Ensure that the extra credit solution   safely   handles being initially asked for an nth term where   n   is large.

(This point is to ensure that caching and/or recursion limits, if it is a concern, is correctly handled).




 
class
	APPLICATION
 
create
	make
 
feature
 
	make
			-- Test output of the feature hofstadter_q_sequence.
		local
			count, i: INTEGER
			test: ARRAY [INTEGER]
		do
			io.put_string ("%NFirst ten numbers: %N")
			test := hofstadter_q_sequence (10)
			across
				test as ar
			loop
				io.put_string (ar.item.out + "%T")
			end
			test := hofstadter_q_sequence (100000)
			io.put_string ("1000th:%N")
			io.put_integer (test [1000])
			io.put_string ("%NNumber of Flips:%N")
			from
				i := 2
			until
				i > 100000
			loop
				if test [i] < test [i - 1] then
					count := count + 1
				end
				i := i + 1
			end
			io.put_integer (count)
		end
 
	hofstadter_q_sequence (lim: INTEGER): ARRAY [INTEGER]
			-- Hofstadter Q Sequence up to 'lim'.
		require
			lim_positive: lim > 0
		local
			q: ARRAY [INTEGER]
			i: INTEGER
		do
			create Result.make_filled (1, 1, lim)
			Result [1] := 1
			Result [2] := 1
			from
				i := 3
			until
				i > lim
			loop
				Result [i] := Result [i - Result [i - 1]] + Result [i - Result [i - 2]]
				i := i + 1
			end
		end
 
end
 
 