Hofstadter Q sequence: Difference between revisions
→{{header|jq}}: faster implementation of flips(n)
(→{{header|jq}}: omit parenthetical remark) |
(→{{header|jq}}: faster implementation of flips(n)) |
||
Line 970:
=={{header|jq}}==
For the tasks related to evaluating Q(n) directy, a recursive implementation is used, firstly because the task requirements refer to "recursion limits", and secondly to demonstrate one way to handle a cache in a functional language. To count the number of inversions, a non-recursive approach is used as it is faster and scales linearly.
For simplicity, we also define Q(0) = 1, so that the defining
formula also holds for n == 2, and so that we can cache Q(n) at the
n-th position of an array with index origin 0.
<lang jq>
def Q(n):▼
n as $n▼
| (if . == null then [1,1,1] else . end) as $q▼
| if $q[$n] != null then $q▼
else ▼
$q | Q($n-1) as $q1▼
| $q1 | Q($n-2) as $q2▼
| $q2 | Q($n - $q2[$n - 1]) as $q3 # Q(n - Q(n-1))▼
| $q3 | Q($n - $q3[$n - 2]) as $q4 # Q(n - Q(n-2))▼
| ($q4[$n - $q4[$n-1]] + $q4[$n - $q4[$n -2]]) as $ans▼
| $q4 | setpath( [$n]; $ans)▼
end ;▼
# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))
def Q:
def Q: . as $n | null | Q($n) | .[$n];▼
▲ def Q(n):
▲ n as $n
▲ | (if . == null then [1,1,1] else . end) as $q
▲ | if $q[$n] != null then $q
▲ else
▲ $q | Q($n-1) as $q1
▲ | $q1 | Q($n-2) as $q2
▲ | $q2 | Q($n - $q2[$n - 1]) as $q3 # Q(n - Q(n-1))
▲ | $q3 | Q($n - $q3[$n - 2]) as $q4 # Q(n - Q(n-2))
▲ | ($q4[$n - $q4[$n-1]] + $q4[$n - $q4[$n -2]]) as $ans
▲ | $q4 | setpath( [$n]; $ans)
▲ end ;
# count the number of times Q(i) > Q(i+1) for 0 < i < n
def flips(n):
(reduce range(
(
| reduce range(0;
▲# The three tasks at hand:
((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),
(
===Transcript===
<lang bash>
Line 1,035 ⟶ 1,023:
flips(100000) = 49798
real
user
sys
=={{header|Julia}}==
|