A103300 -id:A103300 - cp's OEIS frontend

A046693 Size of smallest subset S of N={0,1,2,...,n} such that S-S=N, where S-S={abs(i-j) | i,j in S}.

1, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset: 0

John W. Layman

It is easy to show that a(n+1) must be no larger than a(n)+1. Problem: Can a(n+1) ever be smaller than a(n)?
Problem above solved in A103300. a(137) smaller than a(136).
Except for initial term, round(sqrt(3*n + 9/4)) up to n=51. See A308766 for divergences up to n=213. See A326499 for a list of best known solutions.
From Ed Pegg Jr, Jun 23 2019: (Start)
Minimal marks for a sparse ruler of length n.
Minimal vertices in a graceful graph with n edges. (End)

			a(10)=6 since all integers in {0,1,2...10} are differences of elements of {0,1,2,3,6,10}, but not of any 5-element set.
a(17)=7 since all integers in {0,1,2...17} are differences of elements of {0,1,8,11,13,15,17}, but not of any 6-element set.
In other words, {0,1,8,11,13,15,17} is a restricted difference basis w.r.t. A004137(7)=17.

Ed Pegg Jr, Table of n, a(n) for n = 0..213
Thomas Bloom, Problem 170, Erdős Problems.
Andrew Granville and Friedrich Roesler, The set of differences of a given set.
Andrew Granville and Friedrich Roesler, The set of differences of a given set, Amer. Math. Monthly, 106 (1999), 338-344.
John Leech, On the representation of 1, 2, ..., n by differences, J. Lond. Math. Soc. 31 (1956), 160-169.
Ed Pegg Jr, Best known values A046693(n)-round(sqrt(3*n+9/4)) up to 1750.
Aleksi Saarela and Aleksi Vanhatalo, A Connection Between Unbordered Partial Words and Sparse Rulers, arXiv:2408.16335 [math.CO], 2024. See p. 17.
Terence Tao, Erdős problem database, see no. 170.

Cf. A004137, A103300, A308766, A309407, A326499. - Ed Pegg Jr, Sep 14 2019

Prepend[Table[Round[Sqrt[3*n+9/4]]+If[MemberQ[A308766,n],1,0],{n,1,213}],1]

A325857 Number of integer partitions of n such that every orderless pair of distinct parts has a different sum.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 55, 74, 97, 125, 165, 209, 269, 335, 428, 527, 664, 804, 1005, 1210, 1496, 1780, 2186, 2586, 3148, 3698, 4473, 5226, 6279, 7290, 8706, 10067, 11950, 13744, 16242, 18605, 21864, 24942, 29184, 33188, 38651, 43782, 50791, 57402, 66300, 74683, 86026, 96658

Offset: 0

Gus Wiseman, May 31 2019

nonn

			The A000041(14) - a(14) = 10 partitions of 14 not satisfying the condition are:
  (6,5,2,1)
  (6,4,3,1)
  (5,4,3,2)
  (5,4,2,2,1)
  (4,4,3,2,1)
  (5,4,2,1,1,1)
  (4,3,3,2,1,1)
  (4,3,2,2,2,1)
  (4,3,2,2,1,1,1)
  (4,3,2,1,1,1,1,1)

Max Alekseyev, Table of n, a(n) for n = 0..80

