Anonymous user
Hofstadter Q sequence: Difference between revisions
m
{{out}}
(Add Nimrod) |
m ({{out}}) |
||
Line 75:
end Hofstadter_Q_Sequence;</lang>
{{out}}
<pre> 1 1 2 3 3 4 5 5 6 6
502
Line 109:
printf(($"flips: "g(0)l$, flip))
)</lang>
{{out}}
<pre>
1 1 2 3 3 4 5 5 6 6
Line 137 ⟶ 138:
return Q
}</lang>
{{out}}
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
1000th: 502
Line 189 ⟶ 190:
NEXT
= q%(n%)</lang>
{{out}}
<pre>
First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6
Line 221 ⟶ 222:
printf("flips: %d\n", flip);
return 0;
}</lang>
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
502
Line 251 ⟶ 253:
return 0 ;
}</lang>
{{out}}
<pre>The first 10 numbers are:
1
Line 334 ⟶ 336:
}</lang>
{{out}}
<pre>Q(1) = 1
Q(2) = 1
Line 365 ⟶ 367:
(println "1000th:" (last (qfirst 1000)))
(println "extra credit:" (->> (qfirst 100000) (partition 2 1) (filter #(apply > %)) count))</lang>
{{out}}
<lang>first 10: [1 1 2 3 3 4 5 5 6 6]
1000th: 502
Line 397 ⟶ 399:
(if (< next-q last-q) (incf c))
(setf last-q next-q))
finally (return c)))</lang>
{{out}}
<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)
Q(1000): 502
Bumps up to 100000: 49798</
Although the above definition of <code>q</code> is more general, for this specific problem the following is faster:<lang lisp>(let ((cc (make-array 3 :element-type 'integer
Line 434 ⟶ 438:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}</lang>
{{out}}
<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Q(1000) = 502
Line 522 ⟶ 526:
print("value is smaller than previous $count times");
}</lang>
{{out}}
<pre>Q(1)=1
Q(2)=1
Line 587 ⟶ 591:
Acc = array:set(1, 1, Tmp),
hofstadter(?MAX, 2, Acc, 0).
</lang>
{{out}}
<pre>
The first ten terms are: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
Line 613 ⟶ 618:
printfn "q(1000) = %A" (q 1000I)
printfn "descents(100000) = %A" (Seq.sum (Seq.init 100000 (fun i -> if q(bigint(i)) > q(bigint(i+1)) then 1 else 0)))</lang>
{{out}}
<pre>q(1 .. 10) = 1 1 2 3 3 4 5 5 6 6
q(1000) = 502
Line 676 ⟶ 681:
fmt.Printf("Q(%d) = %d\n", n, q(n))
}</lang>
{{out}}
<pre>
Q(1) = 1
Line 730 ⟶ 735:
_S f g x = f x (g x)</lang>
{{out}}
<lang Haskell>Prelude Main> qSeqTest 1000 100000 -- reversals in 100,000
([1,1,2,3,3,4,5,5,6,6],502,49798)
Line 832 ⟶ 836:
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting]
{{out}}
Q[1000]=502 - verified.
Q(16)=9 < Q(15)=10
Line 919 ⟶ 924:
}
}</lang>
{{out}}
<pre>Q(1) = 1
Q(2) = 1
Line 955 ⟶ 960:
console.log('Q(1000) = ' + hofstadterQ(1000));
</lang>
{{out}}
<pre>
Q(1) = 1
Line 1,039 ⟶ 1,044:
end</lang>
{{out}}
<lang julia>julia> Q(1:10)
10-element Array{Int64,1}:
Line 1,110 ⟶ 1,115:
Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]
]</lang>
{{out}}
<lang Mathematica>Hofstadter /@ Range[10]
{1,1,2,3,3,4,5,5,6,6}
Line 1,156 ⟶ 1,161:
inc lessCount
echo lessCount</lang>
{{out}}
<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
502
Line 1,168 ⟶ 1,173:
print("1000-th term: "Q[1000],if(Q[1000]==502," (as expected)"," (in error)"));</lang>
{{out}}
<pre>First 10 terms: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6] (as expected)
1000-th term: 502 (as expected)</pre>
Line 1,197 ⟶ 1,202:
writeln('Flips: ', flips);
end.</lang>
{{out}}
<pre>:> ./HofstadterQSequence
1 1 2 3 3 4 5 5 6 6
Line 1,227 ⟶ 1,232:
"than their preceding terms!\n";
</lang>
{{out}}
<pre>1
1
Line 1,242 ⟶ 1,247:
</pre>
Here's a second solution.
This solution uses tie to make the Q sequence look like a regular array, and only fills the cache on demand.
Some pre-allocation is done which provides a minor speed increase for the extra credit.
I could have chosen to do recursion instead of iteration, as perl has no limit on how deeply one may recurse, but did not see the benefit of doing so.
<lang Perl>#!perl
Line 1,280 ⟶ 1,288:
print "Extra credit: $count\n";
</lang>
{{out}}
<pre>
1 1 2 3 3 4 5 5 6 6
Line 1,372 ⟶ 1,380:
end H;
</lang>
{{out}}
<pre>
How many values do you want? :
Line 1,398 ⟶ 1,406:
n=1000 502
</pre>
<pre>
n=100000 48157
Line 1,411 ⟶ 1,419:
put skip data (tally);
</lang>
{{out}}
<pre>
n=100000 48157
Line 1,461 ⟶ 1,469:
sum(k1 < k0 for k0, k1 in zip(q.seq[1:], q.seq[2:])))</lang>
<pre>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.</pre>
===Alternative===
<lang python>def q(n):
Line 1,534 ⟶ 1,543:
end /*j*/
return q.x /*return the Xth term to caller.*/</lang>
{{out}}
<pre>
1 1
Line 1,553 ⟶ 1,562:
===non-recursive, simpler===
This REXX example is identical to the first version
except that it uses a function to retrieve array elements with index expressions.
<lang rexx>/*REXX program to generate Hofstadter Q sequence for any N. */
q.=1 /*negative #s won't have values displayed.*/
Line 1,577 ⟶ 1,587:
/*──────────────────────────────────Q subroutine────────────────────────*/
q: parse arg ?; return q.? /*return value of Q.? to invoker.*/</lang>
'''output''' is identical to the first version.<br>
===recursive===
Line 1,606 ⟶ 1,615:
if q.n==0 then q.n=QR(n-QR(n-1)) + QR(n-QR(n-2)) /*¬defined? Define it*/
return q.n /*return with the value. */</lang>
'''output''' is identical to the first version.<br><br>
=={{header|Ruby}}==
Line 1,633 ⟶ 1,641:
end
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</lang>
{{out}}
<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
1000'th term: 502
number of times in the first 100,000 terms where Q(i)<Q(i-1): 49798</pre>
=={{header|Run BASIC}}==
Line 1,650 ⟶ 1,657:
if i > 20 then print "n=";using("####",i);using("####",Q(i))
end
</lang
{{out}}
<pre>
How many values do you want? :?1000
n= 1 1
Line 1,677 ⟶ 1,686:
=={{header|Scala}}==
{{works with|Scala|2.9.1}}
Naive but elegant version using only recursion doesn't work
because runtime is excessive increasing ...
<lang scala>object HofstadterQseq extends App {
val Q: Int => Int = n => {
Line 1,688 ⟶ 1,698:
Unfortunately the function Q isn't tail recursiv,
therefore the compiler can't optimize it.
Thus we are forced to use a caching featured version.
<lang scala>object HofstadterQseq extends App {
Line 1,709 ⟶ 1,721:
println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)
}</lang>
{{out}}
<pre>Q(1) = 1
Q(2) = 1
Line 1,724 ⟶ 1,736:
=={{header|Scheme}}==
I wish there were a portable way to <code>define-syntax</code>,
or to resize arrays, or to do formated output--anything to make the code
less silly looking while still run under more than one interpreter.
<lang lisp>(define qc '#(0 1 1))
(define filled 3)
Line 1,771 ⟶ 1,785:
(if (>= i 100000) s
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))
(newline)</lang>
{{out}}
<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6
Q(1000): 502
bumps up to 100000: 49798</
=={{header|Seed7}}==
Line 1,815 ⟶ 1,831:
end func;</lang>
{{out}}
<pre>
q(n) for n = 1 .. 10:
Line 1,848 ⟶ 1,864:
}
puts "Q(i)<Q(i-1) for i \[2..100000\] is true $count times"</lang>
{{out}}
<pre>
Q(1) == 1
| |||