Hofstadter Q sequence: Difference between revisions

Content added Content deleted
(Add Nimrod)
m ({{out}})
Line 75: Line 75:
end Hofstadter_Q_Sequence;</lang>
end Hofstadter_Q_Sequence;</lang>


{{out}}
Output:
<pre> 1 1 2 3 3 4 5 5 6 6
<pre> 1 1 2 3 3 4 5 5 6 6
502
502
Line 109: Line 109:


printf(($"flips: "g(0)l$, flip))
printf(($"flips: "g(0)l$, flip))
)</lang>'''Output:'''
)</lang>
{{out}}
<pre>
<pre>
1 1 2 3 3 4 5 5 6 6
1 1 2 3 3 4 5 5 6 6
Line 137: Line 138:
return Q
return Q
}</lang>
}</lang>
{{out}}
'''Output:'''
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,
1000th: 502
1000th: 502
Line 189: Line 190:
NEXT
NEXT
= q%(n%)</lang>
= q%(n%)</lang>
{{out}}
'''Output:'''
<pre>
<pre>
First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6
First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6
Line 221: Line 222:
printf("flips: %d\n", flip);
printf("flips: %d\n", flip);
return 0;
return 0;
}</lang>'''Output:'''
}</lang>
{{out}}
<pre>1 1 2 3 3 4 5 5 6 6
<pre>1 1 2 3 3 4 5 5 6 6
502
502
Line 251: Line 253:
return 0 ;
return 0 ;
}</lang>
}</lang>
{{out}}
Output:
<pre>The first 10 numbers are:
<pre>The first 10 numbers are:
1
1
Line 334: Line 336:
}</lang>
}</lang>


{{out}}
'''Output'''
<pre>Q(1) = 1
<pre>Q(1) = 1
Q(2) = 1
Q(2) = 1
Line 365: Line 367:
(println "1000th:" (last (qfirst 1000)))
(println "1000th:" (last (qfirst 1000)))
(println "extra credit:" (->> (qfirst 100000) (partition 2 1) (filter #(apply > %)) count))</lang>
(println "extra credit:" (->> (qfirst 100000) (partition 2 1) (filter #(apply > %)) count))</lang>
{{out}}
Output:
<lang>first 10: [1 1 2 3 3 4 5 5 6 6]
<lang>first 10: [1 1 2 3 3 4 5 5 6 6]
1000th: 502
1000th: 502
Line 397: Line 399:
(if (< next-q last-q) (incf c))
(if (< next-q last-q) (incf c))
(setf last-q next-q))
(setf last-q next-q))
finally (return c)))</lang>output<lang>First of Q: (1 1 2 3 3 4 5 5 6 6)
finally (return c)))</lang>
{{out}}
<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)
Q(1000): 502
Q(1000): 502
Bumps up to 100000: 49798</lang>
Bumps up to 100000: 49798</pre>


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
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: Line 438:
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));
}</lang>
}</lang>
{{out}}
Output:
<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
Q(1000) = 502
Q(1000) = 502
Line 522: Line 526:
print("value is smaller than previous $count times");
print("value is smaller than previous $count times");
}</lang>
}</lang>
{{out}}
Output:
<pre>Q(1)=1
<pre>Q(1)=1
Q(2)=1
Q(2)=1
Line 587: Line 591:
Acc = array:set(1, 1, Tmp),
Acc = array:set(1, 1, Tmp),
hofstadter(?MAX, 2, Acc, 0).
hofstadter(?MAX, 2, Acc, 0).
</lang>'''Output:'''
</lang>
{{out}}
<pre>
<pre>
The first ten terms are: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
The first ten terms are: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
Line 613: Line 618:
printfn "q(1000) = %A" (q 1000I)
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>
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}}
Output
<pre>q(1 .. 10) = 1 1 2 3 3 4 5 5 6 6
<pre>q(1 .. 10) = 1 1 2 3 3 4 5 5 6 6
q(1000) = 502
q(1000) = 502
Line 676: Line 681:
fmt.Printf("Q(%d) = %d\n", n, q(n))
fmt.Printf("Q(%d) = %d\n", n, q(n))
}</lang>
}</lang>
{{out}}
Output:
<pre>
<pre>
Q(1) = 1
Q(1) = 1
Line 730: Line 735:
_S f g x = f x (g x)</lang>
_S f g x = f x (g x)</lang>


