login
A132343
Output of Knuth's "man or boy" test for varying k.
2
1, 0, -2, 0, 1, 0, 1, -1, -10, -30, -67, -138, -291, -642, -1446, -3250, -7244, -16065, -35601, -78985, -175416, -389695, -865609, -1922362, -4268854, -9479595, -21051458, -46750171, -103821058, -230560902, -512016658, -1137056340, -2525108865, -5607619809
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
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.
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
Sequence in context: A029427 A353506 A343380 * A277731 A298307 A287002
KEYWORD
sign,easy
AUTHOR
Paolo Bonzini, Nov 08 2007
EXTENSIONS
More terms from Eric M. Schmidt, Jul 20 2013
STATUS
approved