The subset case is A196723.
The maximal case is A325878.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A103300, A108917, A143823, A196724, A325853, A325855, A325858, A325859, A325862.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@Plus@@@Subsets[Union[#],{2}]&]],{n,0,30}]

Terms a(31) onward from Max Alekseyev, Sep 23 2023

A353392 Number of compositions of n whose own run-lengths are a consecutive subsequence.

Original entry on oeis.org

1, 1, 0, 0, 1, 2, 2, 2, 2, 8, 12, 16, 20, 35, 46, 59, 81, 109, 144, 202, 282

Offset: 0

Gus Wiseman, May 15 2022

			The a(0) = 0 through a(10) = 12 compositions (empty columns indicated by dots, 0 is the empty composition):
  0  1  .  .  22  122  1122  11221  21122  333     1333
                  221  2211  12211  22112  22113   2233
                                           22122   3322
                                           31122   3331
                                           121122  22114
                                           122112  41122
                                           211221  122113
                                           221121  131122
                                                   221131
                                                   311221
                                                   1211221
                                                   1221121

The non-consecutive version for partitions is A325702.
The non-consecutive version is A353390, ranked by A353402.
The non-consecutive recursive version is A353391, ranked by A353431.
The non-consecutive reverse version is A353403.
The recursive version is A353430.
These compositions are ranked by A353432.
A003242 counts anti-run compositions, ranked by A333489.
A011782 counts compositions.
A169942 counts Golomb rulers, ranked by A333222.
A325676 counts knapsack compositions, ranked by A333223.
A329738 counts uniform compositions, partitions A047966.
A329739 counts compositions with all distinct run-lengths.
Cf. A008965, A032020, A103295, A103300, A114901, A238279, A324572, A325705, A333224, A333755, A351013, A353401.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],#=={}||MemberQ[Join@@Table[Take[#,{i,j}],{i,Length[#]},{j,i,Length[#]}],Length/@Split[#]]&]],{n,0,15}]

A325779 Heinz numbers of integer partitions for which every restriction to a subinterval has a different sum.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 105, 106, 107

Offset: 1

Gus Wiseman, May 20 2019

nonn

First differs from A301899 in having 462.

The enumeration of these partitions by sum is given by A325768.

			Most small numbers are in the sequence. However, the sequence of non-terms together with their prime indices begins:
    4: {1,1}
    8: {1,1,1}
    9: {2,2}
   12: {1,1,2}
   16: {1,1,1,1}
   18: {1,2,2}
   20: {1,1,3}
   24: {1,1,1,2}
   25: {3,3}
   27: {2,2,2}
   28: {1,1,4}
   30: {1,2,3}
   32: {1,1,1,1,1}
   36: {1,1,2,2}
   40: {1,1,1,3}
   44: {1,1,5}
   45: {2,2,3}
   48: {1,1,1,1,2}
   49: {4,4}
   50: {1,3,3}

A subsequence of A005117.

Cf. A000041, A002033, A056239, A103300, A112798, A143823, A169942, A299702, A301899, A325676, A325768, A325769, A325770, A325778.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],UnsameQ@@ReplaceList[primeMS[#],{_,s__,_}:>Plus[s]]&]

A325790 Number of permutations of {1..n} such that every positive integer from 1 to n * (n + 1)/2 is the sum of some circular subsequence.

Original entry on oeis.org

1, 1, 2, 6, 16, 100, 492, 1764, 8592, 71208, 395520, 1679480, 9313128, 72154030, 420375872, 1625653650

Offset: 0

Gus Wiseman, May 23 2019

A circular subsequence is a sequence of consecutive non-overlapping terms where the last and first parts are also considered consecutive. The only circular subsequence of maximum length is the sequence itself (not any rotation of it). For example, the circular subsequences of (2,1,3) are: (), (1), (2), (3), (1,3), (2,1), (3,2), (2,1,3).

			The a(1) = 1 through a(4) = 16 permutations:
  (1)  (1,2)  (1,2,3)  (1,2,3,4)
       (2,1)  (1,3,2)  (1,3,2,4)
              (2,1,3)  (1,4,2,3)
              (2,3,1)  (1,4,3,2)
              (3,1,2)  (2,1,4,3)
              (3,2,1)  (2,3,1,4)
                       (2,3,4,1)
                       (2,4,1,3)
                       (3,1,4,2)
                       (3,2,1,4)
                       (3,2,4,1)
                       (3,4,1,2)
                       (4,1,2,3)
                       (4,1,3,2)
                       (4,2,3,1)
                       (4,3,2,1)

Cf. A002033, A008965, A032153, A103295, A103300, A126796, A325684, A325781, A325788, A325791.

subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Permutations[Range[n]],Range[n*(n+1)/2]==Union[Total/@subalt[#]]&]],{n,0,5}]

weigh(p)={my(b=0); for(i=1, #p, my(s=0,j=i); for(k=1, #p, s+=p[j]; if(!bittest(b,s), b=bitor(b,1<Andrew Howroyd, Aug 16 2019

a(10)-a(12) from Andrew Howroyd, Aug 18 2019

a(13)-a(15) from Bert Dobbelaere, Nov 01 2020

A325991 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different sum.

Original entry on oeis.org

210, 420, 462, 630, 840, 858, 910, 924, 1050, 1155, 1260, 1326, 1386, 1470, 1680, 1716, 1820, 1848, 1870, 1890, 1938, 2100, 2145, 2310, 2470, 2520, 2574, 2622, 2652, 2730, 2772, 2926, 2940, 3150, 3234, 3315, 3360, 3432, 3465, 3570, 3640, 3696, 3740, 3780, 3876

Offset: 1

Gus Wiseman, Jun 02 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

			The sequence of terms together with their prime indices begins:
   210: {1,2,3,4}
   420: {1,1,2,3,4}
   462: {1,2,4,5}
   630: {1,2,2,3,4}
   840: {1,1,1,2,3,4}
   858: {1,2,5,6}
   910: {1,3,4,6}
   924: {1,1,2,4,5}
  1050: {1,2,3,3,4}
  1155: {2,3,4,5}
  1260: {1,1,2,2,3,4}
  1326: {1,2,6,7}
  1386: {1,2,2,4,5}
  1470: {1,2,3,4,4}
  1680: {1,1,1,1,2,3,4}
  1716: {1,1,2,5,6}
  1820: {1,1,3,4,6}
  1848: {1,1,1,2,4,5}
  1870: {1,3,5,7}
  1890: {1,2,2,2,3,4}

The subset case is A196723.
The maximal case is A325878.
The integer partition case is A325857.
The strict integer partition case is A325877.
Heinz numbers of the counterexamples are given by A325991.
Cf. A002033, A056239, A103300, A108917, A112798, A143823, A196724, A325853, A325855, A325858, A325859, A325862, A325992, A325993, A325994.

Select[Range[1000],!UnsameQ@@Plus@@@Subsets[PrimePi/@First/@FactorInteger[#],{2}]&]

A308766 Numbers k such that the minimal mark in a length k sparse ruler is round(sqrt(9 + 12*k)/2) + 1.

Original entry on oeis.org

51, 59, 69, 113, 124, 125, 135, 136, 139, 149, 150, 151, 164, 165, 166, 179, 180, 181, 195, 196, 199, 209, 210, 211

Offset: 1

Ed Pegg Jr, Jun 23 2019

Other sparse rulers in the range length 1 to 213 have round(sqrt(9 + 12*k)/2) minimal marks.
Minimal vertices in k-edge graceful graph = minimal marks in length k sparse ruler.
Minimal marks can be derived from A004137 and using zero-count values in A103300.
Conjecture: Minimal marks k - round(sqrt(9 + 12*k)/2) is always 0 or 1.

P. Luschny, The Perfect Ruler Pyramid (1-101)
P. Luschny, Perfect and Optimal Rulers

Cf. A046693, A004137, A103300, A103294.

A325763 Heinz numbers of integer partitions whose consecutive subsequence-sums cover an initial interval of positive integers.

Original entry on oeis.org

1, 2, 4, 6, 8, 12, 16, 18, 20, 24, 32, 36, 40, 48, 54, 56, 60, 64, 72, 80, 96, 100, 108, 112, 120, 128, 144, 160, 162, 168, 176, 180, 192, 200, 216, 224, 240, 256, 280, 288, 300, 320, 324, 336, 352, 360, 384, 392, 400, 416, 432, 448, 480, 486, 500, 504, 512

Offset: 1

Gus Wiseman, May 19 2019

nonn

The Heinz number of an integer partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k).

The enumeration of these partitions by sum appears to be A002865.

			The sequence of terms together with their prime indices begins:
     1: {}
     2: {1}
     4: {1,1}
     6: {1,2}
     8: {1,1,1}
    12: {1,1,2}
    16: {1,1,1,1}
    18: {1,2,2}
    20: {1,1,3}
    24: {1,1,1,2}
    32: {1,1,1,1,1}
    36: {1,1,2,2}
    40: {1,1,1,3}
    48: {1,1,1,1,2}
    54: {1,2,2,2}
    56: {1,1,1,4}
    60: {1,1,2,3}
    64: {1,1,1,1,1,1}
    72: {1,1,1,2,2}
    80: {1,1,1,1,3}

Cf. A002033, A103295, A103300, A169942, A325676, A325685, A325764, A325765.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],Range[Total[primeMS[#]]]==Union[ReplaceList[primeMS[#],{_,s__,_}:>Plus[s]]]&]

A325789 Number of perfect necklace compositions of n.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 1, 5, 1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1

Offset: 1

Gus Wiseman, May 22 2019

A necklace composition of n is a finite sequence of positive integers summing to n that is lexicographically minimal among all of its cyclic rotations. A circular subsequence is a sequence of consecutive terms where the last and first parts are also considered consecutive. A necklace composition of n is perfect if every positive integer from 1 to n is the sum of exactly one distinct circular subsequence.

			The a(1) = 1 , a(2) = 1, a(3) = 2, a(7) = 3, a(13) = 5, and a(31) = 11 perfect necklace compositions (A = 10, B = 11, C = 12, D = 13, E = 14):
  1  11  12   124      1264           12546D
         111  142      1327           1274C5
              1111111  1462           13278A
                       1723           13625E
                       1111111111111  15C472
                                      17324E
                                      1A8723
                                      1D6452
                                      1E4237
                                      1E5263
                                      1111111111111111111111111111111

Cf. A002033, A008965, A103300, A108917, A126796, A325676, A325679, A325685, A325780, A325782, A325786, A325787, A325789.

neckQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And];
subalt[q_]:=Union[ReplaceList[q,{_,s__,_}:>{s}],DeleteCases[ReplaceList[q,{t___,,u___}:>{u,t}],{}]];
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],neckQ[#]&&Sort[Total/@subalt[#]]==Range[n]&]],{n,10}]

For n > 1, a(n) = A325787(n) + 1.

A325765 Number of integer partitions of n with a unique consecutive subsequence summing to every positive integer from 1 to n.

Original entry on oeis.org

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

Offset: 0

Gus Wiseman, May 20 2019

After a(0) = 1, same as A032741(n + 1) (number of proper divisors of n + 1).

The Heinz numbers of these partitions are given by A325764.

			The a(1) = 1 through a(13) = 3 partitions:
  (1)  (11)  (21)   (1111)  (221)    (111111)  (2221)     (3311)
             (111)          (311)              (4111)     (11111111)
                            (11111)            (1111111)
.
  (22221)      (1111111111)  (33311)        (111111111111)  (2222221)
  (51111)                    (44111)                        (7111111)
  (111111111)                (222221)                       (1111111111111)
                             (611111)
                             (11111111111)

Cf. A000041, A002033, A103295, A103300, A143823, A169942, A325676, A325683, A325768, A325769, A325770.

normQ[m_]:=Or[m=={},Union[m]==Range[Max[m]]];
Table[Length[Select[IntegerPartitions[n],normQ[Total/@Union[ReplaceList[#,{_,s__,_}:>{s}]]]&&UnsameQ@@Total/@Union[ReplaceList[#,{_,s__,_}:>{s}]]&]],{n,0,20}]

cp's OEIS Frontend

A046693 Size of smallest subset S of N={0,1,2,...,n} such that S-S=N, where S-S={abs(i-j) | i,j in S}.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A325857 Number of integer partitions of n such that every orderless pair of distinct parts has a different sum.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A353392 Number of compositions of n whose own run-lengths are a consecutive subsequence.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A325779 Heinz numbers of integer partitions for which every restriction to a subinterval has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325790 Number of permutations of {1..n} such that every positive integer from 1 to n * (n + 1)/2 is the sum of some circular subsequence.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Extensions

A325991 Heinz numbers of integer partitions such that not every orderless pair of distinct parts has a different sum.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A308766 Numbers k such that the minimal mark in a length k sparse ruler is round(sqrt(9 + 12*k)/2) + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

A325763 Heinz numbers of integer partitions whose consecutive subsequence-sums cover an initial interval of positive integers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325789 Number of perfect necklace compositions of n.

Views

Author

Keywords

Comments

Examples