Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is it possible to find this number without brute force?

  1. Aug 21, 2015 #1
    Sorry if this is the wrong thread, seems appropriate but I'm kind of just learning math. This started as a thought experiment to learn some new technique. I've been trying to compute the total number of integer polynomials under certain restrictions: such that all coefficients, x, and the constant term are all among the variables within the count.

    I was told that this can only be done by brute force/enumeration, but I feel like there must be a way otherwise.

    Basically all polynomials must suit the following restrictions:

    ± ax³ ± bx² ± cx ± d = 0

    Such That...

    1 ≤ a ≤ 100 ∈ ℤ [a ≠ 0 since it's a 3rd degree]
    0 ≤ b ≤ 100 ∈ ℤ
    0 ≤ c ≤ 100 ∈ ℤ
    0 ≤ d ≤ 100 ∈ ℤ
    0 ≤ x ≤ 100 ∈ ℤ

    1(1)³ + 1(1)² - 1(1) - 1 = 0 ... is an example that would be counted....

    2(1)³ + 2(1)² - 2(1) - 1 = 0 ... is not an example because... 2(1)³ + 2(1)² - 2(1) - 1 = 1

    Could I create a 6D space for ax³ + bx² + cx + d = n and focus on the root for n between -100 and 100 ?

    Do you have any way I could approach this problem?
  2. jcsd
  3. Aug 22, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    Are you looking for all polynomial functions that have an integer root? It might be possible to use those roots as starting point - they allow to factor the polynomial, All polynomials ##(Ax^2+Bx+C)(x-x_0)## have an integer root at x0, and figuring out how many there are that satisfy the other conditions could be faster than brute force. Avoiding double counting might be complicated.

    Without loss of generality, you can assume that the first summand is positive. Negative x are not allowed? That would make the problem more symmetric.
  4. Aug 22, 2015 #3
    Not necessarily, more so the permutations where all coefficients, the x variable, and constant term are considered and all some combination between -100 and 100 such that, the combination satisfies the RS to equal 0.

    I'm trying to imagine a 6D surface: ax³ + bx² + cx + d = y ... It would be like a lower dimensional, x,y,z surface exhibiting all of the possibilities for that function, but just in a higher dimensional topology. I've heard in theory it should still work the same, so I was hoping the y intercepts could be sorted because thats where all of my answers are.

    I've also been considering factored form as well, but not all integer polys can be factored and they won't neccesary factor all the same way so it's much harder to consider I think.
  5. Aug 22, 2015 #4


    User Avatar
    2017 Award

    Staff: Mentor

    What about x^3-4x^2+5x-2?
    This has the solutions x=1 and x=2. If that is counted twice, then the approach I described in post 2 should work well because you don't have to care about double-counting.

    All polynomials with integer roots can be factored that way. The second part (the quadratic one) might not have real factors - so what?
  6. Aug 22, 2015 #5
    Yes, it would be counted twice. All root possibilities for any given polynomial would be a unique combination, and there is no rule saying that number can't repeat or anything either.

    Thanks, I'm going to think about this and see what I come up with.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Is it possible to find this number without brute force?
  1. Finding nth PDS number (Replies: 2)