OFFSET
0,3
COMMENTS
The man or boy test was proposed by computer scientist D. E. Knuth as a means of evaluating implementations of the ALGOL 60 programming language. The aim of the test was to distinguish compilers that correctly implemented "recursion and non-local references" from those that did not.
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
D. E. Knuth (Jul 1964). Man or boy?.
Charles H. Lindsey (Dec 1988). Block Structure and Environments.
A. G. Price, et al. (Jan 1965). Men only.
Rosetta Code, Man or boy test.
Eric M. Schmidt, Recurrences for the man or boy sequence.
Index entries for linear recurrences with constant coefficients, signature (5,-10,11,-6,1).
FORMULA
a(5)=0, a(6)=1, a(7)=-1, a(8)=-10, a(9)=-30, a(n)=a(n-5)-6*a(n-4)+11*a(n-3)-10*a(n-2)+5*a(n-1) for n >= 10. - Markus Jarderot (mizardx(AT)gmail.com), Jun 05 2010
G.f.: (2*x^9-11*x^8+15*x^7+x^6-16*x^5+13*x^4+x^3-8*x^2+5*x-1) / ((x-1)*(x^4-5*x^3+6*x^2-4*x+1)). - Joerg Arndt, Jul 21 2013
MATHEMATICA
CoefficientList[Series[(2 x^9 - 11 x^8 + 15 x^7 + x^6 - 16 x^5 + 13 x^4 + x^3 - 8 x^2 + 5 x - 1) / ((x - 1) (x^4 - 5 x^3 + 6 x^2 - 4 x + 1)), {x, 0, 40}], x] ( * Vincenzo Librandi, Jul 21 2013 *)
Join[{1, 0, -2, 0, 1}, LinearRecurrence[{5, -10, 11, -6, 1}, {0, 1, -1, -10, -30}, 29]] (* Ray Chandler, Jul 15 2015 *)
PROG
I have written the following simple routine, which may separate the "man-compilers" from the "boy-compilers" - D. E. Knuth.
Original ALGOL 60 program by Knuth, different values obtained by modifying the "10" in the last line.
begin
real procedure A (k, x1, x2, x3, x4, x5);
value k; integer k;
begin
real procedure B;
begin k:= k - 1;
B:= A := A (k, B, x1, x2, x3, x4);
end;
if k <= 0 then A:= x4 + x5 else B;
end;
outreal (A (10, 1, -1, -1, 1, 0));
end;
Smalltalk:
Integer>>manOrBoy
^self x1: [1] x2: [-1] x3: [-1] x4: [1] x5: [0]
Integer>>x1: x1 x2: x2 x3: x3 x4: x4 x5: x5
| b k |
k := self.
b := [ k := k - 1. k x1: b x2: x1 x3: x2 x4: x3 x5: x4 ].
^k <= 0 ifTrue: [ x4 value + x5 value ] ifFalse: b
Example: '10 manOrBoy' returns -67
(C++)
#include <functional>
#include <iostream>
using cf = std::function<int()>;
int A(int k, cf x1, cf x2, cf x3, cf x4, cf x5)
{
int Aval;
cf B = [&]()
{
int Bval;
--k;
Bval = Aval = A(k, B, x1, x2, x3, x4);
return Bval;
};
if (k <= 0) Aval = x4() + x5(); else B();
return Aval;
}
cf I(int n) { return [=](){ return n; }; }
int main()
{
for (int n=0; n<10; ++n)
std::cout << A(n, I(1), I(-1), I(-1), I(1), I(0)) << ", ";
std::cout << std::endl;
} // translation of Knuth's code, Eric M. Schmidt, Jul 20 2013
(PARI) Vec(O(x^66)+(2*x^9-11*x^8+15*x^7+x^6-16*x^5+13*x^4+x^3-8*x^2+5*x-1)/((x-1)*(x^4-5*x^3+6*x^2-4*x+1))) \\ Joerg Arndt, Jul 21 2013
CROSSREFS
KEYWORD
sign,easy
AUTHOR
Paolo Bonzini, Nov 08 2007
EXTENSIONS
More terms from Eric M. Schmidt, Jul 20 2013
STATUS
approved