{{out}}
Output:

<lang Haskell>Prelude Main> qSeqTest 1000 100000 -- reversals in 100,000
<lang Haskell>Prelude Main> qSeqTest 1000 100000 -- reversals in 100,000
([1,1,2,3,3,4,5,5,6,6],502,49798)
([1,1,2,3,3,4,5,5,6,6],502,49798)
Line 832: Line 836:
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting]
[http://www.cs.arizona.edu/icon/library/src/procs/printf.icn printf.icn provides formatting]


{{out}}
Output:<pre>Q(1 to 10) - verified.
<pre>Q(1 to 10) - verified.
Q[1000]=502 - verified.
Q[1000]=502 - verified.
Q(16)=9 < Q(15)=10
Q(16)=9 < Q(15)=10
Line 919: Line 924:
}
}
}</lang>
}</lang>
{{out}}
Output:
<pre>Q(1) = 1
<pre>Q(1) = 1
Q(2) = 1
Q(2) = 1
Line 955: Line 960:
console.log('Q(1000) = ' + hofstadterQ(1000));
console.log('Q(1000) = ' + hofstadterQ(1000));
</lang>
</lang>
{{out}}
Output:
<pre>
<pre>
Q(1) = 1
Q(1) = 1
Line 1,039: Line 1,044:
end</lang>
end</lang>


{{out}}
Output:
<lang julia>julia> Q(1:10)
<lang julia>julia> Q(1:10)
10-element Array{Int64,1}:
10-element Array{Int64,1}:
Line 1,110: Line 1,115:
Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]
Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]
]</lang>
]</lang>
{{out}}
Output:
<lang Mathematica>Hofstadter /@ Range[10]
<lang Mathematica>Hofstadter /@ Range[10]
{1,1,2,3,3,4,5,5,6,6}
{1,1,2,3,3,4,5,5,6,6}
Line 1,156: Line 1,161:
inc lessCount
inc lessCount
echo lessCount</lang>
echo lessCount</lang>
{{out}}
Output:
<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
502
502
Line 1,168: Line 1,173:
print("1000-th term: "Q[1000],if(Q[1000]==502," (as expected)"," (in error)"));</lang>
print("1000-th term: "Q[1000],if(Q[1000]==502," (as expected)"," (in error)"));</lang>


{{out}}
Output:
<pre>First 10 terms: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6] (as expected)
<pre>First 10 terms: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6] (as expected)
1000-th term: 502 (as expected)</pre>
1000-th term: 502 (as expected)</pre>
Line 1,197: Line 1,202:
writeln('Flips: ', flips);
writeln('Flips: ', flips);
end.</lang>
end.</lang>
{{out}}
Output:
<pre>:> ./HofstadterQSequence
<pre>:> ./HofstadterQSequence
1 1 2 3 3 4 5 5 6 6
1 1 2 3 3 4 5 5 6 6
Line 1,227: Line 1,232:
"than their preceding terms!\n";
"than their preceding terms!\n";
</lang>
</lang>
{{out}}
Output:
<pre>1
<pre>1
1
1
Line 1,242: Line 1,247:
</pre>
</pre>


Here's a second solution.
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.
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
<lang Perl>#!perl
Line 1,280: Line 1,288:
print "Extra credit: $count\n";
print "Extra credit: $count\n";
</lang>
</lang>
{{out}}
Output:
<pre>
<pre>
1 1 2 3 3 4 5 5 6 6
1 1 2 3 3 4 5 5 6 6
Line 1,372: Line 1,380:
end H;
end H;
</lang>
</lang>
{{out}}
Output:
<pre>
<pre>
How many values do you want? :
How many values do you want? :
Line 1,398: Line 1,406:
n=1000 502
n=1000 502
</pre>
</pre>
Final output for n=100,000
{{out}} for n=100,000
<pre>
<pre>
n=100000 48157
n=100000 48157
Line 1,411: Line 1,419:
put skip data (tally);
put skip data (tally);
</lang>
</lang>
{{out}}
Output:
<pre>
<pre>
n=100000 48157
n=100000 48157
Line 1,461: Line 1,469:
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>


