Undo the square roots Your job is to convert decimals back into the sum of the square roots of integers. The result has to have an accuracy of at least 6 significant decimal digits.

Input:

A number indicating the number of square roots and a decimal indicating the number to approximate.

Example input:

2 3.414213562373095


Output:
Integers separated by spaces that, when square rooted and added, are approximately the original decimal accurate to at least 6 significant decimal digits.

Zeros are not allowed in the solution.

If there are multiple solutions, you only have to print one.

Example output (in any order):

4 2


This works because Math.sqrt(4) + Math.sqrt(2) == 3.414213562373095.

This is code golf. Shortest code (with optional bonus) wins!

There is always going to be a solution but -10 if your program prints "No" when there is no solution with integers. In addition, -10 if your program prints all solutions (separated by newlines or semicolons or whatever) instead of just one.

Test cases:

3 7.923668178593959 --&gt; 6 7 8
2 2.8284271247461903 --&gt; 2 2
5 5.0 --&gt; 1 1 1 1 1
5 13.0 --&gt; 4 4 9 9 9 --&gt; 81 1 1 1 1 --&gt; 36 9 4 1 1 etc. [print any, but print all for the "all solutions bonus"]


And yes, your program has to finish in finite time using finite memory on any reasonable machine. It can't just work "in theory," you have to be able to actually test it.
Python 3, 90 - 10 = 80

def S(N,x,n=[],i=1):
 if x*x&lt;1e-12&gt;N==0:print(*n)
 while.1+x*x&gt;i:S(N-1,x-i**.5,n+[i]);i+=1


(Mega thanks to @xnor for tips, especially the restructuring of the for loop into a while)

A simple recursive attempt. It starts off with the target number and continuously subtracts square roots until it hits 0 or lower. The function S can be called like S(2,3.414213562373095) (the second argument is assumed to be positive).

The program doesn't just print out all solutions, it prints out all permutations of solutions (a little extraneous, I know). Here's the output for the last case: Pastebin.

A slight tweak gives a 98 - 10 = 88 solution which doesn't print permutations, making it more efficient:

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x&lt;1e-12&gt;N==0:print(*n)
 while.1+x*x&gt;i:S(N-1,x-i**.5,n+[i]);i+=1


And just for fun, this 99 - 10 = 89 one is about as efficient as it gets (unlike the others, it doesn't blow the stack on S(1,1000):

def S(N,x,n=[]):
 *_,i=[1]+n
 if x*x&lt;1e-12&gt;N:print(*n)
 while(.1+x*x&gt;i)*N:S(N-1,x-i**.5,n+[i]);i+=1


Note that, although we have a mutable default argument, this never causes a problem if we rerun the function since n+[i] creates a new list.



Proof of correctness

In order to end up in an infinite loop, we must hit some point where x &lt; 0 and 0.1 + x2 > 1. This is satisfied by x &lt; -0.948....

But note that we start from positive x and x is always decreasing, so in order to hit x &lt; -0.948... we must have had x' - i0.5 &lt; -0.948... for some x' > -0.948... before x and positive integer i. For the while loop to run, we must also have had 0.1 + x'2 > i.

Rearranging we get x'2 + 1.897x' + 0.948 &lt; i &lt; 0.1 + x'2, the outer parts implying that x' &lt; -0.447. But if -0.948 &lt; x' &lt; -0.447, then no positive integer i can fit the gap in the above inequality.

Hence we'll never end up in an infinite loop.