Hofstadter Q sequence: Difference between revisions
(→Tcl: Added implementation) |
|||
Line 87: | Line 87: | ||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
tmp = q1(100000) |
tmp = q1(100000) |
||
print("Q(i+1) < Q(i) for i [1.. |
print("Q(i+1) < Q(i) for i [1..100000] is true %i times." % |
||
sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang> |
sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang> |
||
Line 94: | Line 94: | ||
Q(1000) = 502 |
Q(1000) = 502 |
||
Q(i+1) < Q(i) for i [1..10000] is true 49798 times.</pre> |
Q(i+1) < Q(i) for i [1..10000] is true 49798 times.</pre> |
||
===Alternative=== |
|||
<lang python>def q(n): |
|||
if n < len(q.seq): return q.seq[n] |
|||
while n > len(q.seq): q(len(q.seq)) |
|||
ans = q.seq[n - q.seq[n - 1]] + q.seq[n - q.seq[n - 2]] |
|||
q.seq.append(ans) |
|||
return ans |
|||
q.seq = [None, 1, 1] |
|||
print("Q(n) for n = [1..10] is:", [q(i) for i in range(1, 11)]) |
|||
print("Q(1000) =", q(1000)) |
|||
qq = [q(i) for i in range(1, 100001)] |
|||
print("Q(i+1) < Q(i) for i [1..100000] is true %i times." % |
|||
sum(k1 < k0 for k0, k1 in zip(qq[1:], qq[2:])))</lang> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |
Revision as of 13:55, 23 October 2011
The Hofstadter Q sequence is defined as:
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 1000'th term is: 502
- Optional extra credit
- Count and display how many times a member of the sequence is less than its preceeding term for terms up to and including the 100,000'th term.
Common Lisp
<lang lisp>(defparameter *mm* (make-hash-table :test #'equal))
- generic memoization macro
(defmacro defun-memoize (f (&rest args) &body body)
(defmacro hash () `(gethash (cons ',f (list ,@args)) *mm*)) (let ((h (gensym))) `(defun ,f (,@args) (let ((,h (hash)))
(if ,h ,h (setf (hash) (progn ,@body)))))))
- def q
(defun-memoize q (n)
(if (<= n 2) 1 (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))
- test
(format t "First of Q: ~a~%Q(1000): ~a~%Bumps up to 100000: ~a~%" (loop for i from 1 to 10 collect (q i)) (q 1000) (loop with c = 0 with last-q = (q 1) for i from 2 to 100000 do (let ((next-q (q i))) (if (< next-q last-q) (incf c)) (setf last-q next-q)) finally (return c)))</lang>output<lang>First of Q: (1 1 2 3 3 4 5 5 6 6) Q(1000): 502 Bumps up to 100000: 49798</lang>
Python
<lang python>def q(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return q.seq[n] except IndexError: ans = q(n - q(n - 1)) + q(n - q(n - 2)) q.seq.append(ans) return ans
q.seq = [None, 1, 1]
if __name__ == '__main__':
first10 = [q(i) for i in range(1,11)] assert first10 == [1, 1, 2, 3, 3, 4, 5, 5, 6, 6], "Q() value error(s)" print("Q(n) for n = [1..10] is:", ', '.join(str(i) for i in first10)) assert q(1000) == 502, "Q(1000) value error" print("Q(1000) =", q(1000))</lang>
- Extra credit
If you try and initially compute larger values of n then you tend to hit the Python recursion limit.
The function q1 gets around this by calling function q to extend the Q series in increments below the recursion limit.
The following code is to be concatenated to the code above: <lang python>from sys import getrecursionlimit
def q1(n):
if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1") try: return q.seq[n] except IndexError: len_q, rlimit = len(q.seq), getrecursionlimit() if (n - len_q) > (rlimit // 5): for i in range(len_q, n, rlimit // 5): q(i) ans = q(n - q(n - 1)) + q(n - q(n - 2)) q.seq.append(ans) return ans
if __name__ == '__main__':
tmp = q1(100000) print("Q(i+1) < Q(i) for i [1..100000] is true %i times." % sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang>
- Combined output
Q(n) for n = [1..10] is: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6 Q(1000) = 502 Q(i+1) < Q(i) for i [1..10000] is true 49798 times.
Alternative
<lang python>def q(n):
if n < len(q.seq): return q.seq[n] while n > len(q.seq): q(len(q.seq))
ans = q.seq[n - q.seq[n - 1]] + q.seq[n - q.seq[n - 2]] q.seq.append(ans) return ans
q.seq = [None, 1, 1]
print("Q(n) for n = [1..10] is:", [q(i) for i in range(1, 11)]) print("Q(1000) =", q(1000)) qq = [q(i) for i in range(1, 100001)] print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %
sum(k1 < k0 for k0, k1 in zip(qq[1:], qq[2:])))</lang>
Tcl
<lang tcl>package require Tcl 8.5
- Index 0 is not used, but putting it in makes the code a bit shorter
set tcl::mathfunc::Qcache {Q:-> 1 1} proc tcl::mathfunc::Q {n} {
variable Qcache if {$n >= [llength $Qcache]} {
lappend Qcache [expr {Q($n - Q($n-1)) + Q($n - Q($n-2))}]
} return [lindex $Qcache $n]
}
- Demonstration code
for {set i 1} {$i <= 10} {incr i} {
puts "Q($i) == [expr {Q($i)}]"
}
- This runs very close to recursion limit...
puts "Q(1000) == [expr Q(1000)]"
- This code is OK, because the calculations are done step by step
set q [expr Q(1)] for {set i 2} {$i <= 100000} {incr i} {
incr count [expr {$q > [set q [expr {Q($i)}]]}]
} puts "Q(i)<Q(i-1) for i \[2..100000\] is true $count times"</lang> Output:
Q(1) == 1 Q(2) == 1 Q(3) == 2 Q(4) == 3 Q(5) == 3 Q(6) == 4 Q(7) == 5 Q(8) == 5 Q(9) == 6 Q(10) == 6 Q(1000) == 502 Q(i)<Q(i-1) for i [2..100000] is true 49798 times