{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,3,29]],"date-time":"2022-03-29T07:29:32Z","timestamp":1648538972612},"reference-count":10,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T00:00:00Z","timestamp":1611792000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2021,9]]},"abstract":"Abstract<\/jats:title>A set of integers is primitive<\/jats:italic> if it does not contain an element dividing another. Let f<\/jats:italic>(n<\/jats:italic>) denote the number of maximum-size primitive subsets of {1,\u2026,2n<\/jats:italic>}. We prove that the limit \u03b1 = limn\u2192\u221e<\/jats:italic><\/jats:sub>f<\/jats:italic>(n<\/jats:italic>)1\/n<\/jats:italic><\/jats:sup> exists. Furthermore, we present an algorithm approximating \u03b1<\/jats:italic> with (1 + \u03b5<\/jats:italic>) multiplicative error in N<\/jats:italic>(\u03b5<\/jats:italic>) steps, showing in particular that \u03b1<\/jats:italic> \u2248 1.318. Our algorithm can be adapted to estimate the number of all primitive sets in {1,\u2026,n<\/jats:italic>} as well.<\/jats:p>We address another related problem of Cameron and Erd\u0151s. They showed that the number of sets containing pairwise coprime integers in {1,\u2026n<\/jats:italic>} is between ${2^{\\pi (n)}} \\cdot {e^{(1\/2 + o(1))\\sqrt n }}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and ${2^{\\pi (n)}} \\cdot {e^{(2 + o(1))\\sqrt n }}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>. We show that neither of these bounds is tight: there are in fact ${2^{\\pi (n)}} \\cdot {e^{(1 + o(1))\\sqrt n }}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> such sets.<\/jats:p>","DOI":"10.1017\/s0963548321000018","type":"journal-article","created":{"date-parts":[[2021,1,28]],"date-time":"2021-01-28T21:31:10Z","timestamp":1611869470000},"page":"781-795","update-policy":"http:\/\/dx.doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":0,"title":["The number of maximum primitive sets of integers"],"prefix":"10.1017","volume":"30","author":[{"given":"Hong","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e9ter P\u00e1l","family":"Pach","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rich\u00e1rd","family":"Palincza","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2021,1,28]]},"reference":[{"key":"S0963548321000018_ref6","doi-asserted-by":"publisher","DOI":"10.1515\/9783110848632-008"},{"key":"S0963548321000018_ref7","unstructured":"[7] OEIS (1999) A051026: Number of primitive subsequences of {1,2,\u2026,n}. The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A051026"},{"key":"S0963548321000018_ref5","unstructured":"[5] Bishnoi, A. (2017) On a famous pigeonhole problem. Anurag\u2019s Math Blog. https:\/\/anuragbishnoi.wordpress.com\/2017\/11\/02\/on-a-famous-pigeonhole-problem"},{"key":"S0963548321000018_ref2","doi-asserted-by":"publisher","DOI":"10.1017\/fms.2015.22"},{"key":"S0963548321000018_ref4","doi-asserted-by":"publisher","DOI":"10.4171\/JEMS\/802"},{"key":"S0963548321000018_ref9","unstructured":"[9] OEIS (2010) A174094: Number of ways to choose n positive integers less than or equal to 2n such that none of the n integers divides another. The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A174094"},{"key":"S0963548321000018_ref8","unstructured":"[8] OEIS (2003) A084422: Number of subsets of integers 1 through n (including the empty set) containing no pair of integers that share a common factor. The On-line Encyclopedia of Integer Sequences. https:\/\/oeis.org\/A084422"},{"key":"S0963548321000018_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2015-12615-9"},{"key":"S0963548321000018_ref1","first-page":"A25","article-title":"A Cameron and Erd\u0151s conjecture on counting primitive sets","volume":"18","author":"Angelo","year":"2018","journal-title":"Integers"},{"key":"S0963548321000018_ref10","unstructured":"[10] Vijay, S. (2018) On large primitive subsets of {1,2,\u2026,2n}. arXiv:1804.01740"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548321000018","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,6]],"date-time":"2021-08-06T13:36:55Z","timestamp":1628257015000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548321000018\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,28]]},"references-count":10,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,9]]}},"alternative-id":["S0963548321000018"],"URL":"https:\/\/doi.org\/10.1017\/s0963548321000018","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,28]]},"assertion":[{"value":"\u00a9 The Author(s), 2021. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}}]}}