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">

=={{header|8080 Assembly}}==

org 100h

;;; Generate the first 1000 members of the Q sequence

db '*****' ; Placeholder for number

num: db ' $'

{{out}}

=={{header|8086 Assembly}}==

cpu 8086

org 100h

num: db ' $'

Q: dw 1,1

{{out}}

=={{header|Action!}}==

DEFINE MAX="1000"

INT ARRAY q(MAX+1)

OD

PrintF("%I: %I%E",MAX,q(MAX))

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Hofstadter_Q_sequence.png Screenshot from Atari 8-bit computer]

=={{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>

=={{header|ALGOL-M}}==

integer array Q[1:1000];

integer n;

write("The 1000th term is:", Q[1000]);

{{out}}

<pre>The first 10 terms are:

=={{header|ALGOL W}}==

% Q(n) = Q( n - Q( n - 1 ) ) + Q( n - Q( n - 2 ) ) for n > 2 %

integer MAX_Q;

write( i_w := 1, s_w := 0, "Q(n) < Q(n-1) ", ltCount," times for n up to ", MAX_Q )

end

{{out}}

<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}}

=={{header|ARM Assembly}}==

.global _start

_start: ldr r6,=qs @ R6 = base register for Q array

.align 4

.space 8 @ Buffer for number output

{{out}}

=={{header|Arturo}}==

n: 2

while [n<1001][

print ["First ten items:" first.n: 10 q]

{{out}}

=={{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

=={{header|BASIC256}}==

{{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>

=={{header|BBC BASIC}}==

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>

=={{header|Bracmat}}==

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

& ( Q

)

& out$!lessThan

Output:

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

=={{header|BCPL}}==

let start() be

writef("*NThe 1000th term is: %N*N", Q!1000)

{{out}}

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

=={{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|CLU}}==

q: array[int] := array[int]$[1,1]

for i: int in int$from_to(3,n) do

stream$putl(po, "\nflips: " || int$unparse(flips))

{{out}}

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

=={{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

=={{header|COBOL}}==

PROGRAM-ID. Q-SEQ.

MOVE N TO IX.

MOVE Q(N) TO ITEM.

{{out}}

<pre>Q( 1) = 1

=={{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|Cowgol}}==

# Generate 1000 terms of the Q sequence

print("The 1000th term is: ");

print_i16(Q[1000]);

{{out}}

=={{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|Draco}}==

word n;

q[1] := 1;

writeln();

writeln("The 1000th term is: ", q[1000])

{{out}}

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

=={{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|Fermat}}==

Array qq[n+1];

qq[1] := 1;

for i=1 to 10 do !Hq(i);!' ' od;

{{out}}<pre>

1 1 2 3 3 4 5 5 6 6

=={{header|Forth}}==

{{trans|C}}

: q ( n -- addr ) cells here + ;

999 q @ . cr

flips

{{out}}

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|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>

=={{header|GW-BASIC}}==

20 Q(1) = 1: Q(2) = 1

30 FOR N = 3 TO 1000

70 PRINT Q(N)

80 NEXT N

=={{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}}

=={{header|MAD}}==

VECTOR VALUES FMT = $2HQ(,I4,3H) =,I4*$

PRINT FORMAT FMT, 1000, Q(1000)

{{out}}

=={{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)

=={{header|Modula-2}}==

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

WriteCard(Q[1000],4);

WriteLn();

{{out}}

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

=={{header|MiniScript}}==

Q = function(n)

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

end for

{{out}}

<pre>Q(1) = 1

=={{header|Nim}}==

for n in 2 ..< 100_000: q.add q[n-q[n-1]] + q[n-q[n-2]]

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>

=={{header|Oforth}}==

| 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>

Just to be flash, I also (on the desktop only) calculated the 100 millionth term - the only limiting factor here is the length of Q

(theoretically 402,653,177 on 32 bit).

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">Q</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}</span>

<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"100,000,000th: %,d (%3.2fs)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">q</span><span style="color: #0000FF;">(</span><span style="color: #000000;">100_000_000</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">})</span>

<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

{{out}}

<pre>

=={{header|Picat}}==

println([q(I) : I in 1..10]),

println(q1000=q(1000)),

q(1) = 1.

q(2) = 1.

{{out}}

=={{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>

=={{header|PL/M}}==

BDOS: PROCEDURE (FN, ARG); DECLARE FN BYTE, ARG ADDRESS; GO TO 5; END BDOS;

EXIT: PROCEDURE; CALL BDOS(0,0); END EXIT;

CALL PRINT$NUMBER(Q(1000));

CALL EXIT;

{{out}}

<pre>THE FIRST 10 TERMS ARE: 1 1 2 3 3 4 5 5 6 6

=={{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|Quackery}}==

not if

[ drop size 1+ number$

say " decreasing terms" ]

bailed if

{{out}}

=={{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*/