This site is supported by donations to The OEIS Foundation.

 Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS". Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005318 Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) )). (Formerly M1075) 19

%I M1075

%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

%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 T. D. Noe, <a href="/A005318/b005318.txt">Table of n, a(n) for n = 0..300</a>

%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 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

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