Hofstadter Q sequence: Difference between revisions

{{trans|C}}

 

qseq[1] = 1

qseq[2] = 1

I qseq[i] < qseq[i-1]

less_than_preceding++

 

{{out}}

=={{header|360 Assembly}}==

{{trans|PL/I}}

HOFSTRAD CSECT

USING HOFSTRAD,R15 set base register

Q DS 1000F array q(1000)

YREGS

{{out}}

<pre style="height:16ex">

n= 10, q= 6

n=1000, q= 502

</pre>

 

=={{header|Ada}}==

 

procedure Hofstadter_Q_Sequence is

-- how many times a member of the sequence is less than its preceding term

-- for terms up to and including the 100,000'th term

 

{{out}}

{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of '''format'''[ted] ''transput''.}}

 

 

INT n = 100000;

 

printf(($"flips: "g(0)l$, flip))

{{out}}

<pre>

502

flips: 49798

</pre>

 

=={{header|APL}}==

 

size←100000

seq←{⍵,+/⍵[(1+⍴⍵)-¯2↑⍵]}⍣(size-2)⊢1 1

⎕←'The 1000th term is:', seq[1000]

⎕←(+/ 2>/seq),'terms were preceded by a larger term.'

 

{{out}}

49798 terms were preceded by a larger term.

</pre>

 

=={{header|AutoHotkey}}==

Q := HofsQSeq(100000)

 

}

return Q

{{out}}

<pre>First ten: 1, 1, 2, 3, 3, 4, 5, 5, 6, 6,

 

=={{header|AWK}}==

BEGIN {

N = 100000

}

return seq

 

<pre>Q-sequence(1..10) : 1 1 2 3 3 4 5 5 6 6

number of Q(n)<Q(n+1) for n<=100000 : 49798</pre>

 

{{trans|FreeBASIC}}

limite = 100000

dim Q[limite+1]

print "Término número 1000: "; Q[1000]

print "Términos menores que los anteriores: "; cont

{{out}}

<pre>

</pre>

 

FOR i% = 1 TO 10 : PRINT ;FNq(i%, c%) " "; : NEXT : PRINT

PRINT "1000th term = " ; FNq(1000, c%)

IF q%(i%) < q%(i%-1) THEN c% += 1

NEXT

{{out}}

<pre>

Term is less than preceding term 49798 times

</pre>

 

=={{header|Bracmat}}==

& tbl$(memo,!memocells+1) { allocate array }

& ( Q

)

& out$!lessThan

Output:

<pre>1 1 2 3 3 4 5 5 6 6

502

49798</pre>

 

=={{header|C}}==

#include <stdlib.h>

 

printf("flips: %d\n", flip);

return 0;

{{out}}

<pre>1 1 2 3 3 4 5 5 6 6

=={{header|C sharp}}==

 

using System.Collections.Generic;

 

}

}

 

{{out}}

solution modeled after Perl solution

 

int main() {

std::cout << less_than_preceding << " times a number was preceded by a greater number!" << std::endl;

return 0;

{{out}}

<pre>The first 10 numbers are: 1 1 2 3 3 4 5 5 6 6

The subsequences are vectors for efficient indexing.

''qfirst'' iterates ''qs'' so the nth iteration is Q{1..n].

(let [n (count q)]

(condp = n

(println "first 10:" (qfirst 10))

(println "1000th:" (last (qfirst 1000)))

{{out}}

1000th: 502

 

=={{header|CoffeeScript}}==

{{trans|JavaScript}}

memo = [ 1 ,1, 1]

Q = (n) ->

# some results:

console.log 'Q(' + i + ') = ' + hofstadterQ(i) for i in [1..10]

{{out}}

<pre>Q(1) = 1

Q(9) = 6

Q(10) = 6

Q(1000) = 502</pre>

 

=={{header|Common Lisp}}==

 

;;; generic memoization macro

(if (< next-q last-q) (incf c))

(setf last-q next-q))

{{out}}

<pre>First of Q: (1 1 2 3 3 4 5 5 6 6)

Bumps up to 100000: 49798</pre>

 

:initial-element 1

:adjustable t

(aref cc (- n (aref cc (- n 2)))))

cc))

 

=={{header|D}}==

 

int Q(in int n) nothrow

iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));

}

{{out}}

<pre>Q(n) for n = [1..10] is: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

{{trans|Python}}

Same output.

 

uint Q(in int n) nothrow

iota(2, 100_001).count!(i => Q(i) < Q(i - 1)));

}

 

===Even Faster Version===

This code is here to show that you don't have to use all fancy features of D. Straightforward simple code is often clearer, and faster.

 

import std.stdio;

 

writefln("Q(i) is less than Q(i-1) for i [2..100_000] %d times.", lt);

}

 

=={{header|Dart}}==

Naive version using only recursion (Q(1000) fails due to browser script runtime restrictions)

 

main() {

}

print("Q(1000)=${Q(1000)}");

 

Version featuring caching.

Map<int,int> _table;

 

}

print("value is smaller than previous $count times");

{{out}}

<pre>Q(1)=1

 

If the maximum number is known, filling an array is probably the fastest solution.

List<int> q=new List<int>(100001);

q[1]=q[2]=1;

print("Q(1000)=${q[1000]}");

print("value is smaller than previous $count times");

 

=={{header|EchoLisp}}==

(define RECURSE_BUMP 500) ;; minimum of chrome:500 safari:1000 firefox:2000

 

(Q 1000) → 502

(flips 100000) → 49798

 

=={{header|Eiffel}}==

class

APPLICATION

end

 

{{out}}

<pre>

{{trans|Erlang}}

changed collection (Erlang array => Map)

defp flip(v2, v1) when v1 > v2, do: 1

defp flip(_v2, _v1), do: 0

end

 

 

{{out}}

 

=={{header|Erlang}}==

%% Hofstadter Q Sequence for Rosetta Code

 

Acc = array:set(1, 1, Tmp),

hofstadter(?MAX, 2, Acc, 0).

{{out}}

<pre>

=={{header|ERRE}}==

{{output|ERRE}}

PROGRAM HOFSTADER_Q

 

PRINT("Number of Q(n)<Q(n+1) for n<=10000 : ";NN)

END PROGRAM

Note: The extra credit was limited to 10000 because memory addressable range is limited to 64K.

If you want to implement extra credit for 100,000 you must use external file for array Q%[].

 

=={{header|F_Sharp|F#}}==

===The function===

// Populate an array with values of Hofstadter Q sequence. Nigel Galloway: August 26th., 2020

let fQ N=let g=Array.length N in N.[0]<-1; N.[1]<-1;(for g in 2..g-1 do N.[g]<-N.[g-N.[g-1]]+N.[g-N.[g-2]])

===The Tasks===

let Q=Array.zeroCreate<int>10 in fQ Q; printfn "%A" Q

let Q=Array.zeroCreate<int>1000 in fQ Q; printfn "%d" (Array.last Q)

{{out}}

<pre>

</pre>

===Extra Credit===

let Q=Array.zeroCreate<int>100000 in fQ Q; printfn "%d" (Q|>Seq.pairwise|>Seq.sumBy(fun(n,g)->if n>g then 1 else 0))

{{out}}

<pre>

 

;What is a large number?

let Q=Array.zeroCreate<int>2500000000 in fQ Q; printfn "%d" (Array.last Q)

let Q=Array.zeroCreate<int>5000000000 in fQ Q; printfn "%d" (Array.last Q)

{{out}}

<pre>

=={{header|Factor}}==

We define a method next that takes a sequence of the first n Q values and appends the next one to it. Then we perform it 1000 times on <code>{ 1 1 }</code> and show the first 10 and 999th (because the list is zero-indexed) elements.

dup 2 tail* over length [ swap - ] curry map

[ dupd swap nth ] map 0 [ + ] reduce suffix ;

( scratchpad ) { 1 1 } 1000 [ next ] times dup 10 head . 999 swap nth .

{ 1 1 2 3 3 4 5 5 6 6 }

 

=={{header|Fortran}}==

The latter-day function COUNT(''logical expression'') could easily be replaced by a simple test-and-count in the DO-loop preparing the array. One hopes that the compiler produces sensible code rather than creating an auxiliary array of boolean results then counting the ''true'' values. Rather more clunky is the need to employ odd structure for the input loop so as to handle possible bad input (text, rather than a valid number, for example) and who knows, end-of-file might happen also.

 

Calculate the Hofstadter Q-sequence, using a big array rather than recursion.

INTEGER ENUFF

999 WRITE (6,*) "Bye."

END

 

Output:

 

=={{header|FreeBASIC}}==

Const limite = 100000

 

Print "Terminos menores que los anteriores: " &cont

End

{{out}}

<pre>

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Go}}==

