A005318 Conway-Guy sequence: a(n + 1) = 2a(n) - a(n - floor( 1/2 + sqrt(2n) )). (Formerly M1075)

0, 1, 2, 4, 7, 13, 24, 44, 84, 161, 309, 594, 1164, 2284, 4484, 8807, 17305, 34301, 68008, 134852, 267420, 530356, 1051905, 2095003, 4172701, 8311101, 16554194, 32973536, 65679652, 130828948, 261127540, 521203175, 1040311347, 2076449993, 4144588885, 8272623576

Offset

0,3

Comments

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]

References

J. H. Conway and R. K. Guy, Solution of a problem of Erdos, Colloq. Math. 20 (1969), p. 307.

R. K. Guy, Unsolved Problems in Number Theory, C8.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

M. Wald, Problem 1192, Unequal sums, J. Rec. Math., 15 (No. 2, 1983-1984), pp. 148-149.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..3324 (first 301 terms from T. D. Noe)

Tom Bohman, A sum packing problem of Erdos and the Conway-Guy sequence, Proc. AMS 124, (No. 12, 1996), pp. 3627-3636.

P. Borwein and M. J. Mossinghoff, Newman Polynomials with Prescribed Vanishing and Integer Sets with Distinct Subset Sums, Math. Comp., 72 (2003), 787-800.

J. H. Conway & R. K. Guy, Sets of natural numbers with distinct sums, Manuscript.

R. K. Guy, Letter to N. J. A. Sloane, Apr 1975

R. K. Guy, Sets of integers whose subsets have distinct sums, 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.

R. K. Guy, Sets of integers whose subsets have distinct sums, 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)

G. Kreweras, Sur quelques problèmes relatifs au vote pondéré [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.

G. Kreweras, Alvarez Rodriguez, Miguel-Angel, 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] C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347.

G. Kreweras, Alvarez Rodriguez, Miguel-Angel, 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], C. R. Acad. Sci. Paris Ser. I Math. 296 (1983), no. 8, 345-347. (Annotated scanned copy)

W. F. Lunnon, Integer sets with distinct subset-sums, Math. Comp. 50 (1988), 297-320.

M. Wald & N. J. A. Sloane, Correspondence and Attachment, 1987

Formula

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

Mathematica

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 *)

Prog

(PARI) a(n)=if(n<=1, n==1, 2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2))
(PARI) A=[]; /* This is the program above with memoization. */
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
(Haskell)
a005318 n = a005318_list !! n
a005318_list = 0 : 1 : zipWith (-)
   (map (* 2) $ tail a005318_list) (map a005318 a083920_list)
-- Reinhard Zumkeller, Feb 12 2012
(Python)
from sympy import sqrt, floor
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

Crossrefs

Cf. A037254, A096858, A096796, A096824, A205744, A206239, A083920, A003056.

Sequence in context: A255069 A160254 A276661 * A102111 A224704 A265826

Adjacent sequences: A005315 A005316 A005317 * A005319 A005320 A005321

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Sep 21 2000

Status

approved