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