Nathan McNew - cp's OEIS frontend

User: Nathan McNew

Nathan McNew has authored 5 sequences.

A337125 Length of the longest simple path in the divisor graph of {1,...,n}.

1, 2, 3, 4, 4, 6, 6, 7, 8, 9, 9, 11, 11, 12, 13, 14, 14, 16, 16, 17, 18, 19, 19, 21, 21, 22, 23, 24, 24, 26, 26, 27, 28, 28, 29, 30, 30, 30, 31, 32, 32, 34, 34, 36, 37, 37, 37, 39, 39, 41, 42, 43, 43, 44, 45, 46, 47, 47, 47, 49, 49, 49, 50, 51, 51, 53, 53, 54

Offset: 1

Nathan McNew, Aug 17 2020

a(n) is the length of the longest simple path in the graph on vertices {1,...,n} in which two vertices are connected by an edge if one divides another.
Saias shows that there exist positive constants b and c such that for sufficiently large n, b*n/log n < a(n) < c*n/log n.
The definition can also be formulated as: a(n) is the length of the longest sequence of distinct numbers between 1 and n such that if k immediately follows m, then either k divides m or m divides k. - Peter Luschny, Dec 28 2020
Can be formulated as an optimal subtour problem by introducing a depot node 0 that is adjacent to all other nodes. An integer linear programming formulation is as follows. For {i,j} in E, let binary decision variable x_{i,j} indicate whether edge {i,j} is traversed, and for i in N let binary decision variable y_i indicate whether node i is visited. The objective is to maximize Sum_{i in N \ {0}} y_i. The constraints are Sum_{{i,j} in E: k in {i,j}} x_{i,j} = 2 y_k for all k in N, y_0 = 1, as well as (dynamically generated) generalized subtour elimination constraints Sum_{i in S, j in S: {i,j} in E} x_{i,j} <= Sum_{i in S \ {k}} y_i for all S subset N \ {0} and k in S. - Rob Pratt, Dec 28 2020

			For n = 7, the divisor graph has the path 7-1-4-2-6-3, with length 6, but it is not possible to include all 7 integers into a single path, so a(7) = 6.
Other examples for small n (from _N. J. A. Sloane_, Oct 12 2021):
1: 1 (1)
2: 1-2 (2)
3: 2-1-3 (3)
4: 3-1-2-4 (4)
5: 3-1-2-4 (4)
6: 5-1-3-6-2-4 (6)
8: 5-1-3-6-2-4-8 (7)
9: insert 9 between 1 and 3 (8)
10: add 10 to the start (9)

Andrew Pollington, There is a long path in the divisor graph, Ars Combinatoria 16 (Jan. 1983), B, 303-304.

Rob Pratt, Table of n, a(n) for n = 1..200, the first 75 terms by Nathan McNew.
A. Chadozeau, Sur les partitions en chaînes du graphe divisoriel, Period. Math. Hungar. 56(2), 227-239, 2008.
G. Chartrand, R. Muntean, V. Saenpholphat, and P. Zhang, Which graphs are divisor graphs? Cong. Numerantium 151, 189-200, 2001.
Paul Erdős and Éric Saias, Sur le graphe divisoriel, Acta Arith. 73(2), 189-198, 1995.
Erich Friedman, Divisor chains (Problem of the Month (November 1998)).
Nathan McNew, Counting primitive subsets and other statistics of the divisor graph of {1,2,...,n}, arXiv:1808.04923v2 [math.NT], 2020. Published in: European Journal of Combinatorics, Volume 92, February 2021.
Paul Melotti and Éric Saias, On path partitions of the divisor graph, Acta Arith. 192, 329-339, 2020.
Carl Pomerance, On the longest simple path in the divisor graph, Proc. Southeastern Conf. Combinatorics, Graph Theory, and Computing, Boca Raton, Florida, 1983, Cong. Num. 40 (1983), 291-304.
O. Roeder, Solution to last week’s Riddler Classic, FiveThirtyEight.
E. Saias, Applications des entiers à diviseurs denses, Acta Arithmetica, 83, 3 (1998), 225-240.
E. Saias, Étude du graphe divisoriel 3, Rend. Circ. Mat. Palermo (2) 52 no. 3, 481-488, 2003.
G. Tenenbaum, Sur un problème de crible et ses applications. II. Corrigendum et étude du graphe divisoriel, Ann. Sci. École Norm. Sup. (4) 28 (1995) 115-127.

Cf. A034298 (the smallest possible value of the largest number in a divisor chain of length n).
Cf. A035280 (divisor loops).
Cf. A320536 (least number of paths required to cover the divisor graph).
Cf. A339490 (number of longest paths).
Cf. A339491 (lexicographically earliest longest path).
A347698 gives n - a(n).

If p prime >= 5, a(p-1) = a(p). - Bernard Schott, Dec 28 2020

For 1 <= n <= 33: a(n) = floor(n*5/6) + [(n+1) mod 6 <> 0], where [] are the Iverson brackets. - Peter Luschny, Jan 02 2021

a(74) corrected by Rob Pratt, Dec 28 2020

