|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
A. G. Price, et al. (Jan 1965). Men only.
|
|
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;
(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
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|