Ask HN: Can you work out how this is done? (repost) | Hacker News Reader

Ask HN: Can you work out how this is done? (repost)

20 pointsColinWright39 comments

Choose a polynomial p(x) with non-negative integer coefficients.

Now choose an integer k that's larger than all the coefficients and evaluate p(k). You tell me k and p(k), and I tell you the polynomial.

So ...

Can you work out how to do it?

Do you find this interesting?

Please don't give it away - by all means make it clear that you know how to do it (if you do!) but please don't spoil it for the others.

But mostly I'm interested in knowing (eventually) how you think about it.

This is a repost because the first time I asked the question fell off the front page with very little reaction, and perhaps not many people saw it. This is a one-shot repost - I'll not post this question again. I look forward to your answers (assuming there are any ...)

Thanks in advance.

View on HN

> Can you work out how to do it?

Yes.

> Do you find this interesting?

Yes! I found it interesting because at first it seems like the solution space ought to be many-to-one, not one-to-one, and it's not immediately clear why the condition that k is larger than the coefficients is the "right" condition to fix that. I had to work through some examples to see the trick of it.

hints (rot13):

1. jungunccrafvslbhpubbfrxrdhnyfgjb

2. jungunccrafvslbhpubbfrxrdhnyfgra

solution: jevgrcxvaonfrx

Excellent - pleased you liked it. Here on HN we seem to be in a minority. And your answer is one of the two techniques I've got - nice one.

vyvxrgbrknttrengr:jungunccrafvslbhpubbfrxrdhnyfbarzvyyvbanaqgurpbrssvpvragfneryrffgunagra

The simplest answer is for you to try it and see what happens. Nothing goes wrong, and it just makes the solution/technique more obvious.

Thanks! I was just saying how I arrived at the answer, how my mind works, which I think is what the OP was looking to see - how people solve a problem like this. Hope this comes up in my next whiteboard interview :-)

Oh, OK, that wasn't obvious to me, but now is - thanks for the clarification, and for the answer. Interesting.

Your technique, by the way, is a classic puzzle solving technique that I've used successfully many times, sometimes to great effect. Nice one.

If we know what k is, we've got an upper bound on the value of the roots. Since we can express p(k) as (k-x_1)(k-x_2)...(k-x_n) (with x_i as roots), we know that each (k-x_i) must be an integer factor of p(k).

Based on these facts, I'd probably just brute force it. Figure out the prime factorization of p(k), then figure out all of the ways to express the x_i.

Note that this does also prove that the algorithm will not uniquely define an expression for p(k). For example, if p(10) = 12, then (x-4)(x-8), (x-7)(x-6), among others, satisfy.

This is mildly interesting to think about as someone who never was a math major but maybe should have been. There are some interesting side bits (for example, disproving uniqueness) but it does feel like there are more "powerful" statements floating around this type of algebra.

I think you are missing that the coefficients must be non-negative. In fact the answer is always unique, so you may want to rethink your approach.

Ah yeah, misread that there.

Express p(k) in base k. Those are your coefficients.

Pretty cute. :)

“Choose a polynomial p(x) with non-negative integer coefficients”

I think you want to say positive there, or mathematicians will exploit the fact that common definitions (examples: https://en.wikipedia.org/wiki/Polynomial#Definition, http://mathworld.wolfram.com/Polynomial.html) of polynomial allow coefficients to be zero, making, for example, x + 1 (a polynomial of degree 1) different from 0 x² + x + 1 (a polynomial of degree 2)

Reason for that choice is that it makes the set of polynomials of degree n closed under addition and subtraction)

Nope, I explicitly mean non-negative, because you are allowed polynomials like x^4+x+2. In particular, polynomials are considered equivalent if they differ only in terms that have zero coefficients. That means that 0x^2+x+1 is the same polynomial as x+1. Further, 0x²+x+1 is not a polynomial of degree 2, because the degree is the highest power with a non-zero coefficient.

So the question is fine as it stands.

[redacted because I was completely wrong, missing the obvious ;-)] ... See child comment.

> No it is not. Your statement of the problem does not rule out only the coefficient of x^0 being positive, and the rest being zero.

You are correct that we permit any and/or all coefficients to be zero, allowing the case that p(x)=665. That is intentional.