Sure there are ways that run faster or handle larger numbers; for the task though, maps and recursion work just fine.

 

import "fmt"

func showQ(n int) {

fmt.Printf("Q(%d) = %d\n", n, q(n))

{{out}}

<pre>

Q(1000000) = 512066

</pre>

 

=={{header|Haskell}}==

The basic task:

 

qq = 0 : 1 : 1 : map g [3..]

g n = qq !! (n - qq !! (n-1)) + qq !! (n - qq !! (n-2))

*Main> (take 10 qSequence, qSequence !! (1000-1))

([1,1,2,3,3,4,5,5,6,6],502)

 

Extra credit task:

 

 

qSequence n = arr

. _S (zipWith (-)) tail . take n . elems $ arr )

 

 

{{out}}

([1,1,2,3,3,4,5,5,6,6],502,49798)

(0.09 secs, 18879708 bytes)

Prelude Main> qSeqTest 1000000 100000 -- 1,000,000-th item

([1,1,2,3,3,4,5,5,6,6],512066,49798)

 

Using a list (more or less) seemlessly backed up by a double resizing array:

qq ar n = (arr!n) : qq arr (n+1) where

l = snd (bounds ar)

putStr("1000-th: "); print (q !! 999)

putStr("flips: ")

{{out}}

<pre>

 

List backed up by a list of arrays, with nominal constant lookup time. ''Somehow'' faster than the previous method.

import Data.Int (Int64)

where

qqq :: [Int64]

 

=={{header|Icon}} and {{header|Unicon}}==

 

procedure main()

runerr(500,n)

}

 

{{libheader|Icon Programming Library}}

 

=={{header|IS-BASIC}}==

110 LET LIMIT=1000

120 NUMERIC Q(1 TO LIMIT)

190 PRINT Q(I);

200 NEXT

 

=={{header|J}}==

Q=: verb define

n=. >./,y

end.

y{Qs

 

 

1 1 2 3 3 4 5 5 6 6

Q 1000

502

+/2>/\ Q 1+i.100000

 

'''Note''': The bottom-up solution uses iteration and doesn't risk failure due to recursion limits or cache overflows. The top-down solution uses recursion, and likely hews closer to the spirit of the task. While this latter uses memoization/caching, at some point it will still hit a recursion limit (depends on the environment; in mine, it barfs at N=4402). We use the bottom up version for the extra credit part of this task (the expression which compares adjacent numbers and gave us the result 49798).

[[Category:Memoization]]{{works with|Java|1.5+}}

This example also counts the number of times each n is used as an argument up to 100000 and reports the one that was used the most.

import java.util.Map;

 

System.out.println("Q(" + maxN + ") was called the most with " + maxUses + " calls");

}

{{out}}

<pre>Q(1) = 1

===ES5===

Based on memoization example from 'JavaScript: The Good Parts'.

var memo = [1,1,1];

var Q = function (n) {

 

console.log('Q(1000) = ' + hofstadterQ(1000));

{{out}}

<pre>

===ES6===

Memoising with the accumulator of a fold

'use strict';

 

.reduce((a, x, i, xs) => x < xs[i - 1] ? a + 1 : a, 0)

};

 

{{Out}}

"thousandth":502,

 

=={{header|jq}}==

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.

# For n>=2, Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2))

def Q:

((range(0;11), 1000) | "Q(\(.)) = \( . | Q)"),

 

===Transcript===

$ uname -a

Darwin Mac-mini 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun 3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64

real 0m0.562s

user 0m0.541s

 

=={{header|Julia}}==

The following implementation accepts an argument that is a single integer, an array of integers, or a range:

nmax = maximum(n)

r = Vector{typerst}(nmax)

println("First ten elements of sequence: ", join(hofstQseq(1:10), ", "))

println("1000-th element: ", hofstQseq(1000))

 

{{out}}

 

And we can also count the number of times a value is less than its predecessor by, for example:

