Hofstadter Figure-Figure sequences: Difference between revisions

{{trans|Python}}

V cS = [2]

print(‘All Integers 1..1000 found OK’)

E

{{out}}

=={{header|Ada}}==

Specifying a package providing the functions FFR and FFS:

function FFR(P: Positive) return Positive;

function FFS(P: Positive) return Positive;

The implementation of the package internally uses functions which generate an array of Figures or Spaces:

type Positive_Array is array (Positive range <>) of Positive;

end FFS;

Finally, a test program for the package, solving the task at hand:

procedure Test_HSS is

exception

when Program_Error => Ada.Text_IO.Put_Line("Test Failed"); raise;

The output of the test program:

=={{header|APL}}==

{{works with|Dyalog APL}}

:Field Private Shared RBuf←,1

∇r←ffr n

:EndIf

∇

{{out}}

=={{header|AutoHotkey}}==

if n=1

return 1

if !(ObjR[A_Index]||ObjS[A_Index])

return A_index

Outputs:<pre>R(1) = 1, 3, 7, 12, 18, 26, 35,...

S(1) = 2, 4, 5, 6, 8, 9, 10,...</pre>

=={{header|AWK}}==

#

# R(1) = 1; S(1) = 2;

}

return S[ n ];

{{out}}

<pre>

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

{{works with|BBC BASIC for Windows}}

FOR i% = 1 TO 10 : PRINT ;FNffr(i%) " "; : NEXT : PRINT

PRINT "First 10 values of S:"

IF R% <= 2*N% V%?R% = 1

NEXT I%

<pre>

First 10 values of R:

=={{header|C}}==

#include <stdlib.h>

puts("\nfirst 1000 ok");

return 0;

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

Creates an IEnumerable for R and S and uses those to complete the task

using System.Collections.Generic;

using System.Linq;

}

}

Output:

<pre>1

{{works with|gcc}}

{{works with|C++|11, 14, 17}}

#include <iostream>

#include <set>

return 0;

{{out}}

R(40):

1 3 7 12 18 26 35 45 56 69 83 98 114 131 150 170 191 213 236 260

49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 68 70

71 72 73 74 75 76 77 78 79 80 81 82 84 85 86 87 88 89 90 91

=={{header|CLU}}==

rep = null

ai = array[int]

int$unparse(i) || " occurs " || int$unparse(occur[i]) || " times.")

end

{{out}}

<pre>R[1..10] = 1 3 7 12 18 26 35 45 56 69

=={{header|CoffeeScript}}==

{{trans|Ruby}}

S = [ null, 2 ]

if int_array[i - 1] != i

throw 'Something\'s wrong!'

{{out}}

As JavaScript.

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

