|
%I M1075 #75 Jan 31 2022 01:37:33
%S 0,1,2,4,7,13,24,44,84,161,309,594,1164,2284,4484,8807,17305,34301,
%T 68008,134852,267420,530356,1051905,2095003,4172701,8311101,16554194,
%U 32973536,65679652,130828948,261127540,521203175,1040311347,2076449993,4144588885,8272623576
%N Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) )).
%C Conway and Guy conjecture that the set of k numbers {s_i = a(k) - a(k-i) : 1 <= i <= k} has the property that all its subsets have distinct sums - see Guy's book. These k-sets are the rows of A096858. [This conjecture has apparently now been proved by Bohman. - I. Halupczok (integerSequences(AT)karimmi.de), Feb 20 2006]
%D J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.
%D R. K. Guy, Unsolved Problems in Number Theory, C8.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D M. Wald, Problem 1192, Unequal sums, J. Rec. Math., 15 (No. 2, 1983-1984), pp. 148-149.
%H Alois P. Heinz, <a href="/A005318/b005318.txt">Table of n, a(n) for n = 0..3324</a> (first 301 terms from T. D. Noe)
%H Tom Bohman, <a href="http://dx.doi.org/10.1090/S0002-9939-96-03653-2">A sum packing problem of Erdos and the Conway-Guy sequence</a>, Proc. AMS 124, (No. 12, 1996), pp. 3627-3636.
%H P. Borwein and M. J. Mossinghoff, <a href="http://dx.doi.org/10.1090/S0025-5718-02-01460-6">Newman Polynomials with Prescribed Vanishing and Integer Sets with Distinct Subset Sums</a>, Math. Comp., 72 (2003), 787-800.
%H J. H. Conway & R. K. Guy, <a href="/A005318/a005318_2.pdf">Sets of natural numbers with distinct sums</a>, Manuscript.
%H R. K. Guy, <a href="/A003271/a003271.pdf">Letter to N. J. A. Sloane, Apr 1975</a>
%H R. K. Guy, <a href="http://dx.doi.org/10.1016/S0304-0208(08)73500-X">Sets of integers whose subsets have distinct sums</a>, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982.
%H R. K. Guy, <a href="/A005318/a005318_1.pdf">Sets of integers whose subsets have distinct sums</a>, pp. 141-154 of Theory and practice of combinatorics. Ed. A. Rosa, G. Sabidussi and J. Turgeon. Annals of Discrete Mathematics, 12. North-Holland 1982. (Annotated scanned copy)
%H G. Kreweras, <a href="http://www.numdam.org/item?id=MSH_1983__84__45_0">Sur quelques problèmes relatifs au vote pondéré</a> [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
%H G. Kreweras, Alvarez Rodriguez, Miguel-Angel, <a href="http://gallica.bnf.fr/ark:/12148/bpt6k5543890d/f11.item">Pondération entière minimale de N telle que pour tout k toutes les k-parties de N aient des poids distincts</a>, [Minimal integer weighting of N such that for any k all the k-subsets of N have unequal weights] C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347.
%H G. Kreweras, Alvarez Rodriguez, Miguel-Angel, <a href="/A005318/a005318.pdf">Pondération entière minimale de N telle que pour tout k toutes les k-parties de N aient des poids distincts, [Minimal integer weighting of N such that for any k all the k-subsets of N have unequal weights]</a>, C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347. (Annotated scanned copy)
%H W. F. Lunnon, <a href="http://dx.doi.org/10.1090/S0025-5718-1988-0917837-5">Integer sets with distinct subset-sums</a>, Math. Comp. 50 (1988), 297-320.
%H M. Wald & N. J. A. Sloane, <a href="/A005318/a005318_3.pdf">Correspondence and Attachment, 1987</a>
%F a(n+1) = 2*a(n)-A205744(n), A205744(n) = a(A083920(n)), A083920(n) = n - A002024(n). - _N. J. A. Sloane_, Feb 11 2012
%t a[n_] := a[n] = 2*a[n-1] - a[n - Floor[Sqrt[2]*Sqrt[n-1] + 1/2] - 1]; a[0]=0; a[1]=1; Table[a[n], {n, 0, 33}] (* _Jean-François Alcover_, May 15 2013 *)
%o (PARI) a(n)=if(n<=1,n==1,2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2))
%o (PARI) A=[]; /* This is the program above with memoization. */
%o a(n)=if(n<3, return(n)); if(n>#A, A=concat(A,vector(n-#A)), if(A[n], return(A[n]))); A[n]=2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2) \\ _Charles R Greathouse IV_, Sep 09 2016
%o (Haskell)
%o a005318 n = a005318_list !! n
%o a005318_list = 0 : 1 : zipWith (-)
%o (map (* 2) $ tail a005318_list) (map a005318 a083920_list)
%o -- _Reinhard Zumkeller_, Feb 12 2012
%o (Python)
%o from sympy import sqrt, floor
%o def a(n): return n if n<2 else 2*a(n - 1) - a(n - floor(sqrt(2)*sqrt(n - 1) + 1/2) - 1) # _Indranil Ghosh_, Jun 03 2017
%Y Cf. A037254, A096858, A096796, A096824, A205744, A206239, A083920, A003056.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms from Larry Reeves (larryr(AT)acm.org), Sep 21 2000
|
