login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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
AUTHOR
Paolo Bonzini, Nov 08 2007
EXTENSIONS
More terms from Eric M. Schmidt, Jul 20 2013
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 14:02 EDT 2024. Contains 371254 sequences. (Running on oeis4.)