(flet ((seq (i) (make-array 1 :element-type 'integer

:initial-element i

(take #'seq-s 960))

#'<))

{{out}}

<pre>First of R: (1 3 7 12 18 26 35 45 56 69)

=={{header|Cowgol}}==

include "strings.coh";

include "malloc.coh";

if ok != 0 then

print("All numbers 1 .. 1000 found!\n");

{{out}}

=={{header|D}}==

{{trans|Go}}

nothrow static this() {

auto t = iota(1, 41).map!ffr.chain(iota(1, 961).map!ffs);

t.array.sort().equal(iota(1, 1001)).writeln;

{{out}}

<pre>[1, 3, 7, 12, 18, 26, 35, 45, 56, 69]

{{trans|Python}}

(Same output)

struct ffr {

auto t = iota(1, 41).map!ffr.chain(iota(1, 961).map!ffs);

t.array.sort().equal(iota(1, 1001)).writeln;

=={{header|EchoLisp}}==

(+ (FFR (1- n)) (FFS (1- n))))

(remember 'FFR #(0 1)) ;; init cache

(remember 'FFS #(0 2))

{{out}}

(define-macro m-range [a .. b] (range a (1+ b)))

;; checking

(equal? [1 .. 1000] (list-sort < (append (map FFR [1 .. 40]) (map FFS [1 .. 960]))))

=={{header|Euler Math Toolbox}}==

>function RSstep (r,s) ...

$ n=cols(r);

>all(sort(r[1:40]|s[1:960])==(1:1000))

1

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

===The function===

// Populate R and S with values of Hofstadter Figure Figure sequence. Nigel Galloway: August 28th., 2020

let fF q=let R,S=Array.zeroCreate<int>q,Array.zeroCreate<int>q

|i->S.[n]<-i+1; fN (n+1) (g+1)

fN 1 1

===The Tasks===

let ffr,ffs=fF 960

ffr|>Seq.take 10|>Seq.iter(printf "%d "); printfn ""

let N=Array.concat [|ffs;(Array.take 40 ffr)|] in printfn "Unique values=%d Minimum value=%d Maximum Value=%d" ((Array.distinct N).Length)(Array.min N)(Array.max N)

{{out}}

<pre>

===Unbounded n?===

n is bounded in this implementation because it is an signed 32 integer. Within such limit the 10 millionth value will have to be sufficiently unbounded. It can be found in 43 thousandths of sec.

let ffr,ffs=fF 10000000

printfn "%d\n%d (Array.last ffr) (Array.last ffs)

1584961838

10004416

=={{header|Factor}}==

We keep lists S and R, and increment them when necessary.

SYMBOL: R V{ 1 } R set

: ffr ( n -- R(n) )

dup R get length - inc-SR

{ 1 3 7 12 18 26 35 45 56 69 }

( scratchpad ) 40 iota [ 1 + ffr ] map 960 iota [ 1 + ffs ] map append 1000 iota 1 v+n set= .

=={{header|FreeBASIC}}==

{{trans|BBC BASIC}}

if n = 1 then return 1

dim as integer i, j, r=1, s=1, v(1 to 2*n+1)

next i

{{out}}<pre>

R S

=={{header|Go}}==

import "fmt"

}

fmt.Println("task 4: PASS")

{{out}}

<pre>

The following defines two mutually recursive generators without caching results. Each generator will end up dragging a tree of closures behind it, but due to the odd nature of the two series' growth pattern, it's still a heck of a lot faster than the above method when producing either series in sequence.

import "fmt"

}

fmt.Println(sum)

=={{header|Haskell}}==

-- Functions by Reinhard Zumkeller

print $ ffr <$> [1 .. 10]

let i1000 = sort (fmap ffr [1 .. 40] ++ fmap ffs [1 .. 960])

Output:

<pre>[1,3,7,12,18,26,35,45,56,69]

Defining R and S literally:

r :: [Int]

print (take 10 s)

putStr "test 1000: "

output:

<pre>

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

procedure main()

}

}

{{libheader|Icon Programming Library}}

=={{header|J}}==

S=: 0 2 4

FF=: 3 :0

)

ffr=: { 0 {:: FF@(>./@,)

Required examples:

1 3 7 12 18 26 35 45 56 69

(1+i.1000) -: /:~ (ffr 1+i.40), ffs 1+i.960

=={{header|Java}}==

'''Code:'''

class Hofstadter

System.out.println("Done");

}

'''Output:'''

=={{header|JavaScript}}==

{{trans|Ruby}}

var S = [null, 2];

throw "Something's wrong!"

} else { console.log("1000 integer check ok."); }

Output:

<pre>R(1) = 1

to accomplish the specific tasks.

# input: {r,s}

| (.r[1:41] + .s[1:961] | sort) == [range(1;1001)] ) ;

{{out}}

<pre>

'''Functions'''

type FigureFigure{T<:Integer}

r::Array{T,1}

end

end

'''Main'''

NR = 40

NS = 960

end

println("cover the entire interval.")

{{out}}

=={{header|Kotlin}}==

Translated from Java.

fun ffs(n: Int) = get(0, n)[n - 1]

indices.forEach { println("Integer $it either in both or neither set") }

println("Done")

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

2. No maximum value for n should be assumed.

ffr[j_] := Module[{R = {1}, S = 2, k = 1},

Do[While[Position[R, S] != {}, S++]; k = k + S; S++;

ffs[j_] := Differences[ffr[j + 1]]

3. Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69

ffr[10]

(* out *)

{1, 3, 7, 12, 18, 26, 35, 45, 56, 69}

4. Calculate and show that the first 40 values of ffr plus the first 960 values of ffs include all the integers from 1 to 1000 exactly once.

t = Sort[Join[ffr[40], ffs[960]]];

(* out *)

True

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

2. No maximum value for n should be assumed.

t = [1,0];

T = 1;

printf('Sequence S:\n'); disp(S);

end;

3. Calculate and show that the first ten values of R are: 1, 3, 7, 12, 18, 26, 35, 45, 56, and 69

=={{header|Nim}}==

var cs = @[2]

if all: echo "All Integers 1..1000 found OK"

Output:

<pre>/home/deen/git/nim-unsorted/hofstadter

=={{header|Oforth}}==

ListBuffer new 1 over add R put

: ffs(n)

while ( S at size n < ) [ buildnext ]

Output :

Then we go through the first 1000 outputs, mark those which are seen, then check if all values in the range one through one thousand were seen.

use strict;

use warnings;

print "These were duplicated: @dupped\n";

}

=={{header|Phix}}==

Initialising such that length(S)>length(F) simplified things significantly.

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

<span style="color: #004080;">sequence</span> <span style="color: #000000;">F</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;">3</span><span style="color: #0000FF;">,</span><span style="color: #000000;">7</span><span style="color: #0000FF;">},</span>

<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"some error!\n"</span><span style="color: #0000FF;">)</span>

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

{{out}}

<pre>

=={{header|PicoLisp}}==

(de ffr (N)

(inc 'S)

(inc '*RNext) )

Test:

-> (1 3 7 12 18 26 35 45 56 69)

(range 1 1000)

(sort (conc (mapcar ffr (range 1 40)) (mapcar ffs (range 1 960)))) )

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

declare n fixed binary (31);

declare v(2*n+1) bit(1);

end;

return (r);

Output:

<pre>

602 640 679 719 760 802 845 889 935 982

</pre>

declare n fixed binary (31);

declare v(2*n+1) bit(1);

end;

return (s);

Output of first 960 values:

<pre>

</pre>

Verification using the above procedures:

Dcl t(1000) Bit(1) Init((1000)(1)'0'b);

put skip list ('Verification that the first 40 FFR numbers and the first');

end;

if all(t = '1'b) then put skip list ('passed test');

Output:

<pre>

CHR is a programming language created by '''Professor Thom Frühwirth'''.<br>

Works with SWI-Prolog and module '''chr''' written by '''Tom Schrijvers''' and '''Jan Wielemaker'''

:- chr_constraint ffr/2, ffs/2, hofstadter/1,hofstadter/2.

hofstadter(N), ffr(N1, _R), ffs(N1, _S) ==> N1 < N, N2 is N1 +1 | ffr(N2,_), ffs(N2,_).

Output for first task :

<pre> ?- hofstadter(10), bagof(ffr(X,Y), find_chr_constraint(ffr(X,Y)), L).

Code for the second task

hofstadter(960),

% fetch the values of ffr

% to remove all pending constraints

fail.

Output for second task

<pre> ?- hofstadter.

=={{header|Python}}==

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

try:

print("All Integers 1..1000 found OK")

else:

;Output:

===Alternative===

cS = [2]

# the fact that we got here without a key error

===Using cyclic iterators===

{{trans|Haskell}}

Defining R and S as mutually recursive generators. Follows directly from the definition of the R and S sequences.

def R():

# perf test case

{{out}}

<pre>R: [1, 3, 7, 12, 18, 26, 35, 45, 56, 69]

=={{header|R}}==

Global variables aren't idiomatic R, but this is otherwise an ideal task for the language. Comments aside, this is easily one of the shortest solutions on this page. This is mostly due to how R treats most things as a vector. For example, rValues starts out as the number 1, but repeatedly has new values appended to it without much ceremony.

sValues <- 2

ffr <- function(n)

This gives an output of length 960, which clearly cannot contain 1000 different values.

#Presumably, the task wants us to append rValues[1:40] and sValues[1:960].

{{out}}

<pre>> print(rValues)

We store the values of r and s in hash-tables. The first values are added by hand. The procedure extend-r-s! adds more values.

(define r-cache (make-hash '((1 . 1) (2 . 3) (3 . 7))))

(define offset (- s-count last-r))

(for ([val (in-range (add1 last-r) new-r)])

The functions ffr and ffs simply retrieve the value from the hash table if it exist, or call extend-r-s until they are long enought.

(hash-ref r-cache n (lambda () (extend-r-s!) (ffr n))))

(define (ffs n)

Tests:

(displayln (map ffs (list 1 2 3 4 5 6 7 8 9 10)))

i))

"Test passed"

'''Sample Output:'''

(formerly Perl 6)

{{works with|Rakudo|2018.03}}

my %s = 1 => 2;

say @ffr[^10];

Output:

<pre>

This REXX version is over &nbsp; '''15,000%''' &nbsp; faster than REXX version 2.

parse arg x top bot . /*obtain optional arguments from the CL*/

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

return s.n /*return S.n value to the invoker. */

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

To see the talk section about this REXX program's timings, click here: &nbsp; &nbsp; [http://rosettacode.org/wiki/Talk:Hofstadter_Figure-Figure_sequences#timings_for_the_REXX_solutions timings for the REXX solutions]. <br>

===Version 2 from PL/I ===

* 21.11.2012 Walter Pachl transcribed from PL/I

**********************************************************************/

if r <= 2*n then v.r = 1

end

{{out}}

<pre>Verification that the first 40 FFR numbers and the first

=={{header|Ring}}==

# Project : Hofstadter Figure-Figure sequences

svect = left(svect, len(svect) - 1)

see svect + nl

Output:

<pre>

=={{header|Ruby}}==

{{trans|Tcl}}

$s = [nil, 2]

assert_equal(rs_values, Set.new( 1..1000 ))

end

outputs

===Using cyclic iterators===

{{trans|Python}}

y << n = 1

S.each{|s_val| y << n += s_val}

p S.take(10)

p (R.take(40)+ S.take(960)).sort == (1..1000).to_a

{{out}}

<pre>

=={{header|Rust}}==

use std::collections::HashMap;

assert_eq!(f1000, s960, "Does NOT match");

}

{{out}}

<pre>

=={{header|Scala}}==

{{trans|Go}}

import scala.collection.mutable.ListBuffer

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

println((1 to 1000).toList.filterNot(((1 to 40).map(ffr(_))++(1 to 960).map(ffs(_))).contains)==List())

Output:

<pre>r(1): 1

=={{header|Sidef}}==

{{trans|Perl}}

var s = [nil, 2]

say "These were missed: #{missed}"

say "These were duplicated: #{dupped}"

{{out}}

<pre>

=={{header|Tcl}}==

{{tcllib|struct::set}}

package require struct::set

}

puts "set sizes: [struct::set size $numsInSeq] vs [struct::set size $numsRS]"

Output:

<pre>

=={{header|uBasic/4tH}}==

Note that uBasic/4tH has ''no'' dynamic memory facilities and only ''one single array'' of 256 elements. So the only way to cram over a 1000 values there is to use a bitmap. This bitmap consists of an '''R''' range and an '''S''' range. In each range, a bit represents a positional value (bit 0 = "1", bit 1 = "2", etc.). The '''R'''(x) and '''S'''(x) functions simply count the number of bits set they encountered. To determine whether all integers between 1 and 1000 are complementary, both ranges are ''XOR''ed, which would result in a value other than 2³¹-1 if there were any discrepancies present. An extra check determines if there are exactly 40 '''R''' values.

Proc _SetBitS(2) ' Set the first S value

_GetBitS Param(1) ' Return bit n-1 in S-bitmap

a@ = a@ - 1

{{out}}

<pre>Creating bitmap, wait..

=={{header|VBA}}==

Dim R As New Collection

Dim S As New Collection

Debug.Print "The first 40 values of ffr plus the first 960 values of ffs "

Debug.Print "include all the integers from 1 to 1000 exactly once is "; Format(x.Count = 0)

<pre>The first ten values of R are:

1 3 7 12 18 26 35 45 56 69

=={{header|VBScript}}==

'Initialize the r and the s arrays.

Set r = CreateObject("System.Collections.ArrayList")

WScript.StdOut.WriteLine

End If

{{Out}}

=={{header|Wren}}==

{{trans|Go}}

var s = [0, 2]

var allPresent = present.skip(1).all { |i| i == true }

System.print("\nThe first 40 values of ffr plus the first 960 values of ffs")

{{out}}

=={{header|zkl}}==

var n=0, Rs=L(0,1), S=2;

if(True==reset){ n=0; Rs=L(0,1); S=2; return(); }

return(n+=1,R,S);

}

{{out}}

<pre>

L(1,3,7,12,18,26,35,45,56,69)

</pre>

sink:=(0).pump(40,List, 'wrap(ns){ T(Void.Write,Void.Write,genRS()[1,*]) });

sink= (0).pump(960-40,sink,'wrap(ns){ T(Void.Write,genRS()[2]) });

(sink.sort()==[1..1000].pump(List)) // [1..n].pump(List)-->(1,2,3...)

{{out}}

<pre>