> Just saying the coefficients are all nonnegative, the polynomial p(k) = 665 also is a solution for the case k = 6 and p(6) = 665.

No it isn't, because you have evaluated at 6, which is not larger than all the coefficients. Specifically, 6 is not larger than 665.

So I still claim that the question is fine as it stands. I do appreciate you trying to poke holes in it, though. Thanks.

(Added in edit: Given that you've retracted that, would you like me to remove this comment?)

It's amazing how far away I am from being able to figure this out :)

Cool!

It's nice that you've found this, and are interested. There are clues elsewhere in the thread, but email me for another clue, or an explanation. Address is in my profile.

Hm, seems pretty straightforward. Can't think of any "interesting" consequences right now, but I wouldn't be surprised if there's a few interesting things about it that I'm not thinking of right now.

If you think it's straight-forward then here's an example:

k=7, p(k)=12028

What's p(x)? How did you find it?

https://pastebin.com/A3AxRkDT

Just out of interest, can you find a connection to something more "everyday" ??

[redacted]

Yup.

I guess that since the post (and the previous) seems to have attracted almost no interest, the fact that you've given it away doesn't really matter - probably very few people are reading it anyway.

In my experience most people find this connection surprising, and you can get a sense of that from some of the other reactions here, although I deduce from your tone that you don't. Which I find interesting.

Thank you for interacting - any further comments would be welcome.

Oh, sorry, I thought you asking meant you wanted me to post the details, should have looked at the entire thread again :/ EDIT: could still edit, so edited.

I guess I find it not that interesting because I spent a lot of high school with math and math puzzles, so my threshold for "surprising" is higher - although when I wrote the first comment I hadn't made the connection, only when I typed it out later, in a slightly different form than I had in my head it was clear.

Oh - thanks for redacting - appreciated. Mind you, very, very few people seem to be interested, which I find curious.

Nice that you didn't initially make the connection, and it came to you later - that's a nice progression. Thanks for letting me know.

The question is not well defined. If m is the degree of the polynomial, you want ∀ i ∈ {0, ..., m}, c_i ≥ 0 and ∃ i ∈ {1, ..., m}, c_i > 0. Otherwise the solution is either trivial or not unique.

> Do you find this interesting?

Depends. For a pedagogical tool in 5th to 8th grades, maybe.

There may be some reason it is a compelling exercise which I am not seeing though. So, you might want to explain why you find this interesting enough to post it twice.

I find it odd that you think the question is not well defined. Choose a polynomial with non-negative integer coefficients. Note that under the usual conventions, the polynomials x^2+1 and x^2+0x+1 are the same. Does that cover the situation you're worried about? Seriously, I don't know anyone who would say that x^2+1 and x^2+0x+1 are different, so maybe I'm not seeing what you're worried about.

However, given that, does it answer your objection?

As to why I think it's interesting, I think it's slightly surprising that given k=6 and p(k)=665 then the polynomial is uniquely identified as 3x^3+2x+5.

Do you not find that surprising? If you don't find it surprising, how would you explain it?

> I find it odd that you think the question is not well defined.

You must assume that at least some of the coefficients of the x terms are non-zero.

> Do you not find that surprising?

No.

> how would you explain it?

I think it is up to you to explain why this is interesting.

Without the condition that k is greater than all the coefficients, the solution is clearly non-unique.

Given that, the assumption of the coefficients are integers, and that the solution is not a constant polynomial, the statement becomes equivalent to "division is a function".

>> I find it odd that you think the question is not well defined.

> You must assume that at least some of the coefficients of the x terms are non-zero.

That turns out not to be the case.

>> Do you not find that surprising?

> No.

Interesting.

>> how would you explain it?

> I think it is up to you to explain why this is interesting.

So far, many people who are clearly intelligent seem to miss that it works at all, let alone how it works. You appear so far to be among them. As I've said elsewhere, I appreciate that you are trying to poke holes in it, but it really is complete and correct as stated.

> Without the condition that k is greater than all the coefficients, the solution is clearly non-unique.

Well, yes. That's why having k greater than all the coefficients is a requirement. That's why your example in another comment elsewhere is not an example of the puzzle failing - it does not satisfy the condition that k must exceed all the coefficients.

> Given that, the assumption of the coefficients are integers, and that the solution is not a constant polynomial, the statement becomes equivalent to "division is a function".

I don't see why this is true - perhaps you could expand on it? Why is the problem statement equivalent to saying "Division is a function."?

So now I don't understand what you're trying to say or do. The question as stated is fine - an example that doesn't satisfy the conditions isn't a counter-example. So at least one of us is confused.

So let me state clearly, rather than having a bitty back'n'forth.

You pick a polynomial p(x) with non-negative integer coefficients. You choose an integer k that's larger than all the coefficients of p(x). You tell me k and p(k). In return, I tell you p(x).

So:

Are you claiming this doesn't work?

Are you claiming it's trivial to accomplish?

Are you claiming it's obvious why it works?

I'm no longer sure what you're claiming, so I thought I'd ask clearly and plainly.

> Are you claiming this doesn't work?

No, I am not. I misinterpreted the "larger than all coefficients" because I was sure that the condition that at least one of the coefficients other than the constant term had to be positive. You pointed out my mistake, you are correct, thank you.

> Are you claiming it's trivial to accomplish?

It is easy to state what you need to do. Find largest a such that k^a ≤ p(k). Find p(k) / k^a using integer division. Because division is a function, there is unique quotient and unique remainder. The quotient is your first coefficient. Take the remainder, repeat.

Right - that's one way of doing it. It's not the way I first thought of, and the other way I have has a connection to something else that I think makes it all kinda nice. That solution is elsewhere in the thread, but here it is in rot13:

jevgrcxvaonfrxnaqgurqvtvgfnergurpbrssvpvragf

I'm pleased we've got it sorted, though. Thanks for your responses, and I'd be happy to hear more thoughts.

Or, roughly equivalently, "our notation for writing down integers makes sense".

I think of it like a coin counting machine.

I don't see how that helps - can you elaborate?

// usage: node coin_counter.js <p(k)> <k>

const args = process.argv.slice(2);

let p_of_x = Number(args[0]); // p(k)

let x = Number(args[1]); // k

const coins = {0:1};

let coin_ndx = 0;

// compute the values of coins to add to purse total

// exit loop when coin face value is too large to subtract from purse

for (let n = 0; Math.pow(x, n) <= p_of_x; n++,coin_ndx++) {

    coins[coin_ndx] = Math.pow(x, n); // compute coin face values

}

console.log("Show face values of coins:");

let keys = Object.keys(coins);

keys.sort();

// find the largest exponent (max_key)

let max_key = 0;

for (let key in keys) {

    console.log(key, coins[key]);

    max_key = key; // use current largest

}

console.log("Show polynomial");

let purse = p_of_x; // purse is sum of coins

for (max_key; max_key >= 0; max_key--) {

    let count = 0;

    while (coins[max_key] <= purse) {

         purse -= coins[max_key];

         count++;

    }

    console.log("+" + count + " x**" + max_key);

}

>node coin_counting.js 12028 7

Show face values of coins:

0 1

1 7

2 49

3 343

4 2401

Show polynomial

Edit: exercise for the reader

The face value of each coin is multiplied by the count of the coin type to total to the purse.

Or rather, the sum of the nth powers of k multiplied by each positive coefficient equals the value of the function at k.

Edit: Source in sibling.

Wow, what an interesting approach! Thank you ... I've copied that out to a file and I'll study it more later.

Cheers!

Cheers to you. Let me know how close it was to what you were looking for.

https://github.com/techbio/CoinCounting

What you've done is not at all close to the solutions I already have, so it's exactly what I was looking for. On the one hand it's very much more complex, but on the other hand it's a more generic and general solution.

The solutions I have are elsewhere in this thread, sometimes in disguise, and I'm gestating a blog post which I'll eventually submit. If you want to know more feel free to email me - address is in my profile.

Added in edit: I would add that your code gives no hint as to why the solution should be unique.

It is not going to handle a vast range of inputs, including for example, p(k) = 665, for the basic reason that my code is a direct response to your request for an explanation and not proposed as a complete solution for the request of your original submission.

Corrections requested, please. I would like to explore this paradigm to accurately address the problem in an exact way.

I'll reply to your email ... thanks.

Reply on news.ycombinator.com