cp's OEIS Frontend

A132343 Output of Knuth's "man or boy" test for varying k.

%I A132343 #42 Aug 04 2025 06:29:40
%S A132343 1,0,-2,0,1,0,1,-1,-10,-30,-67,-138,-291,-642,-1446,-3250,-7244,
%T A132343 -16065,-35601,-78985,-175416,-389695,-865609,-1922362,-4268854,
%U A132343 -9479595,-21051458,-46750171,-103821058,-230560902,-512016658,-1137056340,-2525108865,-5607619809
%N A132343 Output of Knuth's "man or boy" test for varying k.
%C A132343 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.
%H A132343 Vincenzo Librandi, <a href="/A132343/b132343.txt">Table of n, a(n) for n = 0..1000</a>
%H A132343 D. E. Knuth (Jul 1964). <a href="http://archive.computerhistory.org/resources/text/algol/algol_bulletin/A17/P24.HTM">Man or boy?</a>.
%H A132343 Charles H. Lindsey (Dec 1988). <a href="http://archive.computerhistory.org/resources/text/algol/algol_bulletin/A52/P43.HTM">Block Structure and Environments</a>.
%H A132343 A. G. Price, et al. (Jan 1965). <a href="http://archive.computerhistory.org/resources/text/algol/algol_bulletin/A19/P23.HTM">Men only</a>.
%H A132343 Rosetta Code, <a href="http://rosettacode.org/wiki/Man_or_boy_test">Man or boy test</a>.
%H A132343 Eric M. Schmidt, <a href="/A132343/a132343.pdf">Recurrences for the man or boy sequence</a>.
%H A132343 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,11,-6,1).
%F A132343 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
%F A132343 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
%t A132343 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 *)
%t A132343 Join[{1,0,-2,0,1},LinearRecurrence[{5,-10,11,-6,1},{0,1,-1,-10,-30},29]] (* _Ray Chandler_, Jul 15 2015 *)
%o A132343 (ALGOL 60)
%o A132343 comment I have written the following simple routine, which may separate the "man-compilers" from the "boy-compilers" - D. E. Knuth.
%o A132343 comment Original ALGOL 60 program by Knuth, different values obtained by modifying the "10" in the last line.
%o A132343 begin
%o A132343 real procedure A (k, x1, x2, x3, x4, x5);
%o A132343 value k; integer k;
%o A132343 begin
%o A132343 real procedure B;
%o A132343 begin k:= k - 1;
%o A132343 B:= A := A (k, B, x1, x2, x3, x4);
%o A132343 end;
%o A132343 if k <= 0 then A:= x4 + x5 else B;
%o A132343 end;
%o A132343 outreal (A (10, 1, -1, -1, 1, 0));
%o A132343 end;
%o A132343 Smalltalk:
%o A132343 Integer>>manOrBoy
%o A132343 ^self x1: [1] x2: [-1] x3: [-1] x4: [1] x5: [0]
%o A132343 Integer>>x1: x1 x2: x2 x3: x3 x4: x4 x5: x5
%o A132343 | b k |
%o A132343 k := self.
%o A132343 b := [ k := k - 1. k x1: b x2: x1 x3: x2 x4: x3 x5: x4 ].
%o A132343 ^k <= 0 ifTrue: [ x4 value + x5 value ] ifFalse: b
%o A132343 Example: '10 manOrBoy' returns -67
%o A132343 (C++)
%o A132343 #include <functional>
%o A132343 #include <iostream>
%o A132343 using cf = std::function<int()>;
%o A132343 int A(int k, cf x1, cf x2, cf x3, cf x4, cf x5)
%o A132343 {
%o A132343     int Aval;
%o A132343     cf B = [&]()
%o A132343     {
%o A132343         int Bval;
%o A132343         --k;
%o A132343         Bval = Aval = A(k, B, x1, x2, x3, x4);
%o A132343         return Bval;
%o A132343     };
%o A132343     if (k <= 0) Aval = x4() + x5(); else B();
%o A132343     return Aval;
%o A132343 }
%o A132343 cf I(int n) { return [=](){ return n; }; }
%o A132343 int main()
%o A132343 {
%o A132343     for (int n=0; n<10; ++n)
%o A132343         std::cout << A(n, I(1), I(-1), I(-1), I(1), I(0)) << ", ";
%o A132343     std::cout << std::endl;
%o A132343 } // translation of Knuth's code, _Eric M. Schmidt_, Jul 20 2013
%o A132343 (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
%K A132343 sign,easy
%O A132343 0,3
%A A132343 _Paolo Bonzini_, Nov 08 2007
%E A132343 More terms from _Eric M. Schmidt_, Jul 20 2013