Hofstadter Figure-Figure sequences: Difference between revisions

<br><br>

 

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

69

Verified</pre>

 

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

Ok</pre>

 

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

 

 

main = do

Output:

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

 

Defining R and S literally:

 

r = scanl (+) 1 s

 

main = do

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

R(10) = 69

1000 integer check ok.</pre>

 

=={{header|Julia}}==

 

'''Functions'''

type FigureFigure{T<:Integer}

r::Array{T,1}

end

end

 

'''Main'''

NR = 40

NS = 960

end

println("cover the entire interval.")

 

{{out}}

</pre>

 

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]

 

let x = cr[cr.high] + cs[cr.high]

cr.add x

cs.add x + 1

 

assert n > 0

while n > cr.len: extendRS()

cr[n - 1]

 

assert n > 0

while n > cs.len: extendRS()

 

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

}

 

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

True

</pre>

 

=={{header|Racket}}==

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

(2 4 5 6 8 9 10 11 13 14)

Checking for first 1000 integers: Test passed</pre>

 

=={{header|REXX}}==

 

Over a third of the program was for verification of the first thousand numbers in the Hofstadter Figure-Figure sequences.

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

 

hofr = list(20)

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

see svect + nl

Output:

<pre>

First 10 values of S:

2 4 5 6 8 9 10 11 13 14

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

[2, 4, 5, 6, 8, 9, 10, 11, 13, 14]

true

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

r(10): 69

true</pre>

 

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

 

0 OK, 0:875</pre>

 

=={{header|VBScript}}==

'Initialize the r and the s arrays.

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

WScript.StdOut.WriteLine

End If

 

{{Out}}

 

Test for the first 1000 integers: Passed!!!

</pre>

 

=={{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]) });

{{out}}

<pre>