cnt = count(diff(seq) .< 0)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun main(args: Array<String>) {

val flips = (2..100_000).count { q[it] < q[it - 1] }

println("\nThe number of flips for the first 100,000 terms is : $flips")

 

{{out}}

The number of flips for the first 100,000 terms is : 49798

</pre>

 

=={{header|Maple}}==

We use automatic memoisation ("option remember") in the following. The use of "option system" assures that memoised values can be garbage collected.

option remember, system;

if n = 1 or n = 2 then

thisproc( n - thisproc( n - 1 ) ) + thisproc( n - thisproc( n - 2 ) )

end if

From this we get:

1, 1, 2, 3, 3, 4, 5, 5, 6, 6

 

> Q( 1000 );

To determine the number of "flips", we proceed as follows.

> for i from 2 to 100000 do

> if L[ i ] < L[ i - 1 ] then

> end do:

> flips;

Alternatively, we can build the sequence in an array.

local a := Array( 1 .. n );

a[ 1 ] := 1;

end do;

flips

This gives the same result.

 

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Hofstadter[n_Integer?Positive] := Hofstadter[n] = Block[{$RecursionLimit = Infinity},

Hofstadter[n - Hofstadter[n - 1]] + Hofstadter[n - Hofstadter[n - 2]]

{{out}}

{1,1,2,3,3,4,5,5,6,6}

Hofstadter[1000]

502

Count[Differences[Hofstadter /@ Range[100000]], _?Negative]

 

=={{header|MATLAB}} / {{header|Octave}}==

This solution pre-allocates memory and is an iterative solution, so caching or recursion limits do not apply.

%% zeros are used to pre-allocate memory, this is not strictly necessary but can significantly improve performance for large N

Q = [1,1,zeros(1,N-2)];

Q(n) = Q(n-Q(n-1))+Q(n-Q(n-2));

end;

Confirm and display that the first ten terms of the sequence are: 1, 1, 2, 3, 3, 4, 5, 5, 6, and 6

<pre>>> Qsequence(10)

ans = 49798

</pre>

 

=={{header|MiniScript}}==

 

Q = function(n)

print "Q(" + i + ") = " + Q(i)

end for

{{out}}

<pre>Q(1) = 1

Q(10) = 6

Q(1000) = 502</pre>

 

=={{header|Nim}}==

 

echo q[0..9]

 

var lessCount = 0

if q[n] < q[n-1]:

inc lessCount

{{out}}

<pre>@[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

=={{header|Oberon-2}}==

Works with oo2c version 2

MODULE Hofstadter;

IMPORT

Out.String("terms less than the previous: ");Out.LongInt(count,4);Out.Ln

END Hofstadter.

Output:

<pre>

</pre>

 

 

| q i |

ListBuffer newSize(100000) dup add(1) dup add(1) ->q

q at(i) q at(i 1-) < ifTrue: [ 1+ ]

]

 

{{out}}

=={{header|PARI/GP}}==

Straightforward, unoptimized version; about 1 ms.

Q1=vecextract(Q,"1..10");

print("First 10 terms: "Q1,if(Q1==[1, 1, 2, 3, 3, 4, 5, 5, 6, 6]," (as expected)"," (in error)"));

 

{{out}}

 

=={{header|Pascal}}==

 

const

inc(flips);

writeln('Flips: ', flips);

{{out}}

<pre>:> ./HofstadterQSequence

=={{header|Perl}}==

 

push @Q, $Q[-$Q[-1]] + $Q[-$Q[-2]] for 1..100_000;

say "First 10 terms: [@Q[1..10]]";

say "Term 1000: $Q[1000]";

{{out}}

<pre>First 10 terms: [1 1 2 3 3 4 5 5 6 6]

 

A more verbose and less idiomatic solution:

use warnings;

use strict;

print "Up to and including the 100000'th term, $less_than_preceding terms are less " .

"than their preceding terms!\n";

{{out}}

<pre>1

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.

 

use strict;

use warnings;

}

print "Extra credit: $count\n";

{{out}}

<pre>

 

=={{header|Phix}}==

{{out}}

<pre>

First ten terms: {1,1,2,3,3,4,5,5,6,6}

1000th: 502

</pre>

 

=={{header|PicoLisp}}==

(cache '(NIL) N

(if (>= 2 N)

(+

(q (- N (q (dec N))))

Test:

-> (1 1 2 3 3 4 5 5 6 6)

 

: (let L (mapcar q (range 1 100000))

(cnt < (cdr L) L) )

 

=={{header|PL/I}}==

/* Hofstrader Q sequence for any "n". */

 

end;

end H;

{{out}}

<pre>

</pre>

Bonus to produce the count of unordered values:

declare tally fixed binary (31) initial (0);

 

end;

put skip data (tally);

{{out}}

<pre>

TALLY= 49798;

</pre>

 

=={{header|PureBasic}}==

End 1

EndIf

PrintN(~"Flips:\t\t" + Str(flip))

Input()

{{out}}

<pre>First ten: 1 1 2 3 3 4 5 5 6 6

 

=={{header|Python}}==

if n < 1 or type(n) != int: raise ValueError("n must be an int >= 1")

try:

print("Q(n) for n = [1..10] is:", ', '.join(str(i) for i in first10))

assert q(1000) == 502, "Q(1000) value error"

 

;Extra credit:

 

The following code is to be concatenated to the code above:

 

def q1(n):

tmp = q1(100000)

print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %

 

{{out|Combined output}}

 

===Alternative===

l = len(q.seq)

while l <= n:

q(100000)

print("Q(i+1) < Q(i) for i [1..100000] is true %i times." %

 

=={{header|R}}==

cache <- vector("integer", 0)

cache[1] <- 1

}

cat(count,"terms is less than its preceding term\n")

{{out}}

<pre>

 

=={{header|Racket}}==

#lang racket

 

;; extra credit

(for/sum ([i 100000]) (if (< (Q (add1 i)) (Q i)) 1 0))

 

{{out}}

Similar concept as the perl5 solution, except that the cache is only filled on demand.

 

has @!c = 1,1;

method AT-POS ($me: Int $i) {

my $count = 0;

$count++ if $Q[$_ +1 ] < $Q[$_] for ^99_999;

{{out}}

<pre>first ten: 1 1 2 3 3 4 5 5 6 6

{{Works with|rakudo|2015-11-22}}

With a lazily generated array, we automatically get caching.

(state $n = 1)++;

@Q[$n - $a] + @Q[$n - $b]

say "In the first 100_000 terms, ",

[+](@Q[1..100000] Z< @Q[0..99999]),

(Same output.)

 

===non-recursive===

The REXX language doesn't allow expressions for stemmed array indices, so a temporary variable must be used.

parse arg a b c d . /*obtain optional arguments from the CL*/

if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _

{{out|output|text=&nbsp; when using the internal default inputs:}}

<pre>

This REXX example is identical to the first version

except that it uses a function to retrieve array elements which may have index expressions.

parse arg a b c d . /*obtain optional arguments from the CL*/

if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/

@: parse arg ?; return @.? /*return value of @.? to invoker.*/

th: procedure; #=abs(arg(1)); return word('th st nd rd',1+#//10*(#//100%10\==1)*(#//10<4))

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}}

 

 

===recursive===

parse arg a b c d . /*obtain optional arguments from the CL*/

if a=='' | a=="," then a= 10 /*Not specified? Then use the default.*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

th: procedure; #=abs(arg(1)); return word('th st nd rd',1+#//10*(#//100%10\==1)*(#//10<4))

{{out|output|text=&nbsp; is identical to the 1^st REXX version.}}

 

 

=={{header|Ring}}==

n = 20

aList = list(n)

if i <= 20 see "n = " + string(i) + " : "+ aList[i] + nl ok

next

 

=={{header|Ruby}}==

def Q(n)

if @cache[n].nil?

prev = q

end

{{out}}

<pre>first 10 numbers in the sequence: [1, 1, 2, 3, 3, 4, 5, 5, 6, 6]

 

=={{header|Run BASIC}}==

dim Q(n)

Q(1) = 1

if i > 20 then print "n=";using("####",i);using("####",Q(i))

end

{{out}}

<pre>

Rust doesn't allow static Vec's (but there's lazy_static crate), thus memoization storage is allocated in <code>main</code>.

 

let cur_len=q.len()-1;

let i=x as usize;

println!("Term is less than preceding term {} times", nless);

}

{{out}}

<pre>

Naive but elegant version using only recursion doesn't work

because runtime is excessive increasing ...

val Q: Int => Int = n => {

if (n <= 2) 1

(1 to 10).map(i=>(i,Q(i))).foreach(t=>println("Q("+t._1+") = "+t._2))

println("Q("+1000+") = "+Q(1000))

 

 

Thus we are forced to use a caching featured version.

 

 

val HofQ = scala.collection.mutable.Map((1->1),(2->1))

println("Q("+1000+") = "+Q(1000))

println((3 to 100000).filter(i=>Q(i)<Q(i-1)).size)

{{out}}

<pre>Q(1) = 1

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.

(define filled 3)

(define len 3)

(if (>= i 100000) s

(loop (+ s (if (> (q i) (q (+ 1 i))) 1 0)) (+ 1 i)))))

{{out}}

<pre>Q(1 .. 10): 1 1 2 3 3 4 5 5 6 6

 

=={{header|Seed7}}==

 

const type: intHash is hash [integer] integer;

end for;

writeln("q(n) < q(n-1) for n = 2 .. 100000: " <& less_than_preceding);

 

{{out}}

q(n) < q(n-1) for n = 2 .. 100000: 49798

</pre>

 

=={{header|Sidef}}==

Using a memoized function:

n <= 2 ? 1

 : Q(n - Q(n-1))+Q(n-Q(n-2))

say "First 10 terms: #{ {|n| Q(n) }.map(1..10) }"

say "Term 1000: #{Q(1000)}"

 

Using an array:

100_000.times {

Q << (Q[-Q[-1]] + Q[-Q[-2]])

}

say "Term 1000: #{Q[1000]}"

{{out}}

<pre>

Term 1000: 502

Terms less than preceding in first 100k: 49798

</pre>

 

=={{header|Tailspin}}==

templates q

def outputFrom: $(1);

 

[[1, 100000] -> q] -> countDownSteps -> 'Less than previous $; times' -> !OUT::write

{{out}}

<pre>

 

=={{header|Tcl}}==

 

# Index 0 is not used, but putting it in makes the code a bit shorter

incr count [expr {$q > [set q [expr {Q($i)}]]}]

}

{{out}}

<pre>

{{trans|BBC BASIC}}

uBasic/4tH simply lacks the memory to make it through to the 1000th term. 256 is the best it can do.

For i = 1 To 10 : Print FUNC(_q(i));" "; : Next : Print

Print "256th term = ";FUNC(_q(256))

Next

 

{{out}}

<pre>First 10 terms of Q = 1 1 2 3 3 4 5 5 6 6

 

=={{header|VBA}}==

Public Sub HofstadterQ()

Dim n As Long, smaller As Long

Debug.Print "The 1000th term is:"; Q(1000)

Debug.Print "Number of times smaller:"; smaller

<pre>First ten terms:

1 1 2 3 3 4 5 5 6 6

 

=={{header|VBScript}}==

Sub q_sequence(n)

Dim Q()

 

q_sequence(100000)

 

{{Out}}

 

=={{header|Visual FoxPro}}==

LOCAL p As Integer, i As Integer

CLEAR

RETURN aq[n]

ENDFUNC

{{out}}

<pre>

 

=={{header|Wren}}==

var q = List.filled(N + 1, 0)

q[1] = 1

if (q[n] < q[n-1]) flips = flips + 1

}

 

{{out}}

 

=={{header|XPL0}}==

int N, C, Q(100_001);

[Q(1):= 1; Q(2):= 1; C:= 0;

IntOut(0, Q(1000)); CrLf(0);

IntOut(0, C); CrLf(0);

 

{{out}}

=={{header|zkl}}==

{{trans|ALGOL 68}}

q:=(n+1).pump(List.createLong(n+1).write); // (0,1,2,...,n) base 1

q[1] = q[2] = 1;

flip := 0;

foreach i in (n){ flip += (q[i] > q[i + 1]) }

{{out}}

<pre>

{{trans|BBC_BASIC}}

Extra credit 100000 is not implemented because of memory limitations.

20 FOR i=1 TO 10: GO SUB 1000: PRINT s;" ";: NEXT i: PRINT

30 LET i=1000

1090 NEXT j

1100 LET s=q(i)