A309058 Partitions of n with parts having at most 3 distinct magnitudes.

Original entry on oeis.org

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 41, 54, 72, 91, 115, 145, 177, 215, 258, 308, 364, 424, 491, 568, 651, 742, 838, 940, 1065, 1181, 1320, 1454, 1619, 1757, 1957, 2124, 2329, 2510, 2763, 2934, 3244, 3432, 3752, 3964, 4329, 4531, 4965, 5179, 5627, 5872, 6391, 6577, 7178, 7405

Offset: 0

Nathan McNew, Jul 09 2019

nonn

Partitions whose Ferrers diagrams do not contain the pattern 4321 under removal of rows and columns (as defined by Bloom and Saracino).

			a(10) = 41 because all of the 42 integer partitions of 10 count (i.e., 10 = 10, 10 = 9+1 = 8+1+1, etc.), except the partition 10 = 4+3+2+1.

Alois P. Heinz, Table of n, a(n) for n = 0..5000
J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions, arXiv:1808.04238 [math.CO], 2018.
J. Bloom and D. Saracino, Rook and Wilf equivalence of integer partitions, European J. Combin., 71 (2018), 246-267.

Cf. A265250 (partitions of n with parts having at most 2 distinct magnitudes). Sum of A002134, A002133 and A000005.

Cf. A116608.

b:= proc(n, i, t) option remember; `if`(n=0, 1, `if`(i<1, 0,
      `if`(t=1, `if`(irem(n, i)=0, 1, 0)+b(n, i-1, t),
       add(b(n-i*j, i-1, t-`if`(j=0, 0, 1)), j=0..n/i))))
    end:
a:= n-> b(n$2, 3):
seq(a(n), n=0..100);  # Alois P. Heinz, Jul 11 2019

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, If[i < 1, 0, If[t == 1, If[Mod[n, i] == 0, 1, 0] + b[n, i - 1, t], Sum[b[n - i*j, i - 1, t - If[j == 0, 0, 1]], {j, 0, n/i}]]]];
a[n_] := b[n, n, 3];
a /@ Range[0, 100] (* Jean-François Alcover, Feb 27 2020, after Alois P. Heinz *)

G.f.: Sum_{i>=1} x^i/(1-x^i) + Sum_{j=1..i-1} x^(i+j)/((1-x^i)*(1-x^j)) + Sum_{k=1..j-1} x^(i+j+k)/((1-x^i)*(1-x^j)*(1-x^k)).

a(n) = Sum_{k=0..3} A116608(n,k). - Alois P. Heinz, Jul 11 2019

A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.

Original entry on oeis.org

1, 1, 1, 3, 2, 1, 4, 10, 25, 4, 24, 7, 25, 6, 1, 4, 14, 43, 97, 220, 2, 18, 62, 232, 2, 33, 2, 12, 36, 106, 1, 11, 2, 4, 14, 40, 2, 4, 86, 307, 20, 1, 4, 14, 41, 99, 266, 674, 1505, 3510, 7726, 14, 50, 156, 2, 8, 26, 56, 2, 4, 6, 14, 48, 2, 4, 8, 16, 28, 108, 319, 1046, 4, 26, 82, 1, 2

Offset: 0

Nathan McNew, Sep 18 2015

nonn

The sequence A003002 gives the size of the largest subset of the integers up to n that avoids three-term arithmetic progressions. This sequence gives the number of distinct subsets of [1..n] that have that size and are free of three-term arithmetic progressions.

			The largest subset of [1,6] that doesn't have any 3 terms in arithmetic progression has size 4. There are 4 such subsets with this property: {1,2,4,5}, {1,2,5,6}, {1,3,4,6} and {2,3,5,6}, so a(6)=4.

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..140
Fausto A. C. Cariboni, All sets that yield a(n) for n = 4..130., Feb 19 2018.
Janusz Dybizbanski, Sequences containing no 3-term arithmetic progressions, The Electronic Journal of Combinatorics, 19, no. 2 (2012).
Index entries related to non-averaging sequences

Cf. A003002, A065825.

Last elements of rows of A334187.

G:= proc(n, cons, t)
option remember;
local consn, consr;
   if n < t or member({},cons) then return {} fi;
   if t = 0 then return {{}} fi;
   consn, consr:= selectremove(has,cons,n);
   consn:= subs(n=NULL,consn);
   procname(n-1,consr,t) union
      map(`union`,procname(n-1,consr union   consn,t-1),{n});
end proc:
F:= proc(n)
local m,cons,R;
   m:= A003002(n-1);
   cons:= {seq(seq({i,i+j,i+2*j},i=1..n-2*j),j=1..(n-1)/2)};
   R:= G(n,cons,m+1);
   if R = {} then
      A003002(n):= m;
      G(n,cons,m);
   else
      A003002(n):= m+1;
      R
   fi
end proc:
A003002(1):= 1:
a[1]:= 1:
for n from 2 to 40 do
  a[n]:= nops(F(n))
od:
seq(a[i],i=1..40); # Robert Israel, Sep 20 2015

