24
2
Fermat's polygonal number theorem states that every positive integer can be expressed as the sum of at most \$n\$ \$n\$-gonal numbers. This means that every positive integer can be expressed as the sum of up to three triangle numbers, four square numbers, five pentagonal numbers etc. Your task is to take a positive integer \$x\$, and an integer \$s \ge 3\$, and to output the \$s\$-gonal integers which sum to \$x\$.
The \$n\$-th \$s\$-gonal integer, where \$n \ge 1\$ and \$s \ge 3\$, can be defined in a couple of ways. The non-math-y way is that the \$n\$th \$s\$-gonal number can be constructed as a regular polygon with \$s\$ sides, each of length \$n\$. For example, for \$s = 3\$ (triangular numbers):
See here for examples with a larger \$s\$.
The math-y definition is by using the formula for \$P(n, s)\$, which yields the \$n\$-th \$s\$-gonal number:
$$P(n, s) = \frac{n^2(s-2) - n(s-4)}{2}$$
which is given in the Wikipedia page here.
Input
Two positive integers, \$s\$ and \$x\$, with the condition \$s \ge 3\$. You may input these integers in the most natural representation in your language (decimal, unary, Church numerals, integer-valued floating point numbers etc.).
Output
A list of integers, \$L\$, with a maximum length of \$s\$, where the sum of \$L\$ is equal to \$x\$ and all integers in \$L\$ are \$s\$-gonal integers. Again, the integers may be outputted in the natural representation in your language, with any distinct, consistent separator (so non-decimal character(s) for decimal output, a character different from that used for unary output etc.)
Rules
- The inputs or outputs will never exceed the integer limit for your language
- \$L\$ does not have to be ordered
- In case of multiple possible outputs, any or all are acceptable
- This is code-golf so the shortest code in bytes wins
Test cases
x, s => L
1, s => 1
2, s => 1, 1
5, 6 => 1, 1, 1, 1, 1
17, 3 => 1, 6, 10
17, 4 => 1, 16
17, 5 => 5, 12
36, 3 => 36
43, 6 => 15, 28
879, 17 => 17, 48, 155, 231, 428
4856, 23 => 130, 448, 955, 1398, 1925
Sandbox post – caird coinheringaahing – 2019-10-07T17:14:12.973
Can the output have some zero padding? For instance if we consider
x=17, s=5
could we output5,12,0,0,0
instead of just5,12
? – flawr – 2019-10-07T17:30:33.117@flawr So long as the length of the array doesn't exceed $s$, even with padding, that's fine – caird coinheringaahing – 2019-10-07T17:42:16.510
Are repeats allowed or should I add a
Q
to my submission? – Jonathan Allan – 2019-10-07T18:46:39.573@JonathanAllan Repeated outputs are perfectly fine (if outputting multiple solutions) – caird coinheringaahing – 2019-10-07T18:47:46.130
@AZTECCO Added, but all the answers I checked worked – caird coinheringaahing – 2019-10-11T06:34:40.157
@caird coinheringaahing The test I suggested was s=3 n=53, anyway I written directly to the people after consulting meta stack exchange for the right approach. – AZTECCO – 2019-10-15T11:00:07.543
In the sum for n s=53 10 can not to be 15 because 15 not seem to me a s=10 number...possible I wrong on it, if so what number u is such that P(u,10)=15? – RosLuP – 2019-10-20T08:06:08.537