;Combined output:
{{out|Combined output}}
<pre>Q(n) for n = [1..10] is: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
<pre>Q(n) for n = [1..10] is: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6
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===
===Alternative===
<lang python>def q(n):
<lang python>def q(n):
Line 1,534: Line 1,543:
end /*j*/
end /*j*/
return q.x /*return the Xth term to caller.*/</lang>
return q.x /*return the Xth term to caller.*/</lang>
{{out}}
'''output'''
<pre>
<pre>
1 1
1 1
Line 1,553: Line 1,562:


===non-recursive, simpler===
===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.
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. */
<lang rexx>/*REXX program to generate Hofstadter Q sequence for any N. */
q.=1 /*negative #s won't have values displayed.*/
q.=1 /*negative #s won't have values displayed.*/
Line 1,577: Line 1,587:
/*──────────────────────────────────Q subroutine────────────────────────*/
/*──────────────────────────────────Q subroutine────────────────────────*/
q: parse arg ?; return q.? /*return value of Q.? to invoker.*/</lang>
q: parse arg ?; return q.? /*return value of Q.? to invoker.*/</lang>
'''output''' is identical to the first version.
'''output''' is identical to the first version.<br>
<br><br>


===recursive===
===recursive===
Line 1,606: Line 1,615:
if q.n==0 then q.n=QR(n-QR(n-1)) + QR(n-QR(n-2)) /*¬defined? Define it*/
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>
return q.n /*return with the value. */</lang>
'''output''' is identical to the first version.
'''output''' is identical to the first version.<br><br>
<br><br>The recursive version took over five times longer than the non-recursive version.
The recursive version took over five times longer than the non-recursive version.<br>
<br><br>


=={{header|Ruby}}==
=={{header|Ruby}}==
Line 1,633: Line 1,641:
end
end
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</lang>
puts "number of times in the first 100,000 terms where Q(i)<Q(i-1): #{count}"</lang>
{{out}}
output
<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]
1000'th term: 502
1000'th term: 502
number of times in the first 100,000 terms where Q(i)<Q(i-1): 49798</pre>
number of times in the first 100,000 terms where Q(i)<Q(i-1): 49798</pre>



=={{header|Run BASIC}}==
=={{header|Run BASIC}}==
Line 1,650: Line 1,657:
if i > 20 then print "n=";using("####",i);using("####",Q(i))
if i > 20 then print "n=";using("####",i);using("####",Q(i))
end
end
</lang><pre>
</lang>
{{out}}
<pre>
How many values do you want? :?1000
How many values do you want? :?1000
n= 1 1
n= 1 1
Line 1,677: Line 1,686:
=={{header|Scala}}==
=={{header|Scala}}==
{{works with|Scala|2.9.1}}
{{works with|Scala|2.9.1}}
Naive but elegant version using only recursion doesn't work because runtime is excessive increasing ...
Naive but elegant version using only recursion doesn't work
because runtime is excessive increasing ...
<lang scala>object HofstadterQseq extends App {
<lang scala>object HofstadterQseq extends App {
val Q: Int => Int = n => {
val Q: Int => Int = n => {
Line 1,688: Line 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.
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 {
<lang scala>object HofstadterQseq extends App {
Line 1,709: Line 1,721:
println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)
println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)
}</lang>
}</lang>
{{out}}

<pre>Q(1) = 1
<pre>Q(1) = 1
Q(2) = 1
Q(2) = 1
Line 1,724: Line 1,736:


=={{header|Scheme}}==
=={{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.
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))
<lang lisp>(define qc '#(0 1 1))
(define filled 3)
(define filled 3)
Line 1,771: Line 1,785:
(if (>= i 100000) s
(if (>= i 100000) s
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))
(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))
(newline)</lang>output<lang>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6
(newline)</lang>
{{out}}
<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6
Q(1000): 502
Q(1000): 502
bumps up to 100000: 49798</lang>
bumps up to 100000: 49798</pre>


=={{header|Seed7}}==
=={{header|Seed7}}==
Line 1,815: Line 1,831:
end func;</lang>
end func;</lang>


{{out}}
Output:
<pre>
<pre>
q(n) for n = 1 .. 10:
q(n) for n = 1 .. 10:
Line 1,848: Line 1,864:
}
}
puts "Q(i)<Q(i-1) for i \[2..100000\] is true $count times"</lang>
puts "Q(i)<Q(i-1) for i \[2..100000\] is true $count times"</lang>
{{out}}
Output:
<pre>
<pre>
Q(1) == 1
Q(1) == 1
Retrieved from "https://rosettacode.org/wiki/Hofstadter_Q_sequence"