{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:36:19Z","timestamp":1750307779064,"version":"3.41.0"},"reference-count":2,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2007,12,1]],"date-time":"2007-12-01T00:00:00Z","timestamp":1196467200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0444188"],"award-info":[{"award-number":["CCF-0444188"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Commun. Comput. Algebra"],"published-print":{"date-parts":[[2007,12]]},"abstract":"<jats:p>\n            According to an old result of Tur\u00e1n, any (\n            <jats:italic>n<\/jats:italic>\n            + 1)-subset of {1, 2, ..., 2\n            <jats:italic>n<\/jats:italic>\n            } contains a pair of divisible numbers. Ciurea et al. have recently considered a natural algorithmic variant of this classic mathematical result: if the subset is not known, and it is only accessible via a membership oracle, what is the minimum number of questions necessary to identify one such divisible pair? They showed a 4\/3\n            <jats:italic>n<\/jats:italic>\n            --\n            <jats:italic>O<\/jats:italic>\n            (1) lower bound and also designed an algorithm which they conjectured asks no more than 4\/3\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) queries, and therefore would be optimal. We reanalyze the proposed algorithm and prove that it comes close to the conjectured value, in asking no more than (4\/3 + 5\/108)\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>O<\/jats:italic>\n            (1) queries; this corrects an error in the old analysis.\n          <\/jats:p>","DOI":"10.1145\/1358183.1358186","type":"journal-article","created":{"date-parts":[[2008,4,8]],"date-time":"2008-04-08T15:40:00Z","timestamp":1207669200000},"page":"122-124","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["On a query algorithm for a divisibility problem"],"prefix":"10.1145","volume":"41","author":[{"given":"Adrian","family":"Dumitrescu","sequence":"first","affiliation":[{"name":"University of Wisconsin-Milwaukee, WI"}]},{"given":"Guangwu","family":"Xu","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Milwaukee, WI"}]}],"member":"320","published-online":{"date-parts":[[2007,12]]},"reference":[{"issue":"3","key":"e_1_2_1_1_1","first-page":"98","volume":"38","author":"Ciurea S.","year":"2004","unstructured":"S. Ciurea , E. D. Demaine , C. E. P\u01cetrascu , and M. P\u01cetrascu , Finding a divisible pair, ACM SIGSAM Bulletin , 38 ( 3 ) ( 2004 ), 98 -- 100 . S. Ciurea, E. D. Demaine, C. E. P\u01cetrascu, and M. P\u01cetrascu, Finding a divisible pair, ACM SIGSAM Bulletin, 38(3) (2004), 98--100.","journal-title":"Finding a divisible pair, ACM SIGSAM Bulletin"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0015-1","volume-title":"Topics in the Theory of Numbers","author":"Erd\u0151s P.","year":"2003","unstructured":"P. Erd\u0151s and J. Sur\u00e1nyi , Topics in the Theory of Numbers , second edition, Springer , New York , 2003 . P. Erd\u0151s and J. Sur\u00e1nyi, Topics in the Theory of Numbers, second edition, Springer, New York, 2003."}],"container-title":["ACM Communications in Computer Algebra"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1358183.1358186","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1358183.1358186","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:56:04Z","timestamp":1750254964000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1358183.1358186"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12]]},"references-count":2,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,12]]}},"alternative-id":["10.1145\/1358183.1358186"],"URL":"https:\/\/doi.org\/10.1145\/1358183.1358186","relation":{},"ISSN":["1932-2240"],"issn-type":[{"type":"print","value":"1932-2240"}],"subject":[],"published":{"date-parts":[[2007,12]]},"assertion":[{"value":"2007-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}