login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)
18
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 (list; graph; refs; listen; history; text; internal format)
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

T. D. Noe, Table of n, a(n) for n = 0..300

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.

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.

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, Ponderation entiere 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.

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

FORMULA

A005318(n+1) = 2*A005318(n)-A205744(n), A205744(n) = A005318(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

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

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.

License Agreements, Terms of Use, Privacy Policy .

Last modified May 23 02:46 EDT 2017. Contains 286909 sequences.