A096858 -id:A096858 - cp's OEIS frontend

A205744 The sequence "u_{n-r}" used by Conway and Guy in the construction of A005318 and A096858.

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

Offset: 1

N. J. A. Sloane, Feb 09 2012

nonn

This is A005318 with the terms A005318(i) repeated iff i is a triangular number.

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. See Table 1, column (3).

Cf. A005318, A096858.

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

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

Original entry on oeis.org

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

N. J. A. Sloane

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]

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.

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

A276661 is the main entry for the distinct subset sums problem.

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

a005318 n = a005318_list !! n
a005318_list = 0 : 1 : zipWith (-)
   (map (* 2) $ tail a005318_list) (map a005318 a083920_list)
-- Reinhard Zumkeller, Feb 12 2012

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

a(n)=if(n<=1,n==1,2*a(n-1)-a(n-1-(sqrtint(8*n-15)+1)\2))

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

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

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

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

A096857 a[n] is the length of terminal cycle of the trajectory of g[x]=sigma(phi(x)) if started at 2^n. Formally identical to A096852, but arguments are shifted by 1 and the iterated functions are different!.

Original entry on oeis.org

1, 1, 2, 1, 3, 2, 2, 1, 2, 2, 6, 2, 1, 6, 2, 1, 2, 3, 11, 11, 2, 2, 15, 15, 18, 18, 18, 18, 12, 12, 12, 1

Offset: 1

Labos Elemer, Jul 19 2004

nonn

Offset=1 in contrast to A096852, where offset=0. Also the iterated functions deviate: A062401 iterated in A096852 and A062402 is repeated here; A096852(n)=A096857(n+1) appears to be true. While cycle-lengths seem identical, the composition of cycles are mostly different!

			n=5:iv=32 list={32,[31,72,60]} length=a(5)=3, while the parallel case of A096852(n)=b(n) is b[4] with [16,24,30] cycle.
