login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons 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

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.

Rosetta Code, Man or boy test.

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

Sequence in context: A153148 A091830 A029427 * A277731 A298307 A287002

Adjacent sequences:  A132340 A132341 A132342 * A132344 A132345 A132346

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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 10 02:14 EDT 2020. Contains 333392 sequences. (Running on oeis4.)