14
Directions
Write a program that, given an input integer n (n >= 0
), outputs the smallest positive integer m where:
n = a[1]^b[1] + a[2]^b[2] + a[3]^b[3] + ... + a[k]^b[k]
a
andb
are finite sequences of the same length- all elements of
a
are less thanm
- all elements of
b
are less thanm
- all elements of
a
are different and integersa[x] >= 0
- all elements of
b
are different and integersb[x] >= 0
a[x]
andb[x]
are not both 0 (since 0^0 is indeterminate)
This is code-golf, so fewest bytes wins.
Examples
In 0 -> Out 1
Possible Sum:
In 1 -> Out 2
Possible Sum: 1^0
In 2 -> Out 3
Possible Sum: 2^1
In 3 -> Out 3
Possible Sum: 2^1 + 1^0
In 6 -> Out 4
Possible Sum: 2^2 + 3^0 + 1^1
In 16 -> Out 5
Possible Sum: 2^4
In 17 -> Out 4
Possible Sum: 3^2 + 2^3
In 23 -> Out 6
Possible Sum: 5^1 + 3^0 + 2^4 + 1^3
In 24 -> Out 5
Possible Sum: 4^2 + 2^3
In 27 -> Out 4
Possible Sum: 3^3
In 330 -> Out 7
Possible Sum: 6^1 + 4^3 + 3^5 + 2^4 + 1^0
How are we supposed to make a sequence of unique, nonnegative integers that has a non-infinite sum? – feersum – 2015-01-17T03:32:03.980
Also, the first case doesn't make sense because a sum with 0 terms would suffice. – feersum – 2015-01-17T03:34:46.057
@feersum I don't quite understand your question. My solution to this is a brute force search of all combinations where
m<2
thenm<3
thenm<4
etc. until I find a sum that equalsn
. Also, I thought about having the sum for0
be no terms, but then what is the output? m > ? – kukac67 – 2015-01-17T03:40:48.460My first comment was because the way it is written suggests an infinite sequence. For the second issue, I suggest that the minimum input is 1. – feersum – 2015-01-17T03:43:24.513
@feersum Alright, I will change the example case. And I will also try to notate a finite sequence somehow. Any ideas? – kukac67 – 2015-01-17T03:46:19.530
1For finite sequences, you would usually do something like
n = a[1]^b[1] + a[2]^b[2] + ... + a[k]^b[k]
. – Volatility – 2015-01-17T08:43:19.8531Nice question. Just one quibble on the first test case:
a
andb
are finite sequences of length0
, so there is no integerm
which doesn't satisfy the constraints, and since there is no smallest integer the answer is not defined. Possible fixes would be to ask for the smallest natural numberm
(in which case you should change the expected answer there to0
) or for the smallest positive integerm
. – Peter Taylor – 2015-01-17T08:43:34.053