{"group":{"id":1,"name":"Community","lockable":false,"created_at":"2012-01-18T18:02:15.000Z","updated_at":"2026-04-16T00:12:35.000Z","description":"Problems submitted by members of the MATLAB Central community.","is_default":true,"created_by":161519,"badge_id":null,"featured":false,"trending":false,"solution_count_in_trending_period":0,"trending_last_calculated":"2026-04-16T00:00:00.000Z","image_id":null,"published":true,"community_created":false,"status_id":2,"is_default_group_for_player":false,"deleted_by":null,"deleted_at":null,"restored_by":null,"restored_at":null,"description_opc":null,"description_html":null,"published_at":null},"problems":[{"id":2126,"title":"Split bread like the Pharaohs - Egyptian fractions and greedy algorithm","description":"How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\r\nEgyptian fraction is writing any rational number p/q in terms of unity fractions;\r\ne.g.  \r\n\r\n        3/4 = 1/2 + 1/4, OR \r\n            = 1/3 + 1/4 + 1/6\r\n\r\n      13/48 = 1/4 + 1/48\r\nWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\r\n    i.e.   egyptian_fraction( 13, 48) should return [4,48],\r\nYou can use simple greedy algorithm or alternatives.\r\nReferences\r\nhttp://en.wikipedia.org/wiki/Egyptian_fraction\r\nAMS blog post by Tyler Clark (@tylermath12) http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\r\nBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\r\nP.S: Updated test suite to check for proper solutions only","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 460.333px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 230.167px; transform-origin: 407px 230.167px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 379.5px 8px; transform-origin: 379.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eHow would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 242px 8px; transform-origin: 242px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eEgyptian fraction is writing any rational number p/q in terms of unity fractions;\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 122.6px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404px 61.3px; transform-origin: 404px 61.3px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 24px 8.5px; tab-size: 4; transform-origin: 24px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003ee.g.  \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 8.5px; tab-size: 4; transform-origin: 0px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 112px 8.5px; tab-size: 4; transform-origin: 112px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e        3/4 = 1/2 + 1/4, OR \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 116px 8.5px; tab-size: 4; transform-origin: 116px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e            = 1/3 + 1/4 + 1/6\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 8.5px; tab-size: 4; transform-origin: 0px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 96px 8.5px; tab-size: 4; transform-origin: 96px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e      13/48 = 1/4 + 1/48\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 383.5px 8px; transform-origin: 383.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 20.4333px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 236px 8.5px; tab-size: 4; transform-origin: 236px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; perspective-origin: 180px 8.5px; transform-origin: 180px 8.5px; \"\u003e    i.e.   egyptian_fraction( 13, 48) should \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); perspective-origin: 52px 8.5px; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); transform-origin: 52px 8.5px; \"\u003ereturn [4,48]\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; perspective-origin: 4px 8.5px; transform-origin: 4px 8.5px; \"\u003e,\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 165px 8px; transform-origin: 165px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eYou can use simple greedy algorithm or alternatives.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 41px 8px; transform-origin: 41px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eReferences\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003col style=\"block-size: 61.3px; counter-reset: list-item 0; font-family: Helvetica, Arial, sans-serif; list-style-type: decimal; margin-block-end: 20px; margin-block-start: 10px; margin-bottom: 20px; margin-top: 10px; perspective-origin: 391px 30.65px; transform-origin: 391px 30.65px; margin-top: 10px; margin-bottom: 20px; \"\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttp://en.wikipedia.org/wiki/Egyptian_fraction\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/li\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 142px 8px; transform-origin: 142px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eAMS blog post by Tyler Clark (@tylermath12)\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttp://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/li\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 347px 8px; transform-origin: 347px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 178px 8px; transform-origin: 178px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eP.S: Updated test suite to check for proper solutions only\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function denoms = egyptian_fraction(p,q)\r\n  denoms = [];\r\n  \r\n  if ( p == 1 )\r\n     denoms(end+1) = q;\r\n     return;\r\n  end\r\n  % treat other cases..\r\nend","test_suite":"%%\r\n% Updated test suite to remove trivial solutions;\r\n\r\n%%\r\n Vmin = 13; Vmax = 48;\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n assert(isequal(arr, [4 48]))\r\n \r\n%%\r\n Vmin = 3; Vmax = 4;\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n assert(isequal(arr, [2 4]) || isequal(arr, [3 4 6]))\r\n \r\n%%\r\n Vmin = 2;\r\n in = primes(20);\r\n Vmax = in(randi(numel(in)));\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n l=lcm(arr(1),arr(2));\r\n for k=3:numel(arr)\r\n     l=lcm(l,arr(k));\r\n end\r\n assert(isequal(sum(arr),sum(l./arr)/(Vmax/l)))\r\n \r\n \r\n%%\r\n% Small\r\n Vmin = 10; Vmax = 55;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% Pie\r\n Vmin = 113; Vmax = 355;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% Ramanujan\r\n Vmin = 1023; Vmax = 1729;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% E\r\n Vmin = 27; Vmax = 183;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n","published":true,"deleted":false,"likes_count":3,"comments_count":5,"created_by":3378,"edited_by":223089,"edited_at":"2023-03-29T14:08:28.000Z","deleted_by":null,"deleted_at":null,"solvers_count":96,"test_suite_updated_at":"2023-03-29T14:08:28.000Z","rescore_all_solutions":false,"group_id":38,"created_at":"2014-01-19T06:15:39.000Z","updated_at":"2026-03-31T17:38:29.000Z","published_at":"2014-01-19T17:44:14.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eHow would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEgyptian fraction is writing any rational number p/q in terms of unity fractions;\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[e.g.  \\n\\n        3/4 = 1/2 + 1/4, OR \\n            = 1/3 + 1/4 + 1/6\\n\\n      13/48 = 1/4 + 1/48]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[    i.e.   egyptian_fraction( 13, 48) should return [4,48],]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYou can use simple greedy algorithm or alternatives.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eReferences\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttp://en.wikipedia.org/wiki/Egyptian_fraction\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAMS blog post by Tyler Clark (@tylermath12)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttp://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eP.S: Updated test suite to check for proper solutions only\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"},{"id":2838,"title":"Optimum Egyptian Fractions","description":"Following problem was inspired by \u003chttp://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm this problem\u003e and \u003chttp://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542 that comment\u003e.\r\n\r\nGiven fraction numerator _A_ and denominator _B_, find denominators _C_ for \u003chttps://en.wikipedia.org/wiki/Egyptian_fraction Egyptian fraction\u003e. The goal of this problem is to minimize the sum of the list.\r\n\r\nExample:\r\n  \r\n   A = 16;\r\n   B = 63;\r\n   % 16/63 == 1/7 + 1/9\r\n   C = [7, 9];\r\n\r\n_C_ may be _[4, 252]_ or _[5, 19, 749, 640395]_ or _[5, 27, 63, 945]_ or _[6, 12, 252]_ or _[7, 9]_ or almost any else of infinite more other options. The best one is _[7, 9]_ with sum 16.\r\n\r\n* You may assume _A\u003cB_,\r\n* Your score will be based on sum of answers,\r\n* No cheating, please,\r\n* While greedy algorithm usually solves this problem, score may not be satisfying,\r\n* Class of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\r\n* I'm open for proposals to improve test, i.e. verification of output which is far from perfect.","description_html":"\u003cp\u003eFollowing problem was inspired by \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm\"\u003ethis problem\u003c/a\u003e and \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542\"\u003ethat comment\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eGiven fraction numerator \u003ci\u003eA\u003c/i\u003e and denominator \u003ci\u003eB\u003c/i\u003e, find denominators \u003ci\u003eC\u003c/i\u003e for \u003ca href = \"https://en.wikipedia.org/wiki/Egyptian_fraction\"\u003eEgyptian fraction\u003c/a\u003e. The goal of this problem is to minimize the sum of the list.\u003c/p\u003e\u003cp\u003eExample:\u003c/p\u003e\u003cpre\u003e   A = 16;\r\n   B = 63;\r\n   % 16/63 == 1/7 + 1/9\r\n   C = [7, 9];\u003c/pre\u003e\u003cp\u003e\u003ci\u003eC\u003c/i\u003e may be \u003ci\u003e[4, 252]\u003c/i\u003e or \u003ci\u003e[5, 19, 749, 640395]\u003c/i\u003e or \u003ci\u003e[5, 27, 63, 945]\u003c/i\u003e or \u003ci\u003e[6, 12, 252]\u003c/i\u003e or \u003ci\u003e[7, 9]\u003c/i\u003e or almost any else of infinite more other options. The best one is \u003ci\u003e[7, 9]\u003c/i\u003e with sum 16.\u003c/p\u003e\u003cul\u003e\u003cli\u003eYou may assume \u003ci\u003eA\u0026lt;B\u003c/i\u003e,\u003c/li\u003e\u003cli\u003eYour score will be based on sum of answers,\u003c/li\u003e\u003cli\u003eNo cheating, please,\u003c/li\u003e\u003cli\u003eWhile greedy algorithm usually solves this problem, score may not be satisfying,\u003c/li\u003e\u003cli\u003eClass of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\u003c/li\u003e\u003cli\u003eI'm open for proposals to improve test, i.e. verification of output which is far from perfect.\u003c/li\u003e\u003c/ul\u003e","function_template":"function C = egyptian(A,B)\r\n  A = uint64(A);\r\n  B = uint64(B);\r\n  C = idivide(A,B,'ceil'); % not likely\r\nend","test_suite":"%%\r\nA = 1;\r\nB = 4;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),4);\r\n%%\r\nA = 2;\r\nB = 6;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),3);\r\n%%\r\nA = 3;\r\nB = 7;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),59);\r\n%%\r\nA = 11;\r\nB = 30;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),11);\r\n%%\r\n% random\r\nfor k = 3:7;\r\n  C_min = unique(randi([2 30],1,k));\r\n  A = 0; B = 1;\r\n  for l = C_min\r\n    A = round((A*l + B)/gcd(l,B));\r\n    B = lcm(B,l);\r\n  end\r\n  C = egyptian(A,B);\r\n  fra = sum(1./double(C));\r\n  fra_correct = A/B;\r\n  assert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\n  fprintf('Choosen A: %d, B: %d\\nbased on random C: [%s\\b]\\n Sum of C: %d, best is %d or less\\n',A,B,sprintf(' %d,',C_min),sum(C),sum(C_min));\r\nend\r\n%%\r\nA = 2;\r\nB = 101;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),1212);\r\n%%\r\nA = 11;\r\nB = 28;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),11);\r\n%%\r\nA = 17;\r\nB = 24;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),15);\r\n%%\r\nA = 25;\r\nB = 36;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),16);\r\n%%\r\nA = 1805;\r\nB = 1806;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),55);\r\n%%\r\n\r\nA = 287;\r\nB = 396;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),49);\r\n%%\r\n% Scoring.\r\n% by courtesy of LY Cao\r\nfid = fopen('score.p','wb');\r\nfwrite(fid,sscanf('7630312E30307630302E30300008501CD77E9FB100000035000001110000018422762999A8C1DE50537BEE443F4D73651F830FC6C78ADFB7DF68DF98823F565884DC58E21C7E397E3D26E4FFEA9A0D83589ABB5C0B0B553B44CFD79C9B272D11DF1965AD538598E8319529727DF4C4CF36A6016DD7816544AE5A8F64C9B2D9D0C4B94DD5EDF14595CBFE3D402647499EA3D9D125AC927454ED85973BCD1AAEA536D5A6CDDCD78A0211E8179603FFE12E4AB0E4704EA195704428700BAE5C4DFD42FF1A8760EDF2721F9724498ECC9F957735E7A3CDB9630DB17DF92ACE8F486706020E0A8D022D14BC313879724760AE20D67F572DD85211E4BEA45CDF3E22976253F113AEA96C1FF907329E4BD429BCFC6331077DA21F05D791DA6ECCF680D2E23AC77DFCE5C1D9869D3098F5B89FF92A','%2x'));\r\nfclose(fid);\r\n% Those lists may be extended and scoring mechanism may be changed a bit\r\nlistA = [2 2 2  2  3 3 3 3  4  5   5  13 31  1805];\r\nlistB = [5 7 21 25 5 7 8 71 71 121 17 42 311 1806];\r\nS = 0;\r\ntry\r\n  for k = 1:numel(listA),\r\n    A = listA(k);\r\n    B = listB(k);\r\n    C = egyptian(A,B);\r\n    fra = sum(1./double(C));\r\n    fra_correct = A/B;\r\n    assert(~any(mod(C,1)) ...\r\n         \u0026\u0026 all(C\u003e1) ...\r\n         \u0026\u0026 isequal(sort(C),unique(C)) ...\r\n         \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\n    S = S + sum(C);\r\n  end\r\n  score(round(20*log10(double(S))));\r\ncatch\r\n  score(1e4);\r\n  error+1;\r\nend\r\n","published":true,"deleted":false,"likes_count":0,"comments_count":12,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":20,"test_suite_updated_at":"2016-04-12T22:03:10.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2015-01-18T23:21:47.000Z","updated_at":"2025-11-29T19:57:57.000Z","published_at":"2016-04-11T13:38:12.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFollowing problem was inspired by\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ethis problem\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ethat comment\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven fraction numerator\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eA\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and denominator\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eB\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, find denominators\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eC\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e for\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"https://en.wikipedia.org/wiki/Egyptian_fraction\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eEgyptian fraction\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The goal of this problem is to minimize the sum of the list.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[   A = 16;\\n   B = 63;\\n   % 16/63 == 1/7 + 1/9\\n   C = [7, 9];]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eC\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e may be\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[4, 252]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[5, 19, 749, 640395]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[5, 27, 63, 945]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[6, 12, 252]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[7, 9]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or almost any else of infinite more other options. The best one is\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[7, 9]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e with sum 16.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYou may assume\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eA\u0026lt;B\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour score will be based on sum of answers,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNo cheating, please,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eWhile greedy algorithm usually solves this problem, score may not be satisfying,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eClass of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eI'm open for proposals to improve test, i.e. verification of output which is far from perfect.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"problem_search":{"errors":[],"problems":[{"id":2126,"title":"Split bread like the Pharaohs - Egyptian fractions and greedy algorithm","description":"How would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\r\nEgyptian fraction is writing any rational number p/q in terms of unity fractions;\r\ne.g.  \r\n\r\n        3/4 = 1/2 + 1/4, OR \r\n            = 1/3 + 1/4 + 1/6\r\n\r\n      13/48 = 1/4 + 1/48\r\nWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\r\n    i.e.   egyptian_fraction( 13, 48) should return [4,48],\r\nYou can use simple greedy algorithm or alternatives.\r\nReferences\r\nhttp://en.wikipedia.org/wiki/Egyptian_fraction\r\nAMS blog post by Tyler Clark (@tylermath12) http://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\r\nBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\r\nP.S: Updated test suite to check for proper solutions only","description_html":"\u003cdiv style = \"text-align: start; line-height: 20.4333px; min-height: 0px; white-space: normal; color: rgb(0, 0, 0); font-family: Menlo, Monaco, Consolas, monospace; font-style: normal; font-size: 14px; font-weight: 400; text-decoration: rgb(0, 0, 0); white-space: normal; \"\u003e\u003cdiv style=\"block-size: 460.333px; display: block; min-width: 0px; padding-block-start: 0px; padding-top: 0px; perspective-origin: 407px 230.167px; transform-origin: 407px 230.167px; vertical-align: baseline; \"\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 379.5px 8px; transform-origin: 379.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eHow would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 242px 8px; transform-origin: 242px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eEgyptian fraction is writing any rational number p/q in terms of unity fractions;\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 122.6px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404px 61.3px; transform-origin: 404px 61.3px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 24px 8.5px; tab-size: 4; transform-origin: 24px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003ee.g.  \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 8.5px; tab-size: 4; transform-origin: 0px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 112px 8.5px; tab-size: 4; transform-origin: 112px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e        3/4 = 1/2 + 1/4, OR \u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 116px 8.5px; tab-size: 4; transform-origin: 116px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e            = 1/3 + 1/4 + 1/6\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 0px 8.5px; tab-size: 4; transform-origin: 0px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); block-size: 20.4333px; border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 96px 8.5px; tab-size: 4; transform-origin: 96px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; \"\u003e      13/48 = 1/4 + 1/48\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 42px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384px 21px; text-align: left; transform-origin: 384px 21px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 383.5px 8px; transform-origin: 383.5px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"background-color: rgb(247, 247, 247); block-size: 20.4333px; border-bottom-left-radius: 4px; border-bottom-right-radius: 4px; border-end-end-radius: 4px; border-end-start-radius: 4px; border-start-end-radius: 4px; border-start-start-radius: 4px; border-top-left-radius: 4px; border-top-right-radius: 4px; margin-block-end: 10px; margin-block-start: 10px; margin-bottom: 10px; margin-inline-end: 3px; margin-inline-start: 3px; margin-left: 3px; margin-right: 3px; margin-top: 10px; perspective-origin: 404px 10.2167px; transform-origin: 404px 10.2167px; margin-left: 3px; margin-top: 10px; margin-bottom: 10px; margin-right: 3px; \"\u003e\u003cdiv style=\"background-color: rgba(0, 0, 0, 0); border-bottom-left-radius: 0px; border-bottom-right-radius: 0px; border-end-end-radius: 0px; border-end-start-radius: 0px; border-inline-end-color: rgb(233, 233, 233); border-inline-end-style: solid; border-inline-end-width: 1px; border-inline-start-color: rgb(233, 233, 233); border-inline-start-style: solid; border-inline-start-width: 1px; border-left-color: rgb(233, 233, 233); border-left-style: solid; border-left-width: 1px; border-right-color: rgb(233, 233, 233); border-right-style: solid; border-right-width: 1px; border-start-end-radius: 0px; border-start-start-radius: 0px; border-top-left-radius: 0px; border-top-right-radius: 0px; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; min-block-size: 18px; min-height: 18px; padding-inline-start: 4px; padding-left: 4px; white-space: nowrap; \"\u003e\u003cspan style=\"block-size: auto; border-inline-end-color: rgb(0, 0, 0); border-inline-end-style: none; border-inline-end-width: 0px; border-inline-start-color: rgb(0, 0, 0); border-inline-start-style: none; border-inline-start-width: 0px; border-left-color: rgb(0, 0, 0); border-left-style: none; border-left-width: 0px; border-right-color: rgb(0, 0, 0); border-right-style: none; border-right-width: 0px; display: inline; margin-inline-end: 45px; margin-right: 45px; min-block-size: 0px; min-height: 0px; padding-inline-start: 0px; padding-left: 0px; perspective-origin: 236px 8.5px; tab-size: 4; transform-origin: 236px 8.5px; unicode-bidi: normal; white-space: pre; margin-right: 45px; \"\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; perspective-origin: 180px 8.5px; transform-origin: 180px 8.5px; \"\u003e    i.e.   egyptian_fraction( 13, 48) should \u003c/span\u003e\u003cspan style=\"border-block-end-color: rgb(170, 4, 249); border-block-start-color: rgb(170, 4, 249); border-bottom-color: rgb(170, 4, 249); border-inline-end-color: rgb(170, 4, 249); border-inline-start-color: rgb(170, 4, 249); border-left-color: rgb(170, 4, 249); border-right-color: rgb(170, 4, 249); border-top-color: rgb(170, 4, 249); caret-color: rgb(170, 4, 249); color: rgb(170, 4, 249); column-rule-color: rgb(170, 4, 249); margin-inline-end: 0px; margin-right: 0px; outline-color: rgb(170, 4, 249); perspective-origin: 52px 8.5px; text-decoration-color: rgb(170, 4, 249); text-emphasis-color: rgb(170, 4, 249); transform-origin: 52px 8.5px; \"\u003ereturn [4,48]\u003c/span\u003e\u003cspan style=\"margin-inline-end: 0px; margin-right: 0px; perspective-origin: 4px 8.5px; transform-origin: 4px 8.5px; \"\u003e,\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 10px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 10px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 10px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 165px 8px; transform-origin: 165px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eYou can use simple greedy algorithm or alternatives.\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 41px 8px; transform-origin: 41px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"font-weight: 700; \"\u003eReferences\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003col style=\"block-size: 61.3px; counter-reset: list-item 0; font-family: Helvetica, Arial, sans-serif; list-style-type: decimal; margin-block-end: 20px; margin-block-start: 10px; margin-bottom: 20px; margin-top: 10px; perspective-origin: 391px 30.65px; transform-origin: 391px 30.65px; margin-top: 10px; margin-bottom: 20px; \"\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttp://en.wikipedia.org/wiki/Egyptian_fraction\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/li\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 142px 8px; transform-origin: 142px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eAMS blog post by Tyler Clark (@tylermath12)\u003c/span\u003e\u003c/span\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 2px 8px; transform-origin: 2px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003e \u003c/span\u003e\u003c/span\u003e\u003ca target='_blank' href = \"/#null\"\u003e\u003cspan style=\"\"\u003e\u003cspan style=\"\"\u003ehttp://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\u003c/span\u003e\u003c/span\u003e\u003c/a\u003e\u003c/li\u003e\u003cli style=\"block-size: 20.4333px; counter-reset: none; display: list-item; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-start: 56px; margin-left: 56px; margin-top: 0px; perspective-origin: 363px 10.2167px; text-align: left; transform-origin: 363px 10.2167px; white-space: pre-wrap; margin-left: 56px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-inline-start: 0px; margin-left: 0px; perspective-origin: 347px 8px; transform-origin: 347px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e\u003c/ol\u003e\u003cdiv style=\"block-size: 21px; font-family: Helvetica, Arial, sans-serif; line-height: 21px; margin-block-end: 9px; margin-block-start: 2px; margin-bottom: 9px; margin-inline-end: 10px; margin-inline-start: 4px; margin-left: 4px; margin-right: 10px; margin-top: 2px; perspective-origin: 384px 10.5px; text-align: left; transform-origin: 384px 10.5px; white-space: pre-wrap; margin-left: 4px; margin-top: 2px; margin-bottom: 9px; margin-right: 10px; \"\u003e\u003cspan style=\"block-size: auto; display: inline; margin-block-end: 0px; margin-block-start: 0px; margin-bottom: 0px; margin-inline-end: 0px; margin-inline-start: 0px; margin-left: 0px; margin-right: 0px; margin-top: 0px; perspective-origin: 178px 8px; transform-origin: 178px 8px; unicode-bidi: normal; \"\u003e\u003cspan style=\"\"\u003eP.S: Updated test suite to check for proper solutions only\u003c/span\u003e\u003c/span\u003e\u003c/div\u003e\u003c/div\u003e\u003c/div\u003e","function_template":"function denoms = egyptian_fraction(p,q)\r\n  denoms = [];\r\n  \r\n  if ( p == 1 )\r\n     denoms(end+1) = q;\r\n     return;\r\n  end\r\n  % treat other cases..\r\nend","test_suite":"%%\r\n% Updated test suite to remove trivial solutions;\r\n\r\n%%\r\n Vmin = 13; Vmax = 48;\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n assert(isequal(arr, [4 48]))\r\n \r\n%%\r\n Vmin = 3; Vmax = 4;\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n assert(isequal(arr, [2 4]) || isequal(arr, [3 4 6]))\r\n \r\n%%\r\n Vmin = 2;\r\n in = primes(20);\r\n Vmax = in(randi(numel(in)));\r\n arr = egyptian_fraction(Vmin,Vmax);\r\n l=lcm(arr(1),arr(2));\r\n for k=3:numel(arr)\r\n     l=lcm(l,arr(k));\r\n end\r\n assert(isequal(sum(arr),sum(l./arr)/(Vmax/l)))\r\n \r\n \r\n%%\r\n% Small\r\n Vmin = 10; Vmax = 55;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% Pie\r\n Vmin = 113; Vmax = 355;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% Ramanujan\r\n Vmin = 1023; Vmax = 1729;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n\r\n%%\r\n% E\r\n Vmin = 27; Vmax = 183;\r\n denom = floor(unique(egyptian_fraction(Vmin,Vmax)));\r\n egyptian_value = sum(1./denom);\r\n\r\n rel_tol = Vmin/Vmax*1e-6;\r\n actual_error = abs( egyptian_value - Vmin/Vmax );\r\n assert(isequal(actual_error \u003c rel_tol ,true))\r\n","published":true,"deleted":false,"likes_count":3,"comments_count":5,"created_by":3378,"edited_by":223089,"edited_at":"2023-03-29T14:08:28.000Z","deleted_by":null,"deleted_at":null,"solvers_count":96,"test_suite_updated_at":"2023-03-29T14:08:28.000Z","rescore_all_solutions":false,"group_id":38,"created_at":"2014-01-19T06:15:39.000Z","updated_at":"2026-03-31T17:38:29.000Z","published_at":"2014-01-19T17:44:14.000Z","restored_at":null,"restored_by":null,"spam":null,"simulink":false,"admin_reviewed":false,"description_opc":"{\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eHow would you split 5 loaves of bread among 8 people in all fairness? Get a hint from the Pharaohs. 5/8 = 4/8 + 1/8 , i.e. each receives 1/2 of loaf plus 1/8 - splitting 4 loaves into 1/2 and then the last loaf into 8 pieces.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eEgyptian fraction is writing any rational number p/q in terms of unity fractions;\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[e.g.  \\n\\n        3/4 = 1/2 + 1/4, OR \\n            = 1/3 + 1/4 + 1/6\\n\\n      13/48 = 1/4 + 1/48]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eWrite a program to return the Egyptian fraction of a given rational number p, q. You outputs in the above cases should be the series of denominator values,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[    i.e.   egyptian_fraction( 13, 48) should return [4,48],]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYou can use simple greedy algorithm or alternatives.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:b/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eReferences\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttp://en.wikipedia.org/wiki/Egyptian_fraction\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eAMS blog post by Tyler Clark (@tylermath12)\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ehttp://blogs.ams.org/jmm2014/2014/01/17/friday-morning-math-fun/\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"2\\\"/\u003e\u003c/w:numPr\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eBonus points if you can enumerate all possible Egyptian fractions of (p,q), but thats a problem for another day.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003cw:jc w:val=\\\"left\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eP.S: Updated test suite to check for proper solutions only\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\",\"relationship\":null}],\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"target\":\"/matlab/document.xml\",\"relationshipId\":\"rId1\"}]}"},{"id":2838,"title":"Optimum Egyptian Fractions","description":"Following problem was inspired by \u003chttp://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm this problem\u003e and \u003chttp://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542 that comment\u003e.\r\n\r\nGiven fraction numerator _A_ and denominator _B_, find denominators _C_ for \u003chttps://en.wikipedia.org/wiki/Egyptian_fraction Egyptian fraction\u003e. The goal of this problem is to minimize the sum of the list.\r\n\r\nExample:\r\n  \r\n   A = 16;\r\n   B = 63;\r\n   % 16/63 == 1/7 + 1/9\r\n   C = [7, 9];\r\n\r\n_C_ may be _[4, 252]_ or _[5, 19, 749, 640395]_ or _[5, 27, 63, 945]_ or _[6, 12, 252]_ or _[7, 9]_ or almost any else of infinite more other options. The best one is _[7, 9]_ with sum 16.\r\n\r\n* You may assume _A\u003cB_,\r\n* Your score will be based on sum of answers,\r\n* No cheating, please,\r\n* While greedy algorithm usually solves this problem, score may not be satisfying,\r\n* Class of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\r\n* I'm open for proposals to improve test, i.e. verification of output which is far from perfect.","description_html":"\u003cp\u003eFollowing problem was inspired by \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm\"\u003ethis problem\u003c/a\u003e and \u003ca href = \"http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542\"\u003ethat comment\u003c/a\u003e.\u003c/p\u003e\u003cp\u003eGiven fraction numerator \u003ci\u003eA\u003c/i\u003e and denominator \u003ci\u003eB\u003c/i\u003e, find denominators \u003ci\u003eC\u003c/i\u003e for \u003ca href = \"https://en.wikipedia.org/wiki/Egyptian_fraction\"\u003eEgyptian fraction\u003c/a\u003e. The goal of this problem is to minimize the sum of the list.\u003c/p\u003e\u003cp\u003eExample:\u003c/p\u003e\u003cpre\u003e   A = 16;\r\n   B = 63;\r\n   % 16/63 == 1/7 + 1/9\r\n   C = [7, 9];\u003c/pre\u003e\u003cp\u003e\u003ci\u003eC\u003c/i\u003e may be \u003ci\u003e[4, 252]\u003c/i\u003e or \u003ci\u003e[5, 19, 749, 640395]\u003c/i\u003e or \u003ci\u003e[5, 27, 63, 945]\u003c/i\u003e or \u003ci\u003e[6, 12, 252]\u003c/i\u003e or \u003ci\u003e[7, 9]\u003c/i\u003e or almost any else of infinite more other options. The best one is \u003ci\u003e[7, 9]\u003c/i\u003e with sum 16.\u003c/p\u003e\u003cul\u003e\u003cli\u003eYou may assume \u003ci\u003eA\u0026lt;B\u003c/i\u003e,\u003c/li\u003e\u003cli\u003eYour score will be based on sum of answers,\u003c/li\u003e\u003cli\u003eNo cheating, please,\u003c/li\u003e\u003cli\u003eWhile greedy algorithm usually solves this problem, score may not be satisfying,\u003c/li\u003e\u003cli\u003eClass of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\u003c/li\u003e\u003cli\u003eI'm open for proposals to improve test, i.e. verification of output which is far from perfect.\u003c/li\u003e\u003c/ul\u003e","function_template":"function C = egyptian(A,B)\r\n  A = uint64(A);\r\n  B = uint64(B);\r\n  C = idivide(A,B,'ceil'); % not likely\r\nend","test_suite":"%%\r\nA = 1;\r\nB = 4;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),4);\r\n%%\r\nA = 2;\r\nB = 6;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),3);\r\n%%\r\nA = 3;\r\nB = 7;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),59);\r\n%%\r\nA = 11;\r\nB = 30;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),11);\r\n%%\r\n% random\r\nfor k = 3:7;\r\n  C_min = unique(randi([2 30],1,k));\r\n  A = 0; B = 1;\r\n  for l = C_min\r\n    A = round((A*l + B)/gcd(l,B));\r\n    B = lcm(B,l);\r\n  end\r\n  C = egyptian(A,B);\r\n  fra = sum(1./double(C));\r\n  fra_correct = A/B;\r\n  assert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\n  fprintf('Choosen A: %d, B: %d\\nbased on random C: [%s\\b]\\n Sum of C: %d, best is %d or less\\n',A,B,sprintf(' %d,',C_min),sum(C),sum(C_min));\r\nend\r\n%%\r\nA = 2;\r\nB = 101;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),1212);\r\n%%\r\nA = 11;\r\nB = 28;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),11);\r\n%%\r\nA = 17;\r\nB = 24;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),15);\r\n%%\r\nA = 25;\r\nB = 36;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),16);\r\n%%\r\nA = 1805;\r\nB = 1806;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),55);\r\n%%\r\n\r\nA = 287;\r\nB = 396;\r\nC = egyptian(A,B);\r\nfra = sum(1./double(C));\r\nfra_correct = A/B;\r\nassert(~any(mod(C,1)) \u0026\u0026 all(C\u003e1) \u0026\u0026 isequal(sort(C),unique(C)) \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\nfprintf('Sum of C: %d, best %d',sum(C),49);\r\n%%\r\n% Scoring.\r\n% by courtesy of LY Cao\r\nfid = fopen('score.p','wb');\r\nfwrite(fid,sscanf('7630312E30307630302E30300008501CD77E9FB100000035000001110000018422762999A8C1DE50537BEE443F4D73651F830FC6C78ADFB7DF68DF98823F565884DC58E21C7E397E3D26E4FFEA9A0D83589ABB5C0B0B553B44CFD79C9B272D11DF1965AD538598E8319529727DF4C4CF36A6016DD7816544AE5A8F64C9B2D9D0C4B94DD5EDF14595CBFE3D402647499EA3D9D125AC927454ED85973BCD1AAEA536D5A6CDDCD78A0211E8179603FFE12E4AB0E4704EA195704428700BAE5C4DFD42FF1A8760EDF2721F9724498ECC9F957735E7A3CDB9630DB17DF92ACE8F486706020E0A8D022D14BC313879724760AE20D67F572DD85211E4BEA45CDF3E22976253F113AEA96C1FF907329E4BD429BCFC6331077DA21F05D791DA6ECCF680D2E23AC77DFCE5C1D9869D3098F5B89FF92A','%2x'));\r\nfclose(fid);\r\n% Those lists may be extended and scoring mechanism may be changed a bit\r\nlistA = [2 2 2  2  3 3 3 3  4  5   5  13 31  1805];\r\nlistB = [5 7 21 25 5 7 8 71 71 121 17 42 311 1806];\r\nS = 0;\r\ntry\r\n  for k = 1:numel(listA),\r\n    A = listA(k);\r\n    B = listB(k);\r\n    C = egyptian(A,B);\r\n    fra = sum(1./double(C));\r\n    fra_correct = A/B;\r\n    assert(~any(mod(C,1)) ...\r\n         \u0026\u0026 all(C\u003e1) ...\r\n         \u0026\u0026 isequal(sort(C),unique(C)) ...\r\n         \u0026\u0026 abs(fra-fra_correct)\u003c10*eps(fra));\r\n    S = S + sum(C);\r\n  end\r\n  score(round(20*log10(double(S))));\r\ncatch\r\n  score(1e4);\r\n  error+1;\r\nend\r\n","published":true,"deleted":false,"likes_count":0,"comments_count":12,"created_by":14358,"edited_by":null,"edited_at":null,"deleted_by":null,"deleted_at":null,"solvers_count":20,"test_suite_updated_at":"2016-04-12T22:03:10.000Z","rescore_all_solutions":false,"group_id":1,"created_at":"2015-01-18T23:21:47.000Z","updated_at":"2025-11-29T19:57:57.000Z","published_at":"2016-04-11T13:38:12.000Z","restored_at":null,"restored_by":null,"spam":false,"simulink":false,"admin_reviewed":false,"description_opc":"{\"relationships\":[{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/document\",\"targetMode\":\"\",\"relationshipId\":\"rId1\",\"target\":\"/matlab/document.xml\"},{\"relationshipType\":\"http://schemas.mathworks.com/matlab/code/2013/relationships/output\",\"targetMode\":\"\",\"relationshipId\":\"rId2\",\"target\":\"/matlab/output.xml\"}],\"parts\":[{\"partUri\":\"/matlab/document.xml\",\"relationship\":[],\"contentType\":\"application/vnd.mathworks.matlab.code.document+xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\"?\u003e\\n\u003cw:document xmlns:w=\\\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\\\"\u003e\u003cw:body\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eFollowing problem was inspired by\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/problems/2126-split-bread-like-the-pharaohs-egyptian-fractions-and-greedy-algorithm\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ethis problem\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e and\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"http://www.mathworks.com/matlabcentral/cody/solutions/868356#comment_6542\\\"\u003e\u003cw:r\u003e\u003cw:t\u003ethat comment\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eGiven fraction numerator\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eA\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e and denominator\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eB\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e, find denominators\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eC\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e for\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:hyperlink w:docLocation=\\\"https://en.wikipedia.org/wiki/Egyptian_fraction\\\"\u003e\u003cw:r\u003e\u003cw:t\u003eEgyptian fraction\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:hyperlink\u003e\u003cw:r\u003e\u003cw:t\u003e. The goal of this problem is to minimize the sum of the list.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eExample:\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"code\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003e\u003c![CDATA[   A = 16;\\n   B = 63;\\n   % 16/63 == 1/7 + 1/9\\n   C = [7, 9];]]\u003e\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"text\\\"/\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eC\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e may be\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[4, 252]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[5, 19, 749, 640395]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[5, 27, 63, 945]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[6, 12, 252]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[7, 9]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e or almost any else of infinite more other options. The best one is\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003e[7, 9]\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e with sum 16.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYou may assume\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e \u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:rPr\u003e\u003cw:i/\u003e\u003c/w:rPr\u003e\u003cw:t\u003eA\u0026lt;B\u003c/w:t\u003e\u003c/w:r\u003e\u003cw:r\u003e\u003cw:t\u003e,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eYour score will be based on sum of answers,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eNo cheating, please,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eWhile greedy algorithm usually solves this problem, score may not be satisfying,\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eClass of inputs is double, but keep in mind it may change in the future - most likely to uint64. Preferred output class is uint64.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003cw:p\u003e\u003cw:pPr\u003e\u003cw:pStyle w:val=\\\"ListParagraph\\\"/\u003e\u003cw:numPr\u003e\u003cw:numId w:val=\\\"1\\\"/\u003e\u003c/w:numPr\u003e\u003c/w:pPr\u003e\u003cw:r\u003e\u003cw:t\u003eI'm open for proposals to improve test, i.e. verification of output which is far from perfect.\u003c/w:t\u003e\u003c/w:r\u003e\u003c/w:p\u003e\u003c/w:body\u003e\u003c/w:document\u003e\"},{\"partUri\":\"/matlab/output.xml\",\"contentType\":\"text/xml\",\"content\":\"\u003c?xml version=\\\"1.0\\\" encoding=\\\"UTF-8\\\" standalone=\\\"no\\\" ?\u003e\u003cembeddedOutputs\u003e\u003cmetaData\u003e\u003cevaluationState\u003emanual\u003c/evaluationState\u003e\u003clayoutState\u003ecode\u003c/layoutState\u003e\u003coutputStatus\u003eready\u003c/outputStatus\u003e\u003c/metaData\u003e\u003coutputArray type=\\\"array\\\"/\u003e\u003cregionArray type=\\\"array\\\"/\u003e\u003c/embeddedOutputs\u003e\"}]}"}],"term":"tag:\"egyptian fraction\"","current_player_id":null,"fields":[{"name":"page","type":"integer","callback":null,"default":1,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"per_page","type":"integer","callback":null,"default":50,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"sort","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":null,"prepend":true},{"name":"body","type":"text","callback":null,"default":"*:*","directive":null,"facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":false},{"name":"group","type":"string","callback":null,"default":null,"directive":"group","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"difficulty_rating_bin","type":"string","callback":null,"default":null,"directive":"difficulty_rating_bin","facet":true,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"id","type":"integer","callback":null,"default":null,"directive":"id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"tag","type":"string","callback":null,"default":null,"directive":"tag","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"product","type":"string","callback":null,"default":null,"directive":"product","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_at","type":"timeframe","callback":{},"default":null,"directive":"created_at","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"profile_id","type":"integer","callback":null,"default":null,"directive":"author_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"created_by","type":"string","callback":null,"default":null,"directive":"author","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player_id","type":"integer","callback":null,"default":null,"directive":"solver_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"player","type":"string","callback":null,"default":null,"directive":"solver","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"solvers_count","type":"integer","callback":null,"default":null,"directive":"solvers_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"comments_count","type":"integer","callback":null,"default":null,"directive":"comments_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"likes_count","type":"integer","callback":null,"default":null,"directive":"likes_count","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leader_id","type":"integer","callback":null,"default":null,"directive":"leader_id","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true},{"name":"leading_solution","type":"integer","callback":null,"default":null,"directive":"leading_solution","facet":null,"facet_method":"and","operator":null,"param":"term","static":null,"prepend":true}],"filters":[{"name":"asset_type","type":"string","callback":null,"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":null,"static":"\"cody:problem\"","prepend":true},{"name":"profile_id","type":"integer","callback":{},"default":null,"directive":null,"facet":null,"facet_method":"and","operator":null,"param":"author_id","static":null,"prepend":true}],"query":{"params":{"per_page":50,"term":"tag:\"egyptian fraction\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"egyptian fraction\"","","\"","egyptian fraction","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc0bf8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0b58\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f0f566a7a90\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc1698\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0f18\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0e78\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f0f55cc0c98\u003e":"tag:\"egyptian fraction\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc0c98\u003e":"tag:\"egyptian fraction\""},"queried_facets":{}},"query_backend":{"connection":{"configuration":{"index_url":"http://index-op-v2/solr/","query_url":"http://search-op-v2/solr/","direct_access_index_urls":["http://index-op-v2/solr/"],"direct_access_query_urls":["http://search-op-v2/solr/"],"timeout":10,"vhost":"search","exchange":"search.topic","heartbeat":30,"pre_index_mode":false,"host":"rabbitmq-eks","port":5672,"username":"cody-search","password":"78X075ddcV44","virtual_host":"search","indexer":"amqp","http_logging":"true","core":"cody"},"query_connection":{"uri":"http://search-op-v2/solr/cody/","proxy":null,"connection":{"parallel_manager":null,"headers":{"User-Agent":"Faraday v1.0.1"},"params":{},"options":{"params_encoder":"Faraday::FlatParamsEncoder","proxy":null,"bind":null,"timeout":null,"open_timeout":null,"read_timeout":null,"write_timeout":null,"boundary":null,"oauth":null,"context":null,"on_data":null},"ssl":{"verify":true,"ca_file":null,"ca_path":null,"verify_mode":null,"cert_store":null,"client_cert":null,"client_key":null,"certificate":null,"private_key":null,"verify_depth":null,"version":null,"min_version":null,"max_version":null},"default_parallel_manager":null,"builder":{"adapter":{"name":"Faraday::Adapter::NetHttp","args":[],"block":null},"handlers":[{"name":"Faraday::Response::RaiseError","args":[],"block":null}],"app":{"app":{"ssl_cert_store":{"verify_callback":null,"error":null,"error_string":null,"chain":null,"time":null},"app":{},"connection_options":{},"config_block":null}}},"url_prefix":"http://search-op-v2/solr/cody/","manual_proxy":false,"proxy":null},"update_format":"RSolr::JSON::Generator","update_path":"update","options":{"url":"http://search-op-v2/solr/cody"}}},"query":{"params":{"per_page":50,"term":"tag:\"egyptian fraction\"","current_player":null,"sort":"map(difficulty_value,0,0,999) asc"},"parser":"MathWorks::Search::Solr::QueryParser","directives":{"term":{"directives":{"tag":[["tag:\"egyptian fraction\"","","\"","egyptian fraction","\""]]}}},"facets":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc0bf8\u003e":null,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0b58\u003e":null},"filters":{"#\u003cMathWorks::Search::Field:0x00007f0f566a7a90\u003e":"\"cody:problem\""},"fields":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc1698\u003e":1,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0f18\u003e":50,"#\u003cMathWorks::Search::Field:0x00007f0f55cc0e78\u003e":"map(difficulty_value,0,0,999) asc","#\u003cMathWorks::Search::Field:0x00007f0f55cc0c98\u003e":"tag:\"egyptian fraction\""},"user_query":{"#\u003cMathWorks::Search::Field:0x00007f0f55cc0c98\u003e":"tag:\"egyptian fraction\""},"queried_facets":{}},"options":{"fields":["id","difficulty_rating"]},"join":" "},"results":[{"id":2126,"difficulty_rating":"medium"},{"id":2838,"difficulty_rating":"medium"}]}}