Also A096857[11] starts with 2048 ends in 6-cycle: {2048,2047,4123,10890,8928,[9906,9920,12264,10200,6138,6045],9906,..
while A096852[11-1]=6 and the relevant 6-cycle is {1024,1936,3240,2640,[2880,3024,3840,3456,2560,1800],2880,... These are different cycles with identical lengths.
The initial value 146 leads to list with enormous terms.

Cf. A062401, A062402, A096852, A096858.

f[n_] := DivisorSigma[1, EulerPhi[n]]; g[n_] := Block[{l = NestWhileList[f, 2^n, UnsameQ, All]}, -Subtract @@ Flatten[Position[l, l[[ -1]]]]]; Table[ g[n], {n, 25}] (* Robert G. Wilson v, Jul 21 2004 *)

A037254 Triangle read by rows: T(n,k) (n >= 1, 1 <= k< = n) gives number of non-distorting tie-avoiding integer vote weights.

Original entry on oeis.org

1, 1, 2, 2, 3, 4, 3, 5, 6, 7, 6, 9, 11, 12, 13, 11, 17, 20, 22, 23, 24, 22, 33, 39, 42, 44, 45, 46, 42, 64, 75, 81, 84, 86, 87, 88, 84, 126, 148, 159, 165, 168, 170, 171, 172, 165, 249, 291, 313, 324, 330, 333, 335, 336, 337, 330, 495, 579, 621, 643, 654, 660, 663, 665

Offset: 1

N. J. A. Sloane

T(n,1) = T(n,floor(n/2)+1) = A002083(n+2). - Reinhard Zumkeller, Nov 18 2012

			Triangle:
  1;
  1,  2;
  2,  3,  4;
  3,  5,  6,  7;
  6,  9, 11, 12, 13;
  ...

Author?, Solution to Board of Directors Problem, J. Rec. Math., 9 (No. 3, 1977), 240.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.

Reinhard Zumkeller, Rows n = 1..150 of triangle, flattened
M. Klamkin, ed., Problems in Applied Mathematics: Selections from SIAM Review, SIAM, 1990; see pp. 122-123.
G. Kreweras, Sur quelques problèmes relatifs au vote pondéré, [Some problems of weighted voting], Math. Sci. Humaines No. 84 (1983), 45-63.
B. E. Wynne & N. J. A. Sloane, Correspondence, 1976-84
B. E. Wynne & T. V. Narayana, Tournament configuration, weighted voting, and partitioned catalans, Preprint.
Bayard Edmund Wynne, and T. V. Narayana, Tournament configuration and weighted voting, Cahiers du bureau universitaire de recherche opérationnelle, 36 (1981): 75-78.
Solution to Board of Directors Problem, J. Rec. Math., 9 (No. 3, 1977), 240. (Annotated scanned copy)

Row sums give A005254. A002083 is a column. See also A005318, A096858.

Cf. A005255, A062178.

a037254 n k = a037254_tabl !! (n-1) !! (k-1)
a037254_row n = a037254_tabl !! (n-1)
a037254_tabl = map fst $ iterate f ([1], drop 2 a002083_list) where
   f (row, (x:xs)) = (map (+ x) (0 : row), xs)
-- Reinhard Zumkeller, Nov 18 2012

a[1, 1] = 1; a[n_, 1] := a[n, 1] = a[n - 1, Floor[(n + 1)/2]]; a[n_, k_ /; k > 1] := a[n, k] = a[n, 1] + a[n - 1, k - 1]; A037254 = Flatten[ Table[ a[n, k], {n, 1, 11}, {k, 1, n}]] (* Jean-François Alcover, Apr 03 2012, after given recurrence *)

def T(n, k):
    if k==1:
        if n==1: return 1
        else: return T(n - 1, (n + 1)//2)
    return T(n, 1) + T(n - 1, k - 1)
for n in range(1, 12): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Jun 03 2017

T(1,1) = 1;
T(n,1) = T(n-1, floor((n+1)/2));
T(n,k) = T(n,1) + T(n-1,k-1) for k > 1.

More terms from (and formula corrected by) James Sellers, Feb 04 2000

A201052 a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.

Original entry on oeis.org

1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8

Offset: 1

N. J. A. Sloane, Nov 26 2011

In the count 2^c of the cardinality of subsets of a set with cardinality c, the empty set - with sum 0 - is included; 2^c is just the row sum of the c-th row in the Pascal triangle.
Conjecture (confirmed through k=7): a(n)=k for all n in the interval A005318(k) <= n < A005318(k+1). - Jon E. Schoenfield, Nov 28 2013 [Note: This conjecture is false; see A276661 for a counterexample (n=34808712605260918463) in which n is in the interval A005318(66) <= n < A005318(67), yet a(n)=67, not 66. - Jon E. Schoenfield, Nov 05 2016]
A276661 is the main entry for the distinct subset sums problem. - N. J. A. Sloane, Apr 24 2024

			Numbers n and an example of a subset of {1..n} exhibiting the maximum cardinality c=a(n):
1, {1}
2, {1, 2}
3, {1, 2}
4, {1, 2, 4}
5, {1, 2, 4}
6, {1, 2, 4}
7, {3, 5, 6, 7}
8, {1, 2, 4, 8}
9, {1, 2, 4, 8}
10, {1, 2, 4, 8}
11, {1, 2, 4, 8}
12, {1, 2, 4, 8}
13, {3, 6, 11, 12, 13}
14, {1, 6, 10, 12, 14}
15, {1, 6, 10, 12, 14}
16, {1, 2, 4, 8, 16}
17, {1, 2, 4, 8, 16}
18, {1, 2, 4, 8, 16}
For examples of maximum-cardinality subsets at values of n where a(n) > a(n-1), see A096858. - _Jon E. Schoenfield_, Nov 28 2013

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..220 (terms 1..120 from Jon E. Schoenfield)
T. Khovanova, The weight puzzle sequence, SeqFan Mailing list Aug 24 2010
T. Khovanova et al., The weights puzzle
Jon E. Schoenfield, Excel/VBA macro

Cf. A005318, A096858, A275972, A276661.

# is any subset of L uniquely determined by its total weight?
iswts := proc(L)
    local wtset,s,c,subL,thiswt ;
    # the weight sums are to be unique, so sufficient to remember the set
    wtset := {} ;
    # loop over all subsets of weights generated by L
    for s from 1 to nops(L) do
        c := combinat[choose](L,s) ;
        for subL in c do
            # compute the weight sum in this subset
            thiswt := add(i,i=subL) ;
            # if this weight sum already appeared: not a candidate
            if thiswt in wtset then
                return false;
            else
                wtset := wtset union {thiswt} ;
            end if;
        end do:
    end do:
    # All different subset weights were different: success
    return true;
end proc:
# main sequence: given grams 1 to n, determine a subset L
# such that each subset of this subset has a different sum.
wts := proc(n)
    local s,c,L ;
    # select sizes from n (largest size first) down to 1,
    # so the largest is detected first as required by the puzzle.
    for s from n to 1 by -1 do
        # all combinations of subsets of s different grams
        c := combinat[choose]([seq(i,i=1..n)],s) ;
        for L in c do
            # check if any of these meets the requir, print if yes
            # and return
            if iswts(L) then
                print(n,L) ;
                return nops(L) ;
            end if;
        end do:
    end do:
    print(n,"-") ;
end proc:
# loop for weights with maximum n
for n from 1 do
    wts(n) ;
end do: # R. J. Mathar, Aug 24 2010

More terms from Alois P. Heinz, Nov 27 2011

More terms from Jon E. Schoenfield, Nov 28 2013

cp's OEIS Frontend

A205744 The sequence "u_{n-r}" used by Conway and Guy in the construction of A005318 and A096858.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Python

Formula

Extensions

A096857 a[n] is the length of terminal cycle of the trajectory of g[x]=sigma(phi(x)) if started at 2^n. Formally identical to A096852, but arguments are shifted by 1 and the iterated functions are different!.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A037254 Triangle read by rows: T(n,k) (n >= 1, 1 <= k< = n) gives number of non-distorting tie-avoiding integer vote weights.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Python

Formula

Extensions

A201052 a(n) is the maximal number c of integers that can be chosen from {1,2,...,n} so that all 2^c subsets have distinct sums.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A206239 Subsequence A005318(t_n), where t_n is the n-th triangular number (A000217).

Views

Author

Keywords

Comments

Links

Crossrefs