A003002 = Cases[Import["https://oeis.org/A003002/b003002.txt", "Table"], {, }][[All, 2]];
a[n_] := a[n] = Count[Subsets[Range[n], {A003002[[n+1]]}], s_ /; !MatchQ[s, {_, n1_, _, n2_, _, n3_, _} /; n2 - n1 == n3 - n2]];
Table[Print[n, " ", a[n]]; a[n], {n, 0, 25}] (* Jean-François Alcover, May 30 2020 *)

a(25) to a(44) from Robert Israel, Sep 20 2015
a(45) to a(75) from Fausto A. C. Cariboni, Jan 15 2018
a(0)=1 prepended by Alois P. Heinz, May 16 2020

A230490 Size of largest subset of [1..n] containing no three terms in a geometric progression with integer ratio.

Original entry on oeis.org

1, 2, 3, 3, 4, 5, 6, 7, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 16, 17, 18, 19, 20, 21, 22, 23, 23, 24, 25, 26, 26, 27, 28, 29, 30, 31, 32, 33, 33, 34, 35, 36, 36, 37, 38, 39, 39, 40, 41, 42, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 52, 52, 53, 54, 55, 55, 56, 57, 58, 59, 60, 61, 62, 62, 63, 64, 65, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 76, 77, 78, 79, 79, 80, 81, 81, 81

Offset: 1

Nathan McNew, Oct 20 2013

nonn

Trivial lower bound: a(n) >= A013928(n+1). - Charles R Greathouse IV, Oct 20 2013

McNew proves that if n is sufficiently large, then the n-th term is between 0.818n and 0.820n. - Kevin O'Bryant, Aug 17 2015

			The integers [1..9] include the three geometric progressions (1,2,4) (2,4,8) and (1,3,9), which cannot all be precluded with any 1 exclusion, but 2 exclusions suffice. Thus the size of the largest subsets of [1..9] free of integer ratio geometric progressions is 7.

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..152
M. Beiglboeck, V. Bergelson, N. Hindman, and D. Strauss, Multiplicative structures in additively large sets, J. Combin. Theory Ser. A 113 (2006)
N. McNew, On sets of integers which contain no three terms in geometric progression, arXiv:1310.2277 [math.NT], 2013.
M. B. Nathanson and K. O'Bryant, A problem of Rankin on sets without geometric progressions, arXiv:1408.2880 [math.NT], 2014.
K. O'Bryant, Sets of natural numbers with proscribed subsets, arXiv:1410.4900 [math.NT], 2014-2015.

Cf. A003002, A013928, A208746 is similar but also allows progressions with rational ratio, like (4,6,9).

ok(v)=for(i=3,#v,my(k=v[i]);fordiv(core(k,1)[2],d,if(d>1 && setsearch(v,k/d) && setsearch(v,k/d^2), return(0)))); 1
a(n)=my(v=select(k->4*k>n&&issquarefree(k),vector(n,i,i)), u=setminus(vector(n, i,i),v),r,H);for(i=1,2^#u-1,H=hammingweight(i); if(H>r && ok(vecsort(concat(v,vecextract(u,i)),,8)),r=H));#v+r \\ Charles R Greathouse IV, Oct 20 2013

A104886 Sequence A048138, the number of times that a positive integer occurs as the sum of proper divisors, if Goldbach partitions (two odd primes, which account for most of the values) are ignored.

Original entry on oeis.org

0, 1, 1, 0, 2, 1, 2, 0, 1, 0, 1, 1, 2, 1, 2, 0, 1, 0, 2, 1, 2, 0, 1, 0, 1, 0, 1, 0, 1, 2, 2, 1, 1, 0, 1, 0, 1, 0, 3, 1, 2, 1, 2, 0, 2, 0, 1, 1, 2, 0, 0, 0, 2, 1, 1, 2, 1, 0, 1, 0, 2, 1, 3, 1, 1, 0, 1, 0, 1, 0, 1, 2, 3, 0, 3, 0, 1, 0, 1, 2, 1, 0, 1, 0, 1, 1, 0, 1, 2, 0, 2, 0, 1, 0, 0, 2

Offset: 2

Nathan McNew (agreatnate(AT)yahoo.com), Mar 29 2005

nonn

			a(13)=1 because s(27)=1+3+9 and s(35)=1+5+7=13 however 35's factors 3 and 5 are a Goldbach partition, so 35 is not counted.

Cf. A048138, A001065, A061358.

a(n) = number of m such that the sum of the proper divisors of m is n, ignoring m if m is the product of two different odd primes.

cp's OEIS Frontend

User: Nathan McNew

A337125 Length of the longest simple path in the divisor graph of {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A309058 Partitions of n with parts having at most 3 distinct magnitudes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A262347 Number of subsets of [1..n] of maximal size that are free of 3-term arithmetic progressions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A230490 Size of largest subset of [1..n] containing no three terms in a geometric progression with integer ratio.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A104886 Sequence A048138, the number of times that a positive integer occurs as the sum of proper divisors, if Goldbach partitions (two odd primes, which account for most of the values) are ignored.

Views

Author

Keywords

Examples

Crossrefs

Formula