{"entities":{"Q703565":{"pageid":705414,"ns":120,"title":"Item:Q703565","lastrevid":48396691,"modified":"2026-01-04T14:38:41Z","type":"item","id":"Q703565","labels":{"en":{"language":"en","value":"On the ultimate complexity of factorials"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2126124"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$0113F8DE-58E7-4AE2-A30D-5DF16F9D3A9A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"67bd2dfc68e1968974ab90f5d9a172cb5f7a65ef","datavalue":{"value":{"text":"On the ultimate complexity of factorials","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q703565$0E026597-4071-447C-B11F-FBA91C02A881","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8b0b67d6ca0cc2edb462d4a9da454de815f3b869","datavalue":{"value":"1079.11060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$C3A8A236-4694-49D8-915B-913C86170BA8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7de71bb3fefe54413deae2199cf0bf98bebc779a","datavalue":{"value":{"entity-type":"item","numeric-id":477182,"id":"Q477182"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$E49D1D7A-1F1C-49BC-B4B6-25A81AADA6A6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$D6AEF727-8AAB-4658-9F25-E2BA3518C4F7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"64fc1bb835ad7d7e19dde657c65db04a5fd1cde0","datavalue":{"value":{"time":"+2005-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q703565$7361BDA0-B955-49CB-A2AB-485035305DB9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"130781e01d3215578b31454fa2793125f26f6364","datavalue":{"value":"Let \\(y\\) be a positive integer. A positive integer is said to be \\(y\\)-smooth, if all of its prime factors are less or equal to \\(y\\). Let  \\[ \\Psi(x,y)= |\\{n\\in\\mathbb{Z}: 0< n\\leq x\\text{ and }n\\text{ is }y\\text{-smooth}\\}| \\]  and \\(L_x[c]= \\exp\\{c\\sqrt{\\log x\\log\\log x}\\}\\). A widely believed conjecture asserts that for any constant \\(a> 0\\), we have  \\[ \\Psi(p+ 1+ 2\\sqrt{p}, L_p[a])- \\Psi(p+ 1- 2\\sqrt{p}, L_p[a])= \\sqrt{p}, L_p[-1/2a+ o(1)]. \\]  In the paper under review, the author assumes that the above conjecture is true and proves that there exist absolute constants \\(c_1\\) and \\(c_2\\) such that for any natural number \\(n\\), a nonzero multiple of \\(n!\\) can be computed by a straight-line program of length at most \\(L_n[c_1]\\).   Furthermore, the straight-line program can be constructed in time \\(L_n[c_2]\\) by a probabilistic Turing machine. Note that the essential part of the proof of this result is relied on Lenstra's elliptic curve factorization method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q703565$70498ED7-68AD-4398-9D90-C6837E9A5C2E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fd716104cf156585f3bce22202c836b7465d3133","datavalue":{"value":"11Y16","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$F44546CE-34E8-4C66-BEDD-6FD6E8B5D72C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$E2DEC591-AE47-40B4-8558-F8B9C0E0A6DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$CF6535BC-BB4B-4C11-85E8-33399ED212E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3dc1a5f8700932516eae3c71f9c6151cfe7c894f","datavalue":{"value":"2126124","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$A2177838-D261-4237-99B2-F2A2809AF6C9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9cf16907441c595935c5f9f06ba100bfb7bcc42","datavalue":{"value":"computational and structural complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q703565$B0F2DC87-E5CF-4EDB-BD1E-1FA499C4552F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"152a3a8a7275b37d6dbe5f1a44038a85372ab00c","datavalue":{"value":"elliptic curve","type":"string"},"datatype":"string"},"type":"statement","id":"Q703565$7001EE1E-697A-41C4-A6BB-01FE0DFB7331","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3184b11a31d7da69732803fd79ace03f08629407","datavalue":{"value":"factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q703565$10F5B8DC-5974-4BAE-A18B-E89E1D7A25BD","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"0c6b4cdaeea731b4d721d1e57817c51ed34c489d","datavalue":{"value":{"entity-type":"item","numeric-id":293716,"id":"Q293716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$8694693D-B578-4E98-BEE2-DA8FC18A5BB4","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$2E9C1327-568B-4E2A-8C53-ECC58E4F7BB5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"328db19cfb68493f91838193f416d59207f55d9d","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2004.06.020","type":"string"},"datatype":"url"},"type":"statement","id":"Q703565$971F74D4-26A7-4AAA-A9E2-9E4773E5030F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6c458877748166d6bf43c03590d7d1f343a55de7","datavalue":{"value":"W2007080245","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$3ACB410B-1B16-40B0-BA95-3E654EB893AE","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e3b36173ca60049f5b57fc77030467db53463adf","datavalue":{"value":{"entity-type":"item","numeric-id":4372496,"id":"Q4372496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$D7A0DB78-0BC3-4C17-8C01-898FA91617CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efc6d224ffe0d7322355df220a9a0a92863a911","datavalue":{"value":{"entity-type":"item","numeric-id":4729768,"id":"Q4729768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$E87A5422-4A92-45D5-8278-F719F1DD6F6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a6077e2e54fd6a54fd3728489a248cfff870e3c","datavalue":{"value":{"entity-type":"item","numeric-id":4331740,"id":"Q4331740"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$D6725F71-FCE2-4F9A-9C31-484EB2A9741B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1b8d8ff623a39233f106f087c5cc8368260f7ab","datavalue":{"value":{"entity-type":"item","numeric-id":1050397,"id":"Q1050397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$DEF21EAC-CA97-43E3-9E5C-A408AA4E03B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"224319da476e0ced5dc6ba342253ea3d1932ce4d","datavalue":{"value":{"entity-type":"item","numeric-id":4425948,"id":"Q4425948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$EBFAFEF7-7A8C-4482-B8AC-702656F7B0F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7a56af73b4b09563c18e7408b1d2d0f81a719580","datavalue":{"value":{"entity-type":"item","numeric-id":1803366,"id":"Q1803366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$4E67952D-CF21-4E70-962B-2AB544081E1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15b1ee3af8823aef6d9d871c6f92a86aee3981d0","datavalue":{"value":{"entity-type":"item","numeric-id":3791262,"id":"Q3791262"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$40A370B9-AA8D-47BD-934D-157D7916BF99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4b70abfa3e8a3fd6d5374422826abb69b72adaa","datavalue":{"value":{"entity-type":"item","numeric-id":4385516,"id":"Q4385516"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$978FFD37-9038-4AC5-8D33-767D0E62C860","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c466b478a595d375651ce05b44b568baf6557516","datavalue":{"value":{"entity-type":"item","numeric-id":1093665,"id":"Q1093665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$275C5AFD-7252-4295-B31E-BB9537C5D081","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"223af1b5acd2d85f22ef4527635b673112804faa","datavalue":{"value":{"entity-type":"item","numeric-id":1255313,"id":"Q1255313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$063643EB-14C2-4111-B03D-517479D04F1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4751aaa35d0d09a6f5b321ce125243942c3fa362","datavalue":{"value":{"entity-type":"item","numeric-id":1913573,"id":"Q1913573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$AD09C277-56D4-427F-83C6-A2BFBA4AFD33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fb380c40c10a7d9d6dec3becc8293ee7708df6a0","datavalue":{"value":{"entity-type":"item","numeric-id":3710637,"id":"Q3710637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$3E5B68BF-17A9-40C3-A5C1-DF38D8F42126","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c8fb2517a72a37de4c3e4a053678d0381153b9c","datavalue":{"value":{"entity-type":"item","numeric-id":1239605,"id":"Q1239605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q703565$4E2F0957-53F0-4E3E-847B-B27660140A74","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"039c0ca27e77099b150432b75346fd850f1a6cb1","datavalue":{"value":"10.1016/J.TCS.2004.06.020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q703565$ED70393F-C00D-44AE-9FFA-EACA5FDCA184","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"223f5fa41e1e05e74b480dfd51630771831c529f","datavalue":{"value":{"entity-type":"item","numeric-id":4418645,"id":"Q4418645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ff8c151433af79a955470cf889bbbccfe96eba7","datavalue":{"value":{"amount":"+0.8521897196769714","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q703565$B2E5A60B-B492-4DCF-B1D3-5D9C3605407D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c3cdef1c38f564df17095b8e4e5c7201a678e61","datavalue":{"value":{"entity-type":"item","numeric-id":5246203,"id":"Q5246203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cce1a07de50b8da50ffc51fc5bcb1b2dd67d9493","datavalue":{"value":{"amount":"+0.7851546406745911","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q703565$80028BC2-4FE4-46DA-A68C-37503E1E1C17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c94076f6a5abefd7eb162009ef3679c701075ba","datavalue":{"value":{"entity-type":"item","numeric-id":3696513,"id":"Q3696513"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"893b9e0fb8bb103a16428bdf5ef0805c94666a75","datavalue":{"value":{"amount":"+0.7524290084838867","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q703565$59D26FB3-7F8E-4593-985C-2C9A35ADAF3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08f9859d96e81debac3994f85ad6015534540f54","datavalue":{"value":{"entity-type":"item","numeric-id":3840155,"id":"Q3840155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70af59b18705982515522cbe87c7d11680b2ef8c","datavalue":{"value":{"amount":"+0.7160863280296326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q703565$EB59CF0B-3969-4FA9-9DBC-E68E8AB3A7DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"315679831b3e864c3146d1c3b4ae4d20ee87bac6","datavalue":{"value":{"entity-type":"item","numeric-id":4287023,"id":"Q4287023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70af59b18705982515522cbe87c7d11680b2ef8c","datavalue":{"value":{"amount":"+0.7160863280296326","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q703565$20EB0DCE-DC1B-4BC8-84DC-8F1637D9BCD6","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:703565","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:703565"}}}}}